조합과 순열

조합과 순열 (Combination & Permutation)

조합의 정의

조합은 전체 집합중에서 일정한 수의 부분집합을 선택하는 방법의 수로 그 순서는 고려하지 않습니다. 다음과 같이 나타내지요.

$\left(\begin{array}{r}n\\ p\end{array}\right)$ or $C_n^p$ 로 표현합니다.

위의 의미는 전체 n 원소들로 이루어진 집합에서 p개의 일부 원소들 취해 부분집합을 만드는 방법으로 위의 표현은 $n^p$로 계산됩니다.

2진법으로 6자리를 만드는 방법의 수는 다음과 같이 계산됩니다.

$\left(\begin{array}{r}2\\ 6\end{array}\right)=2^6$

모든 자리에 0, 1 중의 하나를 선택하고 이러한 경우가 6번이므로 $2 \times 2 \times 2 \times 2 \times 2 \times 2$이 됩니다. 위와 같은 결과이지요.

{a, b, c, d, e} 중에서 서로 다른 세개만을 선택하는 방법을 생각해보면 먼저 a를 선택한 후 나머지를 선택하는 방법은 다음과 같이 12가지가 됩니다.

a	b	c
		d
		e
	c	b
		d
		e
	d	b
		c
		e
	e	b
		c
		d

먼저 취한 값이 a외에 4가지가 더 존재합니다. 총 5가지이요. 그러므로 위와 같이 선택할 수 있는 방법은 총 $5 \times 12$= 60가지 입니다. 이 계산은 첫자리에 올수 있는 갯수는 5, 두번째 자리에 올수 있는 갯수는 4개 마지막 자리에 올수 있는 갯수는 3개로 $5\times 4\times \3$=60으로 계산할 수 있습니다.

이와같이 정렬의 순서를 고려하는 경우에서의 선택의 방법을 순열(permutation)이라고 합니다.

순열의 정의

전체 집합에서 순서를 고려하여 만들 수 있는 부분집합의 수로서 다음과 같이 나타냅니다.

$A_n^P=n(n-1)(n-2)\cdots (n-p+1)$

위의 경우에서 순서를 고려하지 않는다면 선택할 수 있는 경우의 수는 어떻게 될까요? 위의 순열의 결과 중에서 중복되는 부분을 제외하면 abc, abd, ade, acd, ace, ade, bcd, bce, bde, cde로 총 10가지가 됩니다. 이 과정을 일반화하여 조합을 다음과 같이 정의할 수 있습니다.

조합의 정의

$C_n^p=\frac{n(n-1)(n-2)\cdots (n-p+1)}{p!}=\frac{n!}{p!(n-p)!}$

조합공식은 다음과 같이 나타낼 수 있습니다.

$C_n^p=C_n^{n-p}$

$C_n^p=C_{n-1}^{p-1}+C_{n-1}^p$

위 조합 공식으로 다항식(a+b)^n을 나타낼 수 있습니다.

$(a+b{)}^2=1a^2+2ab+1b^2=C_2^0{a}^2{b}^0+C_2^1{a}^1{b}^1+C_2^2{a}^0{b}^2$

위 식을 일반화 하면 다음과 같습니다.

$(a+b{)}^n=\sum _{k=0}^n{C}_n^k{a}^{n-k}{b}^k$