이항계수(Binomial coefficient)

정의1

임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 $n ! = 1\cdot 2 \cdot 3 \cdots (n-1)\cdot n$인

$1$에서 $n$까지의 곱을 $n$의 계승 또는 팩토리얼(factorial)이라 정의한다.

$0$의 팩토리얼은 $0! = 1$로 정의된다.

 

 

 

정의2

$n \ge  k \ge 0 $인 모든 자연수 $n,k \in \mathbb{N}$에 대해 $  \dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$를 이항 계수로 정의한다.

 

 

 

정리1(파스칼[Pascal] 항등식)

$n \ge  k \ge 1$인 모든 양의 정수 $n,k \in \mathbb{Z}^+$에 대해 $\dbinom{n+1}{k} = \dbinom{n}{k-1}+\dbinom{n}{k}$이다.

증명

$n \ge  k \ge 1$이므로 $k -1 \ge 0$이고 $n- k +1 \ge 1$이 되어

$\begin{align*} \dbinom{n}{k-1}+\dbinom{n}{k} &= \dfrac{n!}{(k-1)!(n - (k-1))!} + \dfrac{n!}{k!(n-k)!} \\[0.5em] &=   \dfrac{n!\cdot k}{k \cdot (k-1)!(n - k+1)!} + \dfrac{n! \cdot (n-k+1)}{k!(n-k )!(n-k+1)} \\[0.5em] &=  \dfrac{n!}{k!(n - k+1)!}\cdot k + \dfrac{n! }{k!(n-k+1)!} \cdot (n-k+1) \\[0.5em] &= \dfrac{n!}{k!(n - k+1)!}\cdot (k + n- k+1) \\[0.5em] &= \dfrac{n! \cdot (n+1)}{k!(n - k+1)!} \\[0.5em] &= \dfrac{(n+1)!}{k!((n +1)- k)!} \\[0.5em] &= \dbinom{n+1}{k} \text { 이다.} \end{align*}$

 

 

 

정리2(이항 정리)

모든 자연수 $n \in \mathbb{N}$과 임의의 복소수 $x,y \in \mathbb{C}$에 대해 

$\begin{align*} (x + y)^n &= \sum_{k = 0}^{n} \dbinom{n}{k} x^{n-k}y^k  = \dbinom{n}{0}x^n + \dbinom{n}{1}x^{n-1}y + \cdots + \dbinom{n}{n-1}xy^{n-1} + \dbinom{n}{n}y^n \text{  이다.} \end{align*} $

증명

$n = 0$이면 $(x +y)^0 = 1 =  \dbinom{0}{0}x^{0 - 0}y^0 =  { \displaystyle \sum_{k = 0}^{0}} \dbinom{0}{k} x^{0-k}y^k $이다.

$n\ge 1$인 $n \in \mathbb{N}$에 대한 귀납법을 사용한다.

$n = 1$이면 

$\begin{align*} (x + y)^1 &= x+y \\[0.5em] &= \dfrac{1!}{0!(1-0)!}x^{1-0}y^0 + \dfrac{1!}{1!(1-1)!}x^{1-1}y^1 \\[0.5em] &= {\displaystyle \sum_{k = 0}^{1}} \dbinom{1}{k} x^{1-k}y^k \quad \text{로 성립한다.} \end{align*} $

$m \ge 1$인 모든 $m \in \mathbb{N}$에 대해 $(x + y)^m= {\displaystyle \sum_{k = 0}^{m} } \dbinom{m}{k} x^{m-k}y^k  $가 성립한다고 가정하면 

$m > k \ge1$일때 파스칼 항등식을 사용하여 $\dbinom{m}{k} + \dbinom{m}{k-1} = \dbinom{m+1}{k}$이고 

이항계수 정의에 따라 $\dbinom{m}{0} = 1=\dbinom{m+1}{0}$이고 $\dbinom{m}{m} = 1=\dbinom{m+1}{m+1}$이므로

$\begin{align*}  (x + y)^{m+1} &= (x + y)\cdot (x + y)^m \\[0.5em] &= (x + y)\cdot \left ( \sum_{k = 0}^{m}  { \binom{m}{k}x^{m-k} } y^k \right  ) \\[0.5em] &= \sum_{k = 0}^{m} { \binom{m}{k}} x^{m -k+1}y^k + \sum_{k = 0}^{m} { \binom{m}{k}} x^{m-k}y^{k+1} \\[0.5em] &= \left ( \sum_{k = 1}^{m} { \binom{m}{k}} x^{m-k+1}y^k + { \binom{m}{0}x^{m-0+1} } y^0 \ \right ) +\left( \sum_{k=1}^{m+1} { \binom{m}{k-1} } x^{m-(k-1)}y^k  \right ) \\[0.5em] &= { \binom{m}{0}x^{m+1} }+ \sum_{k=1}^{m} { \binom{m}{k} } x^{(m+1) -k}y^k + \sum_{k= 1}^{m} {\binom{m}{k-1} } x^{m-(k-1)}y^k + { \binom{m}{(m+1)-1} } x^{m-(m+1-1)}y^{m+1}  \\[0.5em] &= { \binom{m}{0} } x^{m+1} +  \sum_{k=1}^{m} ({ \binom{m}{k} + \binom{m}{k-1} }) x^{(m+1) -k}y^k + { \binom{m}{m} } y^{m+1}  \\[0.5em] &=  {\binom{m+1}{0} } x^{m+1} +  \sum_{k=1}^{m} { \binom{m+1}{k} } x^{(m+1) -k}y^k + { \binom{m+1}{m+1} } y^{m+1} \\[0.5em] &=  \sum_{k=0}^{m+1} { \binom{m+1}{k} } x^{(m+1) -k}y^k \quad \text{이다.}  \end{align*}$

따라서 모든 $n \in \mathbb{N} $에 대해 $(x + y)^n = {\displaystyle \sum_{k = 0}^{n} \binom{n}{k} } x^{n-k}y^k $이다.

 

 

 

정리3

$n \ge r \ge 0$인 모든 자연수 $n,r \in \mathbb{N}$에 대해 ${\displaystyle \binom{n+1}{r+1} = \sum_{j=r}^{n} \binom{j}{r}}$이다.

증명

$n = 0$이면 $r = 0$이므로 $\displaystyle \binom{0+1}{0+1}  = \binom{1}{1} = \binom{0}{0} = \sum_{j=0}^{0} \binom{j}{r}$이다.

$n \ge 1$인 $n \in \mathbb{N}$에 대해서는 귀납법을 사용한다.

$n = 1$일때

$r = 0$이면 $\displaystyle \binom{1+1}{0+1} = \binom{2}{1} = \frac{2!}{1!\cdot (2-1)!} = 2 = 1 +1 = \binom{0}{0} + \binom{1}{0} = \sum_{j=0}^{1} \binom{j}{0}  $이고

$r = 1$이면 $\displaystyle \binom{1+1}{1+1} = \binom{2}{2} = \frac{2!}{2!\cdot (2-2)!} = 1 =  \binom{1}{1} = \sum_{j=1}^{1} \binom{j}{1}  $이다.

$k \ge 1$일때 $k \ge r \ge 0$인 모든 $k,r \in \mathbb{N}$에 대해 ${\displaystyle \binom{k+1}{r+1} = \sum_{j=r}^{k} \binom{j}{r}}$이라고 가정하면

파스칼 항등식과 귀납가정으로

$r > 0$일때 

$\begin{align*}  \binom{(k+1)+1}{r+1} & = \binom{k+2}{r+1} \\[0.5em] & = \binom{k+1}{r} +\binom{k+1}{r+1} \\[0.5em] & = \sum_{j = r-1}^k \binom{j}{r-1} + \sum_{j = r}^k \binom{j}{r} \\[0.5em] & = \binom{r-1}{r-1} + \sum_{j =r}^k \binom{j}{r-1} + \sum_{j=r}^k \binom{j}{r} \\[0.5em] & = \binom{r}{r} + \sum_{j=r}^k \left (\binom{j}{r-1} +\binom{j}{r} \right ) \\[0.5em] & = \binom{r}{r} + \sum_{j=r}^k \binom{j+1}{r} \\[0.5em] & = \binom{r}{r} + \sum_{j=r+1}^{k+1} \binom{j}{r} \\[0.5em] & = \sum_{j=r}^{k+1} \binom{j}{r} \text{ 이고}\end{align*}$ 

$r = 0$일땐

$\begin{align*}  \binom{(k+1)+1}{0+1} & = \binom{k+2}{1} \\[0.5em] & = \binom{k+1}{0} +\binom{k+1}{1} \\[0.5em] & = \binom{k+1}{0} + \sum_{j = 0}^k \binom{j}{0} \\[0.5em] & = \sum_{j = 0}^{k+1} \binom{j}{0} \text{ 이다.} \end{align*}$ 

따라서 $n \ge r \ge 0$인 모든 $n,r \in \mathbb{N}$에 대해 ${\displaystyle \binom{n+1}{r+1} = \sum_{j=r}^{n} \binom{j}{r}}$이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/16#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/16#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Kenneth H. Rosen - Discrete mathematics and its applications - 9791132102229