이항계수

자연수 n과 정수 k에 대한 이항계수(二項係數, 영어: binomial coefficient)는 n개의 서로 다른 물건 중에서 순서 없이 k개를 뽑는 조합의 가짓수로, 다음과 같이 정의된다.

${n \choose k} = \frac{n!}{k!(n-k)!} \quad \mbox{if } n\geq k\geq 0 \qquad \mbox{(1)}$

${n \choose k} = 0 \quad \mbox{if } k<0 \mbox{ or } k>n$

이때 ${n \choose k}$ 대신 ${_n}C{_k}$, $C(n, k)$로 쓰기도 한다.

예를 들어,

${7 \choose 3} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35$

가 된다.

이항계수는 (x+y)ⁿ을 전개했을 때, 각 항의 계수에 해당한다(그래서 이항계수란 이름이 붙었다).

$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k} \qquad (2)$

이항계수의 성질

$C(n,k) + C(n,k+1) = C(n+1,k+1) \qquad (3)$

위 점화식은 이항계수의 정의에서 유도할 수 있다. 이 식을 이용하여 파스칼의 삼각형을 만들 수 있다.

${n \choose k}={n \choose {n-k}} \qquad (4)$

이 식의 증명은 ${n \choose {n-k}} = \frac{n!}{(n-k)!(n-(n-k))!} = \frac{n!}{(n-k)!k!} = {n \choose k}$와 같이 할 수 있다.

$\sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n \qquad (5)$

(2)번 식에 x = y = 1을 대입하여 보일 수 있다.

$\sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} \qquad (6)$

위 식은 (2) 식을 전개한 후, 양변을 미분하고 x = y = 1을 대입하면 보일 수 있다.

$\sum_{j=0}^{k} \mathrm{C}(m,j) \mathrm{C}(n,k-j) = \mathrm{C}(m+n,k) \qquad (7)$

(x + y)ⁿ (x + y)^m = (x + y)^m+n 식을 (2)를 이용하여 전개하면 된다. (3)번 식의 일반식이다.

$\sum_{k=0}^{n} \mathrm{C}(n,k)^2 = \mathrm{C}(2n,n) \qquad (8)$

(7)번 식을m = k = n와 (4)를 이용하여 정리하면 된다.

$\sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1) \qquad (9)$

F(n + 1)은 피보나치 수를 나타낸다. 이 식은 파스칼의 삼각형의 대각선에 대한 식으로 (3)을 이용하여 귀납법으로 보일 수 있다.

$\sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1) \qquad (10)$

(3)을 이용하여 n에 대한 귀납법으로 보일 수 있다.

바깥 고리

• Binomial Coefficient -- from MathWorld