같은 종류를 여러 번 고를 수 있는 선택(중복조합)과, 자연수를 더 작은 자연수의 합으로 나누는 방법(분할)을 다룬다. 사탕 나누기, 방정식의 정수해 세기가 모두 중복조합이다.
핵심 개념
- 중복조합: 서로 다른 $n$종류에서 중복을 허락하여 $r$개를 고르는 방법 ${}_nH_r={}_{n+r-1}C_r$
- 방정식의 해: $x_1+\cdots+x_n=r$의 음이 아닌 정수해의 개수 ${}_nH_r$, 자연수해의 개수 ${}_nH_{r-n}={}_{r-1}C_{n-1}$
- 자연수의 분할 $p(n)$: $n$을 순서를 생각하지 않고 자연수의 합으로 나타내는 방법의 수. $p(4)=5$: $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$
- 집합의 분할: 원소가 $n$개인 집합을 공집합이 아닌 $k$개의 부분집합으로 나누는 방법 $S(n,k)$ (제2종 스털링 수)
핵심 정리
${}_nH_r={}_{n+r-1}C_r$
증명 보기 (별과 막대)
$x_1+x_2+\cdots+x_n=r$ ($x_i\ge0$)의 해를 센다. $r$개의 별을 일렬로 놓고 그 사이에 $n-1$개의 막대를 끼워 $n$개의 묶음으로 나누면, 각 묶음의 별의 수가 $x_1,\dots,x_n$이 된다. 예: ★★|★|★★★| $\to(2,1,3,0)$. 거꾸로 모든 해는 이런 배열 하나에 대응하므로 일대일대응이다. 배열은 별과 막대 $n+r-1$개의 자리 중 별의 자리 $r$개를 고르는 것이므로 ${}_{n+r-1}C_r$가지이다.
자연수해는 각 $x_i$에 먼저 $1$씩 주고 남은 $r-n$개를 나누는 것과 같으므로 ${}_nH_{r-n}$이다. $\blacksquare$
예제
- 사과, 배, 감 중에서 $5$개를 사는 방법: ${}_3H_5={}_7C_5=21$
- $x+y+z=10$의 자연수해: ${}_3H_7={}_9C_7=36$
- $(a+b+c)^4$의 전개식의 서로 다른 항의 수: ${}_3H_4={}_6C_4=15$
확인 문제
$x+y+z\le5$를 만족하는 음이 아닌 정수 $(x,y,z)$의 개수를 구하시오.
풀이 보기
남는 양 $w=5-(x+y+z)\ge0$을 새 변수로 두면 $x+y+z+w=5$의 음이 아닌 정수해와 같다. ${}_4H_5={}_8C_5=56$이다.
정리
- 중복조합 ${}_nH_r={}_{n+r-1}C_r$ (별과 막대)
- 부등식은 여분 변수를 더해 등식으로 바꾼다.
