조합
조합은 집합에서 일부 원소로 부분집합을 만드는 것을 말한다. n개의 원소를 가지는 집합에서 r개의 부분집합을 고르는 조합의 경우의 수를 이항 계수라 하고, 기호로 \({_{n}}{C}_{r}\), \(C(n, r)\), 또는 \(\begin{pmatrix} n \\ r \end{pmatrix}\)로 나타낸다.조합의 성질
(1) \({_{n}}{C}_{r}={_{n}}{C}_{n-r}\)(2) \({_{n}}{C}_{r}={_{n-1}}{C}_{r-1}+{_{n-1}}{C}_{r}\)
논리적 증명
(1) n명 중 A라는 그룹에 들어갈 사람을 뽑는 경우의 수는 n명 중 A라는 그룹에 들어가지 않을 n-r명을 뽑는 경우의 수와 같다.(2) n명 중 A라는 그룹에 들어갈 사람을 결정할 때, n명 중 특정한 한명 M이라는 사람을 중심으로 결정한다면, M이라는 사람이 A라는 그룹에 무조건 포함 되는 경우와 M이라는 사람이 A라는 그룹에 무조건 포함되지 않는 경우로 나눌 수 있다. 일단 M이라는 사람은 그룹에 포함될지의 여부가 결정되어 있으므로 M을 뺀 나머지 n-1명 중 M이 A라는 그룹에 무조건 포함되는 경우, M을 뺀 나머지 r-1명 뽑을 것이고, M이 A라는 그룹에 무조건 포함되지 않는 경우 A라는 그룹에 들어갈 r명을 뽑을 것이다.
중복조합
중복조합은 서로 다른 n개의 원소 중에서 중복을 허락하여 r개를 뽑는 경우의 수를 말하고, 기호로 \({_{n}}{H}_{r}\)이라 나타낸다. 중복조합의 수는 \({_{n}}{H}_{r}={_{n+r-1}}{C}_{r}\)로 계산한다.중복조합의 공식 유도
중복조합 \({_{n}}{H}_{r}\)은 r개의 원소들을 순서에 상관없이 나열하는 것이므로, r개의 빈칸에 중복을 허용하여 n개의 원소를 넣는 경우의 수를 계산하는 문제와 같다. 여기에 n 가지의 경우로 구분할 수 있는 원소들을 순서에 상관없이 구분해야 하므로, n-1 개의 칸막이를 두고 n 가지 경우를 임의의 순서로 배열한다고 할 수 있다. 예를 들어 칸막이 기호를 /로 나타낸다면, 원소 A, B, C를 중복하여 5개를 뽑는 경우 중 " A A A B C "는 " A A A / B / C ", " B B B C C "는 " / B B B / C C "로 구분하는 것이다. 즉, 중복조합은 r개의 빈칸과 칸막이의 수 n-1개를 합한 r+n-1개의 빈칸에 칸막이가 들어갈 n-1개의 칸을 선택하면 된다. 결국 중복조합 \({_n}{H}{_r}\)은 \({_{n+r-1}}{C}{_{n-1}}\)이 된다. 따라서 \({_n}{C}{_r} = {_n}{C}{_{n-r}}\) 이므로 \({_n}{H}{_r}= {_{n+r-1}}{C}{_r}\)이 된다.참조
위키백과Loading
댓글 쓰기