조합과 순열

조합과 순열 (Combination & Permutation)

조합의 정의

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

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

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

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

$\left( \begin{array}{rr} 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^P_n = n(n-1)(n-2)\cdots (n-p+1)$

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

조합의 정의

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

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

$C^p_n = C^{n-p}_n$

$C^p_n=C^{p-1}_{n-1} + C^p_{n-1}$

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

$(a+b)^2 = 1a^2 + 2ab + 1b^2 =C^0_2 a^2 b^0 + C^1_2 a^1b^1 +C^2_2 a^0b^2$

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

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