중복조합의 공식 H(n,r) =C(n+r-1,r)

중복조합
- 주어진 집합의 원소 중에서 뽑되 동일한 원소의 중복을 허용하여 뽑아내는 것
- 1과 2에서 세 개를 취하는 중복조합은 111, 112, 122, 222의 네 가지가 있음.
n개 중에서 r개를 선택하는 중복조합의 개수를 $_n H_r=\textstyle\left\langle{n\atop r}\right\rangle$ 로 나타낸다.

증명의 아이디어를 이해하기 위해, H(4,2)의 예를 들어보자
1,2,3,4 중에서 뽑는 것으로 하면, 중복해서 두 개를 뽑는 방법은 다음과 같이 열 가지가 있음.
- 11,12,13,14,22,23,24,33,34,44
이제 이 중복조합에서 첫번째 것은 내버려 두고, 두번째 수에 1을 더하면 다음과 같은 결과를 얻음.
- 12,13,14,15,23,24,25,34,35,45
- 이것은 1부터 5까지 중에서 2개를 선택하는 방법과 같아짐.
그러므로, H(4,2)=C(5,2)

또다른 예. H(2,3)의 계산.
1,2 중에서 세 가지를 택하는 중복조합은 다음과 같음.
- 111,112,122,222
위에서 한 것처럼 첫번째 것은 내버려 두고, 두번째 것에 1, 세번째 것에 2를 더해 보면, 다음을 얻게 됨
- 123,124,134,234
- 이 경우는 1,2,3,4 중에서 세 개를 뽑는 조합과 일치함.
그러므로, H(2,3)=C(4,3)

n=4, r=18 인 경우
집합을 $\{a,b,c,d\}$ 로 두자.
a가 6개, b가 2개, c가 3개, d가 7개 있는 경우를 아래처럼 나타내자.

$\{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d \}$

$\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet$
그림에서 점과 막대를 다 합하여 총 4+18-1=21 개가 있는데, 이 21개의 위치에서 18개를 선택하여 a,b,c,d를 배열하는 중복조합과 일대일대응된다.

생성함수
{ {}, {x}, {x,x}, {x,x,x}, ... } gives S = 1 + x + x2 + x3 + ... = 1 + xS which is formally S=1/(1-x)
(1 − x)⁻¹·(1 − y)⁻¹ = 1 + (x + y) + (x² + x·y + y²) +(x³ + x²·y + xy²+y³)+...
(1 − x)⁻² = 1 + (x + x) + (x² + x·x + x²) + ...
n개의 원소에서 k개를 뽑는 중복조합의 생성함수는 다음과 같이 주어진다

$\frac{1}{(1-x)^n}=\sum_{k=0}^{\infty}\textstyle\left\langle{n\atop k}\right\rangle x^k$

$=\sum_{k=0}^{\infty}\frac{(n)_k}{k!}x^k=1+nx+\frac{n(n+1)}{2!}x^2+\frac{n(n+1)(n+2)}{3!}x^3+\cdots$

자연수 r에 대하여, 다음 부정방정식의 $x_i \geq 0$ 인 정수해의 개수를 구해보자

$x_0+x_1+x_2+\cdots+x_n=r$
해의 개수는 n+1개의 원소를 가지고 r개를 뽑는 중복조합의 수와 같다. 즉, 해의 개수는 다음과 같다

$_{n+1} H_r=_{n+r}C_{r}=_{n+r}C_{n}$
프로베니우스 디오판투스 방정식

$\sum_{k}\left\langle \begin{matrix} 3 \\ 4 \end{matrix} \right\rangle x^k$

$\sum_{k} \textstyle\left\langle{n\atop k}\right\rangle x^k$

단어사전 http://www.google.com/dictionary?langpair=en|ko&q=
발음사전 http://www.forvo.com/search/
대한수학회 수학 학술 용어집
- http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
남·북한수학용어비교
대한수학회 수학용어한글화 게시판