Mental Plex

Loading

조합과 중복조합의 공식과 증명

조합

조합은 집합에서 일부 원소로 부분집합을 만드는 것을 말한다. 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

댓글 쓰기

모든 문서는 CC-BY-SA에 따라 사용할 수 있습니다.