$\def\com#1#2{ {#1 \atopwithdelims () #2 }}$

표기법: 조합

조합을 의미하는 Combination 을 다음과 같이 괄호를 써서 위아래로 표기하고, 이항 계수라 부른다.
의미는 똑같지만 $aCb$ 는 $a \times C \times b$ 로 착각하기 좋은 모양이라 $\com{a}{b}$ 를 선호한다.

$\begin{align} a C b & = \com{a}{b} \\ 3 C 2 & = \com{3}{2} = 3 \\ \end{align}$

이항 정리

Binomial Theorem

$\begin{align} (x+y)^n & = \sum_{j=0}^n \com{n}{j} x^{n-j} y^j \\ & = \com{n}{0} x^{n} y^0 + \com{n}{1} x^{n-1} y^1 + ... + \com{n}{n-1} x^{1} y^{n-1} + \com{n}{n} x^{0} y^{n} \\ \end{align}$

중학교 때 배운 곱셈 공식을 생각해 볼 수 있을 것이다.

$(a+b)^2 = a^2 + 2ab + b^2$

이 등식의 계수는 왜 $1, 2, 1$ 이 될까?

식을 전개하는 과정이 a와 b가 들어있는 주머니에서 중복을 무시하고 2번 꺼내서 나열하는 것과 같기 때문이다.

$\begin{array}{rlllllllll} (a+b)^2 & = & a^2 & + & 2ab & + & b^2 \\ & & aa & & ab & & bb \\ & & & & bb & & \\ \end{array}$

$(a+b)^3$ 형태도 마찬가지다.

$\begin{array}{rlllllllll} (a+b)^3 & = & a^3 & + & 3a^2b & + & 3ab^2 & + & b^3 \\ & & aaa & & aab & & bba & & bbb \\ & & & & aba & & bab & & \\ & & & & baa & & abb & & \\ \end{array}$

즉, $(a+b)^n$ 형태의 각 항의 계수는 조합 $\com{n}{k}$ 형태로 표현할 수 있다.

따름 정리 1

n 이 음이 아닌 정수라면 다음이 성립한다.

$\sum_{k=0}^n \com{n}{k} = 2^n$

왜냐하면 $(1+1)^n$ 과 같은 형태이기 때문이다.

$\begin{align} (1+1)^n & = \sum_{k=0}^n \com{n}{k} 1^k 1^{n-k} \\ & = \sum_{k=0}^n \com{n}{k} \\ \end{align}$

따름 정리 2

n 이 음이 아닌 정수라면 다음이 성립한다.

$\sum_{k=0}^n (-1)^k \com{n}{k} = 0$

왜냐하면 $(-1 + 1)^n$ 과 같은 형태이기 때문이다.

$\begin{align} (-1 + 1)^n & = \sum_{k=0}^n \com{n}{k} (-1)^k 1^{n-k} \\ 0^n & = \sum_{k=0}^n \com{n}{k} (-1)^k \\ \end{align}$

따름 정리 3

n 이 음이 아닌 정수라면 다음이 성립한다.

$\sum_{k=0}^n 2^k \com{n}{k} = 3^n$

왜냐하면 $(1 + 2)^n$ 과 같은 형태이기 때문이다.

$\begin{align} (1 + 2)^n & = \sum_{k=0}^n \com{n}{k} 1^{n-k} 2^{k} \\ 3^n & = \sum_{k=0}^n \com{n}{k} 2^{k} \\ \end{align}$

파스칼의 항등식

Pascal’s Identity

$n, k$ 가 양의 정수이고, $n \ge k$ 라면 다음이 성립한다.
$\com{n+1}{k} = \com{n}{k-1} + \com{n}{k}$

주머니 하나에 여러 색깔의 구슬 $n+1$ 개가 들어 있다고 하자.

만약 이 주머니에서 $k$ 개의 구슬을 순서 상관없이 골라낸다고 하면 경우의 수는 $\com{n+1}{k}$ 가 될 것이다.

그런데 이 경우의 수를 두 경우로 분할해서 생각할 수 있다.

빨간 구슬 한 개를 골라놓고 $k-1$ 개를 골라내는 경우. $\com{n}{k-1}$
빨간 구슬을 제외하고 $k$ 개를 골라내는 경우. $\com{n}{k}$

따라서 다음과 같이 정리할 수 있다.

$\com{n+1}{k} = \com{n}{k-1} + \com{n}{k}$

그냥 식을 정리해서 증명하는 방법도 있다.

$\begin{align} \com{n+1}{k} & = \com{n}{k-1} + \com{n}{k}\\ & = { n! \over (k-1)! (n-k+1)!} + { n! \over k!(n-k)! } \\ & = { n!k \over k! (n-k+1)!} + { n!(n-k+1) \over k!(n-k+1)! } \\ & = { n!k + n!(n-k+1) \over k!(n-k+1)! } \\ & = { n! (k + n-k+1) \over k!(n-k+1)! } \\ & = { n! (n+1) \over k!(n-k+1)! } \\ & = { (n+1)! \over k!(n+1-k)! } \\ \end{align}$

파스칼의 삼각형

Pascal’s Triangle

각 $n$ 번째 행을 $\com{n}{0} ... \com{n}{n}$ 으로 나열하고 삼각형 모양으로 정렬한 것을 파스칼의 삼각형이라 한다.

$\begin{array}{ccccccccccccccccccccccccc} & & & \com{0}{0} \\ & & \com{1}{0} & & \com{1}{1} \\ & \com{2}{0} & & \com{2}{1} & & \com{2}{2}\\ \com{3}{0} & & \com{3}{1} & & \com{3}{2} & & \com{3}{3} \\ & & & ... \\ \end{array}$

각 조합을 계산해보면 다음과 같은 자연수의 삼각형이 나오는데, 각 행은 행 번호에 해당하는 이항계수들의 리스트가 된다.

$\begin{array}{ccccccccccccccccccccccccc} & & & & & 1 & \\ & & & & 1 & & 1 & \\ & & & 1 & & 2 & & 1 & & \\ & & 1 & & 3 & & 3 & & 1 & \\ & 1 & & 4 & & 6 & & 4 & & 1 \\ & & & & & ... & \\ \end{array}$

잘 살펴보면 한 줄의 아이템 하나와 바로 위의 대각선 양쪽 아이템들이 파스칼의 항등식을 보여주고 있음을 알 수 있다.

즉, 다음 행의 특정 값을 구하고 싶으면 조합식을 계산하지 않고 위쪽의 양쪽 대각선의 합을 구해도 된다.

참고문헌

Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일