확률과 통계 > 여러 가지 순열과 조합

이해 : 소소한 변형의 거대한 나비효과

분류의 기준 : 인싸와 아싸

문제에서 특정한 항목이 여러 항목에 한꺼번에 영향을 줄 수 있는 인싸인 경우, 인싸를 기준으로 분류하는 것이 타당해 보입니다. 인싸의 값이나 위치가 정해짐에 따라 다른 항목들이 동시에 영향을 받아 문제의 상황이 간단해질 수 있기 때문입니다.

반대로 문제에서 다른 항목과 달리 어떤 항목만 무언가 독특한 제한이나 자유를 가지고 있는 아싸인 경우, 아싸를 기준으로 분류하는 것도 타당해 보입니다. 아싸의 위치나 값을 먼저 처리하고 나면 다른 평범한 항목들끼리 평범하게 문제를 해결할 수 있기 때문입니다.

인싸든 아싸든 분류의 기준을 명확히 잡는 것이 중요합니다. 한 문제를 인싸를 기준으로도 풀어보고 아싸를 기준으로도 풀어보면 문제를 두 개 푸는 효과를 얻을 수 있을 것입니다.

순열 시리즈의 소소한 변형

부분집합의 개수

$n\left( A \right) = k $인 집합의 원소를 각각 $a_1$, $a_2$, $\cdots$, $a_k$라 할 때, $A$의 부분집합 $B$에는 $a_1$이 속할 수도 있고, 속하지 않을 수도 있습니다. 이는 $a_2$, $a_3$, $\cdots$, $a_k$ 모두 마찬가지입니다. 따라서 서로 다른 $B$의 개수는 $2^k$입니다.1진부분집합의 개수는 이 값에서 집합 $A$ 자기 자신의 개수인 $1$을 뺀 $2^k -1$입니다.

이웃하게 배열하기

특정 항목이 서로 이웃하게 배열하려면, 이웃하는 항목들을 하나의 그룹으로 묶고, 그 그룹을 하나의 항목인 것처럼 간주한 채로 배열한 다음, 그룹 내에서의 배열을 처리해주면 됩니다.

달랐는데요, 같았습니다.

특정 항목의 순서가 이미 정해져 있는 경우, 순서가 정해진 대상들을 서로 같다고 가정한다면, 같있순과 동일한 상황이 됩니다.

물물교환

$n$명이 서로의 물건을 바꾸어 가지는 경우입니다. 당연히 자신의 물건은 자신이 가져서는 안 되겠지요.2교란순열이라는 이름으로 불리기도 합니다만, 교과 외 용어이니 참고만 하시기 바랍니다. 아래 문제를 풀어봅시다.
다음을 구하시오.
  1. 두 명이 서로 물물교환하는 방법의 수
  2. 세 명이 서로 물물교환하는 방법의 수
  3. 네 명이 서로 물물교환하는 방법의 수
  4. 다섯 명이 서로 물물교환하는 방법의 수
다음을 구하시오.
  1. 두 명이 서로 물물교환하는 방법의 수
  2. 세 명이 서로 물물교환하는 방법의 수
  3. 네 명이 서로 물물교환하는 방법의 수
  4. 다섯 명이 서로 물물교환하는 방법의 수
이러한 경우는 수형도를 그려 해결하는 것이 일반적입니다.3물물교환의 결과인 $1$, $2$, $9$, $44$를 외워두면 편리합니다.

원순열의 소소한 변형

돌리고, 또 돌리고

원순열의 상황을 겹겹이 쌓은 듯하게 모양을 설정하는 경우가 있습니다. 이럴 때에는 한 바퀴 회전하는 동안 겹치는 경우가 생기는지를 유의해야 하고, 겹치는 경우가 적은 것부터 생각하는 것이 좋습니다. 예를 들어, (a)와 같은 경우 안쪽에 칠할 색을 정하더라도, 바깥쪽을 칠할 때 회전하여 겹칠 수 있으므로 원순열의 논리를 적용해야 합니다. 반면 (b)와 같은 경우 안쪽을 원순열로 칠하면 `고정의 관점'이 적용되어 나머지 자리들이 고정되므로 바깥쪽에 원순열의 논리를 적용해서는 안 됩니다. 또한, 바깥쪽을 먼저 칠할 경우, 원순열의 논리를 적용할 때 주의해야 합니다. 안쪽 그림의 모양으로 인해 한 바퀴 회전하면 겹치는 횟수가 기존의 $4$번이 아닌, $2$번이므로 $\dfrac{4!}{2}$으로 계산해야 하기 때문입니다.4고정의 관점($2\times 3!$)으로도 계산해보시기 바랍니다.

원이 없는 원순열

원은 아니지만 원순열과 같은 논리로 설명할 수 있는 삼각형, 정사각형, 직사각형에 자리를 배치하는 문제도 풀이할 수 있습니다. 원순열의 논리를 그대로 사용하기에, 당연히 회전의 관점으로도, 고정의 관점으로도 풀 수 있습니다.

\section[중복조합 변형꼴]중복조합의 소소한 변형 $x+y+\cdots z=n$ 꼴이기는 하지만, $x$, $y$, $\cdots$, $z$가 음이 아닌 정수가 아닐 수도 있습니다. $x+y+z=n$인 경우를 예를 들어 설명하겠습니다.

자연수 또는 특정 값 이상의 수

$x+y+z=n$인 자연수 $x$, $y$, $z$의 순서쌍 $\xyz xyz$의 개수를 구하려면 계산의 편의를 위해 음이 아닌 정수 $x'$, $y'$, $z'$를 도입하면 됩니다. 세 자연수를 각각 $x=x'+1$, $y=y'+1$, $z=z'+1$이라 하고, 이 세 식을 좌변에 대입하면 $x'+y'+z'=n-3$입니다. 이는 중복조합의 기본꼴에 정확히 부합하므로 순서쌍 $\xyz{x'}{y'}{z'}$의 개수를 구할 수 있고, 이는 곧 순서쌍 $\xyz xyz$의 개수와 같습니다.5두 순서쌍은 서로 일대일대응되기 때문에 개수가 같습니다.
이는 칸막이로 해석할 때, 각 칸막이 \HSQUARE로 나누어져 있는 영역마다 미리 $\HCIRCLE$을 하나씩 배열해놓았다고 간주하고, 나머지 $n-3$개의 $\HCIRCLE$과 $2$개의 \HSQUARE를 배열하는 것이라 생각할 수 있습니다. 각각의 값이 $i$, $j$, $k$ 이상의 정수인 경우도 마찬가지입니다. 같은 원리로 미리 $\HCIRCLE$을 $i$, $j$, $k$개씩 미리 배열해놓았다고 간주하고,6$i$, $j$, $k$는 개수이지만 $0$도 허용됩니다. 이 경우 해당 항목을 미리 배열해두지 않는 것이라 생각할 수 있습니다. 나머지 $n-\left( i+j+k \right) $개의 $\HCIRCLE$와 $2$개의 \HSQUARE를 배열하는 것이라 생각할 수 있습니다.

홀수 또는 짝수

홀수 또는 짝수라고 하는 경우 자연수 조건도 같이 주는 경우가 많습니다.7$0$과 음수에 대한 홀짝성에 대해 불필요한 오해가 있을 수 있기 때문입니다. 이러한 경우도 역시 음이 아닌 정수 $x'$, $y'$, $z'$를 도입하면 됩니다. 모두 홀수인 경우 $x=2x'+1$, $y=2y'+1$, $z=2z'+1$이라 두고, 모두 짝수인 경우 $x=2x'+2$ $y=2y'+2$, $z=2z'+2$와 같이 둔 다음 식을 정리하기만 하면 끝입니다.

범위 내의 정수

$x+y+z=n$이고 $i_1 \le x \le i_2$, $j_1 \le y \le j_2$, $k_1 \le z \le k_2$인 정수 $x$, $y$, $z$의 순서쌍 $\xyz xyz$를 구해야 하는 경우, $x \ge i_1$, $y \ge j_1$, $z \ge k_1$인 것은 앞서 이야기한 것처럼 처리할 수 있습니다. 문제가 되는 경우는 $i_2$ 또는 $j_2$ 또는 $k_2$의 값보다 작은 경우입니다. 이러한 경우는 여사건으로 처리하는 것이 편리할 것입니다.

등호가 아니라 부등호면, 부등호를 등호로 바꿔보자

$x+y+z \le n$인 음이 아닌 정수 $x$, $y$, $z$의 순서쌍 $\xyz xyz$를 구하려면 $n$의 값에 따라 분류하여 $\sum_{k=0}^{n}\NHR 3k$를 계산하여 구할 수 있습니다. 그러나 이를 쉽게 처리하는 아이디어가 있습니다. 부등호를 등호로 바꾸는 것입니다. 그런데 어떻게 부등호를 등호로 바꿀 수 있을까요?

바로 새로운 음이 아닌 정수 $0 \le w \le n$를 도입하는 것입니다. 새로운 식 $x+y+z+w=n$은 기존의 식 $x+y+z\le n$을 만족시킵니다. 이때 이를 만족시키는 순서쌍 $\xyzw xyzw$을 구하고, 각 순서쌍에서 $w$만 없애버리면, 이는 순서쌍 $\xyz xyz$이 됩니다. 따라서 순서쌍 $\xyzw xyzw$의 개수가 곧 순서쌍 $\xyz xyz$의 개수와 같으므로, $\sum_{k=0}^{n}\NHR 3k$를 계산하지 않고도 한 번에 원하는 값($\NHR{4}{n}$)을 구할 수 있습니다.8두 값이 실제로 같은지는 직접 계산하여 확인해 보시기 바랍니다.

재닛, 지은, 민아, 예원, 리오가 가로로 놓인 다섯 개의 의자에 순서대로 앉아 있었다. 각자가 앉아 있는 의자에 자신의 이름을 적은 후, 다섯 명을 모두 일으켜 세웠다. 이 다섯 명을 다섯 개의 의자에 다시 앉힐 때, 다음을 구하시오.
  1. 민아, 예원, 리오 세 명이 서로 이웃하도록 앉는 방법의 수
  2. 재닛이 항상 지은이보다 왼쪽 위치에 앉게 하는 방법의 수
  3. 모두가 자신의 이름이 적히지 않은 의자에 앉는 방법의 수
  1. 다음의 영역의 개수만큼 서로 다른 색이 있다. 영역에 색을 칠하는 방법의 수를 구하시오. (단, 회전하여 일치하는 것은 같은 것으로 본다.)
  2. 다음의 탁자에 의자 수만큼의 인원을 앉히는 방법의 수를 구하시오. (단, 회전하여 일치하는 것은 같은 것으로 본다.)
재닛, 지은, 민아, 예원, 리오가 가로로 놓인 다섯 개의 의자에 순서대로 앉아 있었다. 각자가 앉아 있는 의자에 자신의 이름을 적은 후, 다섯 명을 모두 일으켜 세웠다. 이 다섯 명을 다섯 개의 의자에 다시 앉힐 때, 다음을 구하시오.
  1. 민아, 예원, 리오 세 명이 서로 이웃하도록 앉는 방법의 수
  2. 재닛이 항상 지은이보다 왼쪽 위치에 앉게 하는 방법의 수
  3. 모두가 자신의 이름이 적히지 않은 의자에 앉는 방법의 수
  1. 민아, 예원, 리오를 $A$라고 둔 후, $A$, 재닛, 지은 세 명을 배열하면 $3!$이고, $A$ 안에서 민아, 예원, 리오를 배열하면 $3!$이므로 $3!\times 3! = 36$입니다.
  2. 재닛과 지은이를 동일하게 `송송'으로 간주하고, 다섯 명의 민아, 예원, 리오, 송송, 송송을 일렬로 세우는 방법의 수는 $\dfrac{5!}{2!} = 60$입니다. 이때 두 송송 중 앞에 서 있는 송송을 재닛으로 보고, 뒤에 서 있는 송송을 지은이로 보면 우리가 원하던 대로 배열할 수 있습니다.
  3. 서로가 서로의 의자를 물물교환하는 상황이므로 $44$입니다.
  1. 다음의 영역의 개수만큼 서로 다른 색이 있다. 영역에 색을 칠하는 방법의 수를 구하시오. (단, 회전하여 일치하는 것은 같은 것으로 본다.)
  2. 다음의 탁자에 의자 수만큼의 인원을 앉히는 방법의 수를 구하시오. (단, 회전하여 일치하는 것은 같은 것으로 본다.)
  1. (a)의 경우, 회전의 관점을 이용하면 한 바퀴 회전할 때 일치하는 경우가 $3$번 생깁니다. 따라서 방법의 수는 $\dfrac{4!}{3} = 8$입니다. 한편, (b)의 경우는 한 바퀴 회전할 때 일치하는 경우가 $2$번 생깁니다. 따라서 방법의 수는 $\dfrac{6!}{2} = 360$입니다.
  2. ①과 마찬가지로 회전의 관점을 이용하면, 한 바퀴 회전할 때 일치하는 경우가 각각 $3$, $4$, $2$번 생깁니다. 따라서 방법의 수는 각각 $\dfrac{6!}{3}$, $\dfrac{8!}{4}$, $\dfrac{10!}{2}$입니다.9고정의 관점으로도 직접 계산해보시기 바랍니다.
  1. 1. 진부분집합의 개수는 이 값에서 집합 $A$ 자기 자신의 개수인 $1$을 뺀 $2^k -1$입니다.
  2. 2. 교란순열이라는 이름으로 불리기도 합니다만, 교과 외 용어이니 참고만 하시기 바랍니다.
  3. 3. 물물교환의 결과인 $1$, $2$, $9$, $44$를 외워두면 편리합니다.
  4. 4. 고정의 관점($2\times 3!$)으로도 계산해보시기 바랍니다.
  5. 5. 두 순서쌍은 서로 일대일대응되기 때문에 개수가 같습니다.
  6. 6. $i$, $j$, $k$는 개수이지만 $0$도 허용됩니다. 이 경우 해당 항목을 미리 배열해두지 않는 것이라 생각할 수 있습니다.
  7. 7. $0$과 음수에 대한 홀짝성에 대해 불필요한 오해가 있을 수 있기 때문입니다.
  8. 8. 두 값이 실제로 같은지는 직접 계산하여 확인해 보시기 바랍니다.
  9. 9. 고정의 관점으로도 직접 계산해보시기 바랍니다.