[조합론] 3. 경우의 수 세기(2: 중복순열, 중복조합, 이항계수의 성질)

[조합론] 3. 경우의 수 세기(2: 중복순열, 중복조합, 이항계수의 성질)

서로 다른 \(n\)개 중에서 중복을 허용해서 \(r\)개를 선택해 일렬로 나열하는 것을 \(n\)개에서 \(r\)개를 선택하는 중복순열(permutation with repetition)이라고 하고 \(_{n}\Pi_{r}\)로 나타내고 \(_{n}\Pi_{r}=n^{r}\)이다.

예: 집합 \(X=\{a,\,b,\,c,\,d\}\)에서 집합 \(Y=\{1,\,2,\,3\}\)으로의 함수의 개수는?

풀이: 함수는 집합 \(X\)의 모든 원소가 집합 \(Y\)의 한 원소에 대응되는 관계이므로 \(1,\,2,\,3\)중에서 중복을 허용하여 \(4\)개를 선택해 나열하는 수와 같으므로 따라서$$_{3}\Pi_{4}=3^{4}=81$$개 이다.

예: 네 문자 \(a,\,b,\,c,\,d\)중에서 중복을 허용해서 2개를 뽑아 나열하는 경우의 수는?

풀이: 4개 중에서 중복을 허용해서 2개를 선택하는 경우의 수는 \(_{4}\Pi_{2}=4^{2}=16\)가지 이다.(아래를 참고)$$\begin{matrix}aa&ab&ac&ad\\ba&bb&bc&bd\\ca&cb&cc&cd\\da&db&dc&dd\end{matrix}$$ 

정리: \(n\)의 원소를 갖는 집합에서 첫번째 유형의 원소가 \(r_{1}\)개, 두번째 유형의 원소가 \(r_{2}\)개, ...., \(n\)번째 유형의 원소가 \(r_{n}\)개 있으면, \(n\)개의 원소를 일렬로 나열하는 경우의 수는$$\frac{n!}{r_{1}!r_{2}!\cdots r_{n}!}\,(r_{1}+r_{2}+\cdots+r_{n}=n)$$이다.

증명:

첫번째 유형의 원소들은 \(\displaystyle\binom{n}{r_{1}}\)개로 선택되고, 두번째 유형의 원소들은 \(\displaystyle\binom{n-r_{1}}{r_{2}}\)개로 선택되며, ...., \(n\)번째 유형의 원소는 \(\displaystyle\binom{n-r_{1}-r_{2}-\cdots-r_{n-1}}{r_{n}}\)개로 선택되므로 따라서$$\binom{n}{r_{1}}\binom{n-r_{1}}{r_{2}}\cdots\binom{n-r_{1}-r_{2}-\cdots-r_{n-1}}{r_{n}}=\frac{n!}{r_{1}!r_{2}!\cdots r_{n}!}$$가지이다.

예: 단어 MISSISSIPPI의 11개의 문자를 모두 재배열해서 나열하면 몇개의 단어가 만들어지는가?

풀이: M이 1개, S가 4개, I가 4개, P가 2개 있으므로$$\frac{11!}{1!4!4!2!}$$가지의 단어가 만들어진다.

(또는 11개의 빈간에 M을 넣을 1칸, S를 넣을 4칸, I를 넣을 4칸, P를 넣을 2칸을 선택하는 방법의 수는$$\binom{11}{1}\binom{10}{4}\binom{6}{4}\binom{2}{2}=\frac{11!}{1!10!}\frac{10!}{4!6!}\frac{6!}{4!2!}\cdot1=\frac{11!}{1!4!4!2!}$$이다.)

정리:(원순열) \(n\)개의 서로 다른 원소의 집합에서 \(r\,(r\leq n)\)개를 선택해 원 위에 나열하는 경우의 수는 \(\displaystyle\frac{_{n}P_{r}}{r}\)이고, 특히 \(n\)개의 원소들의 원순열은 \((n-1)!\)가지이다.

증명: \(r\)개의 원소를 원 위에 나열하면 모두 \(r\)개의 같은 경우가 되기 때문에 따라서 \(n\)개에서 \(r\)개를 선택해 원 위에 나열하는 경우의 수는 \(\displaystyle\frac{_{n}P_{r}}{r}\)이다. 같은 이유로 \(n\)개의 원소들의 원순열은 \(\displaystyle\frac{n!}{n}=(n-1)!\)이다. 

예: 어느 식당에서 다섯 쌍의 부부가 원탁에 둘러 앉아 저녁식사를 한다. 

(1) 모든 부부가 자신의 남편 또는 아내와 이웃하게 앉는 경우의 수는?

(2) 어떤 한 부부(최씨 부부)는 서로 떨어져서 앉기를 원하면, 그 경우의 수는?(다른 부부는 이웃할 수도 있고 아닐 수도 있다.)

풀이:

(1) 부부를 하나로 묶어서 다섯 쌍을 원탁에 앉게 하는 경우의 수는 \(4!\)이고, 남편과 아내가 서로 자리를 바꾸는 경우의 수는 각각 2!이므로 \(4!\times(2!)^{5}=768\)가지 이다.

(2) 10명에 대한 원순열의 수는 \(9!\)이고, 최씨부부가 이웃하게 앉는 방법의 수는 그 부부를 한 묶음으로 보고 그 부부가 자리를 바꿔 앉는 경우이므로 \(8!\cdot2!\)이다. 따라서 \(9!-8!\cdot2!=7\cdot8!\)가지 이다.

(또는 최씨부부의 남편(또는 부인)을 고정된 자리에 앉히면, 부인(또는 남편)은 남편(또는 부인)의 양 옆에 앉을 수 없다.

고정된 남편(또는 부인)의 왼쪽(또는 오른쪽)에는 최씨 부부를 제외한 8명이 앉을 수 있고, 오른쪽(또는 왼쪽)옆에는 나머지 7명이 앉을 수 있다. 그리고 나머지 자리에 최씨 부인(또는 남편)을 포함한 7명이 앉으면 되므로 따라서 \(8\cdot7\cdot7!=7\cdot8!\)가지 이다.)

정리: 일차 부정방정식 \(x_{1}+x_{2}+\cdots+x_{n}=k\)의 음이 아닌 정수해의 개수는 \(\displaystyle\frac{(n+k-1)!}{(n-1)!k!}\)이다.

증명: 음이 아닌 정수해의 개수는 \(n\)개의 빈 상자에 \(k\)개의 공을 넣는 경우이고, 이때 \(k\)개의 공과 \(n-1\)개의 칸막이의 순열로 볼 수 있으므로 따라서 이 부정방정식의 음이 아닌 정수해의 개수는 \(\displaystyle\frac{(n+k-1)!}{(n-1)!k!}\)이다.

위의 정리를 이용하여 중복조합을 정의할 수 있다.

서로 다른 \(n\)개에서 중복을 허용해서 \(r\)개를 선택하는 것을 \(n\)개에서 \(r\)개를 선택하는 중복조합(combination with repetition)이라 하고 \(_{n}H_{r}\)로 나타내고 \(\displaystyle_{n}H_{r}=\binom{n+r-1}{r}\)이다.

증명: \(n\)개의 원소 \(s_{1},\,s_{2},\,\cdots,\,s_{n}\)중에서 중복을 허용하여 \(r\)개를 뽑았을 때, \(s_{i}\)의 개수를 \(m_{i}\)라고 하자. 그러면$$m_{1}+m_{2}+\cdots+m_{n}=r\,(m_{i}\geq0)$$이고, 역으로 부정방정식$$x_{1}+x_{2}+\cdots+x_{n}=r$$의 음이 아닌 정수해는 \(n\)개의 원소 중에서 중복을 허용해 \(r\)개를 선택하는 경우에 대응된다. 따라서 \(_{n}H_{r}\)은 위의 부정방정식의 음이 아닌 정수해의 개수와 같고, 또한 \(r\)개의 공과 \(n-1\)개의 칸막이의 순열의 개수와 같으며 \(n+r-1\)개의 자리 중 공이 놓일 \(r\)개의 자리를 선택하는 조합의 수와 같으므로 따라서$$_{n}H_{r}=\binom{n+r-1}{r}$$이다.

예: 어느 도서관에 한식, 중식, 일식 요리책이 각각 6권 있다. 이 3종류의 책 중에서 6권을 선택하는 경우의 수는?

풀이: 3개 중에서 6개를 선택하는 중복조합의 수와 같으므로 \(\displaystyle_{3}H_{6}=\binom{3+6-1}{6}=\binom{8}{6}=28\)가지 이다.

예: 부등식 \(x_{1}+x_{2}+x_{3}\leq17\)을 만족하는 음이 아닌 정수해의 개수는?

풀이: \(y=17-x_{1}+x_{2}+x_{3}\)이라고 하면, \(y\geq0\)이어야 하고 따라서 이 부등식을 만족하는 음이 아닌 정수해의 개수는 다음의 부정방정식$$x_{1}+x_{2}+x_{3}+y=17$$을 만족하는 음의 아닌 정수해의 개수와 같고 따라서 이 부등식을 만족하는 해의 개수는 \(\displaystyle_{4}H_{17}=\binom{17+4-1}{4}=\binom{20}{17}=1140\)개이다. 

\(n\)개에서 \(r\)개를 선택하는 조합의 수 \(\displaystyle\binom{n}{r}\)를 이항계수(binomial coefficient)라고 한다.

다음은 이항계수들로 구성된 파스칼의 삼각형(Pascal's triangle)이다.

  

이 파스칼의 삼각형으로부터 모든 정수 \(0\leq r\leq n\)에 대해$$\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$$이 성립한다.

정리:(이항정리, binomial theorem) 다음의 등식$$(x+y)^{n}=\binom{n}{0}x^{n}+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^{2}+\cdots+\binom{n}{n}y^{n}=\sum_{r=0}^{n}{\binom{n}{r}x^{n-r}y^{r}}$$이 성립한다.

증명: 다음의 등식$$(x+y)^{n}=(x+y)(x+y)\cdots(x+y)$$를 분배법칙을 이용하여 전개할 때, 전개식의 각 항은 \(x^{r}y^{n-r}\,(r=0,\,1,\,\cdots,\,n)\)이다. 이때 \(x^{r}y^{n-r}\)을 얻기 위해서는 \(r\)개의 인수에서 \(x\)를 선택하고, 나머지에서 \(y\)를 선택하면 되므로 \(x^{r}y^{n-r}\)은 총 \(\displaystyle\binom{n}{r}\)번 나타난다. 그러므로 위의 등식이 성립한다.

이항전개식의 계수로 \(\displaystyle\binom{n}{r}\)이 나타나므로 \(\displaystyle\binom{n}{r}\)을 이항계수라고 한다.

예: 다음 등식들이 성립한다.

(1) \(n\geq0\)에 대하여 \(\displaystyle\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^{n}\)이다.

(2) \(n>0\)에 대하여 \(\displaystyle\binom{n}{0}-\binom{n}{1}+\cdots+(-1)^{n}\binom{n}{n}=0\)이다.

풀이:

(1): 이항정리에서 \(x=1,\,y=1\)인 경우이다.

(2): 이항정리에서 \(x=1,\,y=-1\)인 경우이다.

정리: 1 이상의 자연수 \(n,\,r\)에 대하여 다음의 등식이 성립한다.$$\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\cdots+\binom{n+r}{n}=\binom{n+r+1}{n+1}$$

증명: 등식 \(\displaystyle\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}\)을 반복해서 적용하면 얻을 수 있다.$$\begin{align*}\binom{n+r+1}{n+1}&=\binom{n+k}{n}+\binom{n+k}{n+1}=\binom{n+k}{n}+\binom{n+k-1}{n}+\binom{n+k-1}{n+1}\\&=\cdots\\&=\binom{n+k}{n}+\binom{n+k-1}{n}+\cdots+\binom{n+1}{n}+\binom{n+1}{n+1}\\&=\binom{n+k}{n}+\binom{n+k-1}{n}+\cdots+\binom{n+1}{n}+\binom{n}{n}\end{align*}$$

다음의 다항식$$(x_{1}+x_{1}+\cdots+x_{m})^{n}=\sum_{k_{1}+k_{2}+\cdots+k_{m}=n}{\frac{n!}{k_{1}!k_{2}!\cdots k_{m}!}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}}$$의 계수인 \(\displaystyle\frac{n!}{k_{1}!k_{2}!\cdots k_{m}!}\,(k_{1}+k_{2}+\cdots+k_{m}=n)\)를 다항계수(multinomial coefficient)라 하고, \(\displaystyle\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}\)으로 나타낸다. 다항계수 \(\displaystyle\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}\)의 의미는 \(k_{1}\)개의 \(A_{1}\), \(k_{2}\)개의 \(A_{2}\), ..., \(k_{m}\)개의 \(A_{m}\)을 일렬로 나열한 순열의 수이고, \(\displaystyle\binom{n}{k}=\binom{n}{k,\,n-k}\)이다.

정리: 다음의 등식이 성립한다.

(1) \(\displaystyle\binom{n}{k_{1},\,k_{2},\,k_{3}}=\binom{n-1}{k_{1}-1,\,k_{2},\,k_{3}}+\binom{n-1}{k_{1},\,k_{2}-1,\,k_{3}}+\binom{n-1}{k_{1},\,k_{2},\,k_{3}-1}\)

(2) \(\displaystyle\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}=\sum_{i=1}^{m}{\binom{n}{k_{1},\,\cdots,\,k_{i-1},\,k_{i}-1,\,k_{i+1},\,\cdots,\,k_{m}}}\)

증명:

(1) 3차원 좌표공간의 원점에서 출발해서 좌표축의 양의 방향으로 1단위씩 움직이는 동점이 점 \(P(k_{1},\,k_{2},\,k_{3})\)에 최단경로로 도달하는 경우의 수는 \(\displaystyle\binom{n}{k_{1},\,k_{2},\,k_{3}}=\frac{n!}{k_{1}!k_{2}!k_{3}!}\,(n=k_{1}+k_{2}+k_{3})\)이다.

그런데 점 \(P\)에 도달하기 바로 전 단계의 동점은 점 \(P_{1}(k_{1}-1,\,k_{2},\,k_{3})\), \(P_{2}(k_{1},\,k_{2}-1,\,k_{3})\), \(P_{3}(k_{1},\,k_{2},\,k_{3}-1)\)중 어느 한 점에 있고 \(P\)에 도달하기 위해서는 위의 세 점 중 어느 한점에 도달해야 하며 각각의 경로는 서로 다른 경로이므로 다음의 등식이 성립한다.$$\binom{n}{k_{1},\,k_{2},\,k_{3}}=\binom{n-1}{k_{1}-1,\,k_{2},\,k_{3}}+\binom{n-1}{k_{1},\,k_{2}-1,\,k_{3}}+\binom{n-1}{k_{1},\,k_{2},\,k_{3}}$$

(2)$$\begin{align*}\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}&=\frac{k_{1}+k_{2}+\cdots+k_{m}}{n}\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}\\&=\sum_{i=1}^{m}{\frac{k_{i}}{n}\binom{n}{k_{1},\,k_{2},\,\cdots,\,k_{m}}}\\&=\sum_{i=1}^{m}{\binom{n-1}{k_{1},\,\cdots,\,k_{i-1},\,k_{i}-1,\,k_{i+1},\,\cdots,\,k_{m}}}\end{align*}$$또는 (1)을 반복해서 얻을 수 있다.

참고자료:

조합론과 그래프이론, 조성진, 김한두, 경문사

조합 및 그래프이론, 김정진, 교우사