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

원리 : 여러 가지 순열과 조합의 해석

원순열

회전의 관점 : 한 바퀴 회전하는 동안 $n$번 겹치므로, $\div n$

서로 다른 $n$개를 일단 $n!$으로 배열한 후, 이 각각을 원형으로 배열하면 회전하여 서로 겹치는 경우가 $n$가지씩 있습니다. 따라서 수형도의 마지막 마디 $n$개를 $1$개로 축소시켜 $n! \div n =\left( n-1 \right) !$이라 구할 수 있습니다.

고정의 관점 : 일단 한 명을 먼저 앉혀서 회전을 차단한 뒤, $(n-1)$명을 배열

원순열의 어려운 점은, 원탁을 회전시킬 수 있어 겹치는 경우가 발생한다는 점입니다. 이를 해결하기 위해서는 회전을 차단시킬 필요가 있습니다.
$n$명 중에서 일단 원탁을 고정시킬 사람을 한 명 정합니다. 이때 처음 앉는 사람은 누가 선택되어도 상관없고, 그 사람이 어느 자리에 앉아도 상관없습니다. 따라서 이 사람을 고르는 방법의 수도 $1$이고, 이 사람이 앉을 자리를 정하는 방법의 수도 $1$입니다.

이제 한 명이 원탁이 회전되지 않도록 붙잡고 있으므로, 나머지 $n-1$개의 자리는 잘 구별됩니다.1그림에는 ①, ②, \hcn3으로 세 자리가 잘 구별되고 있습니다. ①은 탁자를 붙잡은 사람의 오른쪽 자리, ②는 탁자를 붙잡은 사람과 마주보는 자리, \hcn3은 탁자를 붙잡은 사람의 왼쪽 자리로 모두 잘 구별됩니다. 따라서 나머지 $(n-1)$명을 $(n-1)$개의 자리에 앉히면 되므로, 원순열의 수는 $1\times1\times \left( n-1 \right) ! = \left( n-1 \right) !$입니다.

중복순열 : $\NPIR nr$은 버린다. $n^r$일 뿐.

중복순열은 곱의 법칙을 $r$번 거듭 적용한 $n\times n \times \cdots \times n=n^r$에 불과합니다. 따라서 앞으로 $\NPIR nr$이라는 표현은 쓸 일이 없을 것입니다.

조합 관련 공식의 해석

$\NCR nr = \NCR{n-1}{r-1} + \NCR{n-1}{r}$ : 분류와 합의 법칙

$\NCR 73$과 $\NCR 62+\NCR 63$를 생각해봅시다. $\NCR 73$은 $7$개 중에서 $3$개를 택하는 방법의 수를 의미합니다. 이는 $7$개 중 어떤 항목 $\mrm{A}$를 택하는 경우$\cthcn1$과 $\mrm{A}$를 택하지 않는 경우$\cthcn2$로 분류할 수 있고, 계산하면 ①은 $\NCR 62$, ②는 $\NCR 63$입니다. 따라서 합의 법칙에 의해 $\NCR 73 = \NCR 62 + \NCR63$입니다.2이는 분류의 기준을 $\mrm{A}$ 대신 다른 것으로 정해도 마찬가지입니다.

이를 일반화한 것이 $\NCR nr = \NCR{n-1}{r-1} + \NCR{n-1}{r}$입니다. 단순히 조합의 정의에 대입하여 계산해도 참임을 알 수 있고, 실제 상황에도 잘 부합함을 알 수 있습니다.

$n \times \NCR{n-1}{r-1} = r \times \NCR nr$ : 순서를 고려하면 조합이 아니다.

위 공식은 식을 약간 변형한 것을 통해 이해하는 것이 좋습니다. 양변을 $r$로 나눈 $\NCR nr$과 $n \times \NCR{n-1}{r-1} \div r$로 생각하는 것입니다.

$\NCR nr$과 $n \times \NCR {n-1}{r-1}$을 각각 해석해봅시다. $\NCR nr$은 $n$개 중 $r$개를 택하는 것입니다. $n \times \NCR {n-1}{r-1}$은 먼저 $n$개 중 $1$개를 택하고, 그 후에 나머지 $n-1$개 중 $r-1$개를 택하는 것입니다. 언뜻 보면 두 식의 의미가 같아 보이지만, 실제로는 아닙니다. 실제로는 후자에 $\div r$을 해주어야 두 식이 동일한 의미를 갖습니다. 그래서 $\NCR nr \ne n \times \NCR {n-1}{r-1}$이고, $\NCR nr = n \times \NCR{n-1}{r-1} \div r$인 것입니다.

예를 들어 $\mrm{ABCD}$ 네 개 중에서 $3$개를 고르는 상황을 생각해봅시다. 처음에 $\mrm{A}$를 고르고 나중에 $\mrm{BC}$를 고르는 경우도 $\mrm{ABC}$이지만, 처음에 $\mrm{B}$를 고르고 나중에 $\mrm{AC}$를 골라도, 처음에 $\mrm{C}$를 고르고 나중에 $\mrm{AB}$를 골라도 $\mrm{ABC}$입니다. 따라서 하나의 경우 $\mrm{ABC}$가 $3$가지의 경우로 증폭되므로 $\div 3$을 해주어야 합니다.

이를 일반화한 것이 $n \times \NCR{n-1}{r-1} = r \times \NCR nr$입니다. 조합 $\NCR nr$에서는 순서를 고려하지 않고 세는데, $n \times \NCR {n-1}{r-1}$에서는 무엇을 먼저 택하고 무엇을 나중에 택하는지를 통해 순서를 고려하여 셉니다. 따라서 후자에서 순서를 고려함으로써 증폭된 부분을 나눗셈을 이용해 축소시키고 나서야 비로소 두 식의 의미가 서로 같아지게 됩니다. 단순히 조합의 정의에 대입하여 계산해도 참임을 알 수 있고, 실제 상황에도 잘 부합함을 알 수 있습니다.

같있순(같은 것이 있는 순열)의 해석

\subsection[일반적인 해석]일반적인 경우 : 나눗셈으로 해석(가짓수의 축소) 같있순은 나눗셈을 이용하여 가짓수를 축소하는 것으로 해석할 수 있습니다. 즉 같있순의 공식 $\dfrac{n!}{p!q!\cdots r!} $를 해석하면 다음과 같습니다. \[\begin{align*} \dfrac{n!}{p!q!\cdots r!} = n! \times \dfrac{1}{p!} \times \dfrac{1}{q!} \times \cdots \times \dfrac{1}{r!} \end{align*}\]

(두 종류만 있을 때) 조합으로 해석 : 위치만 선택하면 끝 ($a+b=n$일 때 $\NCR na = \NCR nb$)

$n$개가 두 종류 $A$, $B$로만 구성되어 있고 $A$가 $a$개, $B$가 $b$개 있을 때를 생각해봅시다. $a+b=n$이므로 같있순으로 계산하면 $\dfrac{n!}{a!b!} = \dfrac{n!}{a!\left( n-a \right)! }$입니다. 그런데 식의 구조를 보면 $\NCR na$와 완전히 동일하네요?

이는 두 종류만 있을 때는 $n$개 중에서 $A$가 놓일 위치 $a$개를 고르면 자동으로 나머지 자리를 $B$가 차지하며 배열이 끝나기 때문입니다. 마찬가지로 $\dfrac{n!}{a!b!}=\dfrac{n!}{\left( n-b \right)!b! }=\NCR nb$라 해석하는 것도 가능합니다.3이는 앞서 설명했던 조합의 대칭성인 $\NCR nr = \NCR{n}{n-r}$과 동일한 상황입니다.

중복조합의 해석

중복조합의 대표적인 두 가지 상황

중복조합은 `$n$개 중에서 중복을 허용하여 $r$개를 뽑는다'는 상황인데, 이에 부합하는 대표적인 상황은 다음의 두 가지입니다. \[\begin{gather*} 3 \le a \le b \le c \le d \le 7\quad (\text{단, $a$, $b$, $c$, $d$는 정수이다.} )\\ x+y+z=8\quad \left( \text{단, $x$, $y$, $z$는 음이 아닌 정수이다.}\right) \end{gather*}\] 전자는 $3$, $4$, $5$, $6$, $7$의 $5$개 중에서 중복을 허용하여 $4$개$\xyzw abcd$를 선택하여 순서쌍 $\xyzw abcd$의 개수를 구하는 상황이므로 중복조합 $\NHR 54$의 정의에 부합합니다.4$4$개를 선택하면 $a, \, b, \, c, \, d$의 대소 관계, 즉 순서가 정해져 있으므로 순서쌍이 하나로 정해집니다. 후자는 $x$, $y$, $z$의 방정식의 해를 순서쌍 $\xyz xyz$로 나타낼 때, 순서쌍의 세 성분이 각각 `$x$가 몇 번 선택되었는가', `$y$가 몇 번 선택되었는가', `$z$가 몇 번 선택되었는가'를 의미하므로, $3$개 중에서 중복을 허용하여 $8$개를 선택하는 중복조합 $\NHR 38$의 정의에 부합합니다.

\subsection[중조딱]$x+y+\cdots+z = r$ (단, $x$, $y$, $\cdots$, $z$는 음이 아닌 정수)를 통해 중복조합 혼동 피하기 중복조합 관련 문제를 풀 때, `$n$개 중에서 중복을 허용하여 $r$개를 뽑는다'는 정의를 혼동하는 경우가 많습니다. 이를테면, 문제에서는 $5$개 중에서 중복을 허용하여 $8$개를 뽑으라고 했는데, $n$과 $r$의 역할을 혼동하여 $\NHR 58$을 구해야 할 때 $\NHR 85$라고 답하는 것입니다. 이러한 혼동을 피하기 위해서는, 중복조합에 대해 항상 다음과 같이 생각하면 됩니다.

$x+y+\cdots+z=r$을 만족시키는 $n$개의 음이 아닌 정수 $x$, $y$, $\cdots$, $z$의
순서쌍 $(x,\:y,\:\cdots,z)$를 구하는 상황은 중복조합 $\NHR nr$으로 해결한다.
이를 조금 더 형식적으로 나타내면 다음과 같습니다.
정수 $r$과 $1\le k \le n$인 정수 $k$에 대하여 $a_k$가 항상 음이 아닌 정수일 때
$\sum_{k=1}^{n}a_k = r$를 만족시키는 순서쌍 $(a_1,\:a_2,\:\cdots,a_n)$을 구하는 상황은
중복조합 $\NHR nr$으로 해결한다.
그럼 앞서 중복조합의 대표적인 상황이라고 했던 $3 \le a \le b \le c \le d \le 7$의 형태도 동일하게 표현할 수 있을 것입니다. 이는 아래 문제를 풀며 생각해봅시다.

$3 \le a \le b \le c \le d \le 7$인 순서쌍 $\xyzw abcd$를 구하는 상황을 $\sum_{k=1}^{n}s_k = r$를 만족시키는 순서쌍 $(s_1,\:s_2,\:\cdots,s_n)$을 구하는 상황으로 바꾸어 나타내시오.
$3\le k\le 7$인 정수 $k$에 대하여 $k$가 선택된 횟수를 $s_{k-2}$라 하면, $\sum_{k=1}^{5}s_k=4$입니다.5$k$가 선택된 횟수를 $t_{k}$라 하고 $\sum_{k=3}^{7}t_k=4$라 나타낼 수도 있습니다. 따라서 중복조합의 대표적인 두 상황 중 전자는 후자로 바꾸어 생각할 수 있으므로,6추가로 설명하지는 않겠지만, 후자를 전자로 바꾸는 것도 얼마든지 가능합니다. 앞으로는 모든 중복조합 문제를 후자로 바꾸어 생각해도 됩니다.

중복조합 공식의 유도과정

$n$과 $r$을 헷갈리지 않는 방법은 알았지만, 정작 그 순서쌍의 개수를 구하는 방법은 아직 배우지 않았습니다. 이를 유도하는 대표적인 아이디어 두 가지를 배워봅시다. 먼저 간단한 예시인 $x+y+z=4$와 $1\le a \le b \le c \le d \le 3$로 생각해봅시다.7두 상황은 모두 $\NHR 34$로 같습니다.
$\NHR 34$를 $x+y+z=4$을 만족시키는 음이 아닌 정수 $x$, $y$, $z$의 순서쌍 $\xyz xyz$로 설명하기(칸막이 아이디어)
조건을 만족시키는 순서쌍 $\xyz xyz$를 모두 구해봅시다. \[\begin{align*} &\xyz400,\quad \xyz040,\quad \xyz004\\ &\xyz310,\quad \xyz301,\quad \xyz130,\quad\xyz103,\quad \xyz031,\quad \xyz013\\ &\xyz220,\quad \xyz202,\quad \xyz022\\ &\xyz211,\quad \xyz121,\quad \xyz112 \end{align*}\] 이 $15$개의 순서쌍은 모두 `$4$개의 $\HCIRCLE$와 $2$개의 \HSQUARE의 배열'로 바꾸어 생각할 수 있습니다.
이때 $\HCIRCLE$은 선택을 의미하고, \HSQUARE은 무엇을 선택하는지를 구별해주는 칸막이를 의미합니다. $\HCIRCLE$이 $4$개인 것은 $x+y+z=4$에서 우변의 값이 $4$이기 때문이고, \HSQUARE이 $2$개인 것은 $x+y+z=4$에서 $x$, $y$, $z$를 서로 구별해주는 덧셈 기호인 $+$의 개수가 $2$이기 때문입니다.8$x$, $y$, $z$의 $3$개 항목을 구별하기 위해서는 $3-1=2$개의 칸막이가 필요하다고 생각할 수도 있습니다.

따라서 우리가 구하는 순서쌍의 개수는 $4$개의 $\HCIRCLE$과 $2$개의 \HSQUARE을 배열하는 경우의 수와 같습니다. 이를 같있순으로 설명하면 $\dfrac{6!}{4!2!}$이고, 조합으로 설명하면 $\NCR 62 = \NCR 64$입니다. 따라서 $\NHR 34 = \NCR{3+4-1}{4} = \NCR62$가 성립하고, 이를 일반화하면 $\NHR nr = \NCR{n+r-1}{r}$입니다.9$n$개의 $\HCIRCLE$와 $r$개의 항목을 구별해주는 $r-1$개의 칸막이 \HSQUARE을 배열하는 것이므로 $\NCR {n+r-1}r$에서 $n+r-1 = n + (r-1)$이라 생각할 수 있습니다.

$\NHR 34$를 $1\le a \le b \le c \le d \le 3$를 만족시키는 정수 $a$, $b$, $c$, $d$의 순서쌍 $\xyzw abcd $를$\xyzw{a}{b+1}{c+2}{d+3}$로 변형하여 설명하기 ($\mrm{H}$와 $\mrm{C}$ 사이의 일대일대응 아이디어)
조건을 만족시키는 순서쌍 $\xyzw abcd$을 모두 구해봅시다. \[\begin{align*} &\xyzw1111,\quad \xyzw1112,\quad \xyzw1113\\ &\xyzw1122,\quad \xyzw1123,\quad \xyzw1133\\ &\xyzw1222,\quad \xyzw1223,\quad \xyzw1233\\ &\xyzw1333\\ &\xyzw2222,\quad \xyzw2223,\quad \xyzw2233\\ &\xyzw2333\\ &\xyzw3333 \end{align*}\] 이때 구한 각각의 순서쌍에서 $b$에는 $1$을 더하고, $c$에는 $2$를 더하고, $d$에는 $3$을 더하면 다음과 같습니다. \[\begin{align*} &\xyzw1234,\quad \xyzw1235,\quad \xyzw1236\\ &\xyzw1245,\quad \xyzw1246,\quad \xyzw1256\\ &\xyzw1345,\quad \xyzw1346,\quad \xyzw1356\\ &\xyzw1456\\ &\xyzw2345,\quad \xyzw2346,\quad \xyzw2356\\ &\xyzw2456\\ &\xyzw3456 \end{align*}\] 이는 $1$, $2$, $3$, $4$, $5$, $6$ 중에서 $4$개의 수를 고르는 경우의 수 $\NCR64$와 같으므로, $\NHR 34 = \NCR64$입니다. 이를 일반화하면 $1\le a_1 \le a_2 \le \cdots \le a_r \le n$를 만족하는 순서쌍 $(a_1,\: a_2,\:,a_3,\: \cdots,\: a_r)$의 개수는 $1$, $2$, $\cdots$, $n+r-2$, $n+r-1$ 중에서 $r$개를 택하는 경우의 수와 같습니다. 따라서 $\NHR nr = \NCR{n+r-1}{r}$입니다.
  1. 1. 그림에는 ①, ②, \hcn3으로 세 자리가 잘 구별되고 있습니다. ①은 탁자를 붙잡은 사람의 오른쪽 자리, ②는 탁자를 붙잡은 사람과 마주보는 자리, \hcn3은 탁자를 붙잡은 사람의 왼쪽 자리로 모두 잘 구별됩니다.
  2. 2. 이는 분류의 기준을 $\mrm{A}$ 대신 다른 것으로 정해도 마찬가지입니다.
  3. 3. 이는 앞서 설명했던 조합의 대칭성인 $\NCR nr = \NCR{n}{n-r}$과 동일한 상황입니다.
  4. 4. $4$개를 선택하면 $a, \, b, \, c, \, d$의 대소 관계, 즉 순서가 정해져 있으므로 순서쌍이 하나로 정해집니다.
  5. 5. $k$가 선택된 횟수를 $t_{k}$라 하고 $\sum_{k=3}^{7}t_k=4$라 나타낼 수도 있습니다.
  6. 6. 추가로 설명하지는 않겠지만, 후자를 전자로 바꾸는 것도 얼마든지 가능합니다.
  7. 7. 두 상황은 모두 $\NHR 34$로 같습니다.
  8. 8. $x$, $y$, $z$의 $3$개 항목을 구별하기 위해서는 $3-1=2$개의 칸막이가 필요하다고 생각할 수도 있습니다.
  9. 9. $n$개의 $\HCIRCLE$와 $r$개의 항목을 구별해주는 $r-1$개의 칸막이 \HSQUARE을 배열하는 것이므로 $\NCR {n+r-1}r$에서 $n+r-1 = n + (r-1)$이라 생각할 수 있습니다.