이항계수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

자연수 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)n을 전개했을 때, 각 항의 계수에 해당한다(그래서 이항계수란 이름이 붙었다).

 (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)n (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에 대한 귀납법으로 보일 수 있다.

같이 보기[편집]

바깥 고리[편집]