이항 계수

[섬네일|right|이항 계수의 표를 [파스칼의 삼각형이라고 한다.]]
조합론에서 **이항 계수**(二項係數, )는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

## 정의
자연수 n 및 정수 k가 주어졌을 때, **이항 계수** \textstyle\binom nk는 다음과 같다.
:\binom nk=\begin{cases}
n!/\left(k!(n-k)!\right)&0\le k\le n\\
0&kn
\end{cases}
여기서 !는 계승 (수학)이다. 이항 계수를 \textstyle\binom nk 대신 {}_nC_k나 C(n, k)로 쓰기도 한다. 이항 계수의 값을 삼각형 모양으로 나열한 표를 **[[파스칼의 삼각형]]**이라고 한다.

n=2k인 경우의 이항 계수를 **중심 이항 계수**(中心二項係數, )라고 한다. 이는 다음과 같다 (k=0,1,2,\dots).
:1, 2, 6, 20, 70, 252, 924, 432, 12870, 48620, … 

## 성질
### 항등식
이항 계수는 다음과 같은 항등식을 만족시킨다. 이는 이항 계수의 정의로부터 쉽게 증명할 수 있다.
:\binom nk=\binom n{n-k}
다음과 같은 점화식이 성립하며, 이는 **파스칼의 법칙**(Pascal-法則, )이라고 한다.
:\binom nk+\binom n{k+1}=\binom{n+1}{k+1}

### 급수 공식
이항 계수는 다음과 같은 급수 공식들을 만족시킨다. 이들은 대부분 생성 함수(의 도함수)의 특수한 값으로 얻어진다.

#### 이항 계수의 합
이 공식들은 생성함수 (1+x)^n(의 도함수)의 x=1 값으로부터 유도할 수 있다.
:\sum_{k=0}^n\binom nk=2^n
:\sum_{k=0}^nk\binom nk=n2^{n-1}
또한, 피보나치 수를 다음과 같이 나타낼 수 있다.
: \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}k =F(n+1)
여기서 F(n)은 n번째 피보나치 수이다.

#### 이항 계수의 곱의 합
다음 항등식은 **[[주세걸]]-[[알렉상드르테오필 방데르몽드|방데르몽드]] 항등식**(朱世傑-Vandermonde恒等式, )이라고 한다.
: \sum_{j=0}^k\binom mj\binom n{k-j}=\binom{m+n}k
이항계수의 제곱의 합은 다음과 같이 중심 이항 계수로 주어진다.
: \sum_{k=0}^{n} \binom nk^2 =\binom{2n}n
이는 조합론적으로 증명할 수 있다. \textstyle\binom{2n}n은 크기가 2n 집합 속에서 n개의 조합의 가짓수인데, 이는 크기 2n의 집합의 처음 절반에서 k개를 고르고, 나머지 절반에서 n-k개를 고르는 가짓수의 k에 대한 합 \textstyle\sum_{k=0}^n\binom nk\binom n{n-k}=\sum_{k=0}^n\binom nk^2과 같다.

### 생성 함수
이항 계수는 다음과 같은 생성 함수를 갖는다.
:\sum_{k=0}^n\binom nkx^k=(1+x)^n
:\sum_{n=k}^\infty\binom nkx^n = \frac{x^k}{(1-x)^{k+1}}
:\sum_{n=0}^\infty\sum_{k=0}^n\binom nkx^k y^n = \frac1{1-y-xy}
:\sum_{n=0}^\infty\sum_{k=0}^n\frac1{(n+k)!}\binom{n+k}kx^k y^n =\exp(x+y)

중심 이항 계수의 생성 함수는 다음과 같다.
:\sum_{n=0}^\infty\binom{2n}nx^n=\frac1{\sqrt{1-4x}}

### 점근 공식
일반적으로, 모든 n\in\mathbb N 및 k\in\{1,\dots,n\}에 대하여, 다음과 같은 부등식이 성립한다.
:(n/k)^k\le\binom nk\le n^k/k!\le(en/k)^k
중심 이항 계수의 경우 다음 부등식이 성립한다.
:\frac{4^n}{\sqrt{4n}} \le \binom{2n}n \le \frac{4^n}{\sqrt{3n+1}}\qquad\forall n\ge1

n\gg1 및 |1/2-k/n|\ll1에 대하여, 스털링 근사를 사용하여 이항계수를 다음과 같이 근사할 수 있다.
:\binom nk\approx\frac{2^{n+1}}{\sqrt{2\pi n}}\exp(-(2k-n)^2/2n)
이에 따라, 이항분포를 정규분포로 근사할 수 있다. 특히, k=n/2일 경우 중심 이항 계수의 스털링 근사는 다음과 같다.
:\binom n{n/2}\approx \frac{2^{n+1}}{\sqrt{2\pi n}}
이다.

만약 n\gg1이며 n\gg k라면, 스털링 근사를 사용하여 이항 계수를 다음과 같이 근사할 수 있다.
:\binom nk\sim\frac{(n/k-1/2)^k\exp(k)}{\sqrt{2\pi k}}

### 수론적 성질
**쿠머 정리**(Kummer定理, )에 따르면, 음이 아닌 정수 n\ge k 및 소수 p에 대하여,
:p^c \mid \binom nk
인 최대 c는 다음과 같다.
:c=|\{b\in\mathbb Z^+\colon k/p^b-\lfloor k/p^b\rfloor>n/p^b-\lfloor n/p^b\rfloor\}|
즉, 이는 k+(n-k)를 p진법에서 계산할 때 받아올림의 수와 같다.

**[[뤼카의 정리]]**는 이항계수의 소수에 대한 나머지의 값을 제시한다.

중심 이항 계수 \textstyle\binom{2n}n은 n>4에 대하여 항상 제곱 인수가 없는 정수이다. 이를 **에르되시 추측**(Erdős推測, )라고 한다. 에르되시 팔이 1980년에 추측하였고, 앤드루 그랜빌()과 올리비에 라마레()가 1996년에 증명하였다.

임의의 양의 정수 d\in\mathbb Z^+에 대하여, 다음이 성립한다.
:\lim_{N\to\infty}\frac{\left|\{n
\textstyle N(N+1)/2=\sum_{n=0}^{N-1}\sum_{k=0}^n1은 n인 이항계수 \textstyle\binom nk의 수이므로, 임의의 양의 정수는 거의 모든 이항계수를 약수로 가진다. 이는 데이비드 싱매스터()가 1974년에 증명하였다.

### 초한 이항 계수
이항 계수의 정의는 임의의 기수에 대하여 확장할 수 있다. 임의의 기수 \kappa,\lambda에 대하여, **초한 이항 계수**(超限二項係數, )
:\binom\kappa\lambda
는 크기가 \kappa인 집합의, 크기가 \lambda인 부분 집합들의 수이다. 만약 \kappa와 \lambda가 둘 다 유한 기수라면 이는 자연수의 이항 계수의 정의와 일치한다.

초한 이항 계수의 값은 다음과 같다.
:\binom\kappa\lambda=\begin{cases}
\kappa^\lambda&\lambda\le\kappa\ge\aleph_0\\
0&\lambda>\kappa\\
\binom nk&k=\lambda
첫 번째 경우는
:\kappa^\lambda\le\binom{\kappa\lambda}\lambda=\binom\kappa\lambda\le\kappa^\lambda
이기 때문이다. (여기서 첫 부등식은 \lambda개의, 크기가 \kappa인 집합들에서 각각 하나의 원소를 뽑는 것이다.)

특히, 중심 이항 계수는 다음과 같다.
:\binom{2\kappa}\kappa=\binom\kappa\kappa=2^\kappa
초한 이항 계수의 경우, 유한 이항 계수에 대하여 성립하는 대칭성이 일반적으로 성립하지 않는다.
:\binom{\kappa+\lambda}\lambda\ne\binom{\kappa+\lambda}\kappa
예를 들어
:\binom{1+\aleph_0}1=\aleph_0
:\binom{1+\aleph_0}{\aleph_0}=2^{\aleph_0}
이다.

## 응용
### 조합론
조합론에서, 이항 계수는 크기가 n인 유한 집합의 크기가 k인 부분집합의 수이다. 즉, n개의 원소의 k개의 조합의 수이다. 이 밖에도, 이항계수는 다음과 같은 다양한 조합론적 문제에 등장한다.
* 카탈랑 수 \textstyle C_n=\binom{2n}n/(n+1)= {2n \choose n} - {2n \choose n+1}는 다양한 조합론적 문제의 해이다.
* 크기가 n인 집합에서, 크기가 k인 중복집합을 고를 수 있는 가짓수는 \textstyle\binom{n+k-1}k이다.
* k개의 기호 \bullet 및 n개의 기호 \circ를 포함하는 문자열의 수는 \textstyle\binom{n+k}k이다. 또한, \bullet\bullet을 부분 문자열로 포함하지 않는 문자열의 수는 \textstyle\binom{n+1}k이다.

### 대수학

이항 계수는 대수학에서 다음과 같이 이항급수의 전개에 사용되며, "이항계수"라는 이름은 이로부터 유래한다.
:(x+y)^n = \sum_{k=0}^n\binom nkx^{n-k} y^k = \sum_{k=0}^n \binom nkx^k y^{n-k}

### 통계학

통계학에서, 이항 계수는 이항분포를 정의하는 데 사용된다.

### 정수론
베르트랑의 공준을 증명할 때, 중심 이항 계수의 성질로부터 시작한다. 또한, 중심 이항 계수는 아페리 상수 \zeta(3)가 무리수임을 증명할 때 쓰이는 급수
:\zeta(3)=\frac52\sum_{n=1}^\infty \frac{(-1)^{n+1}}{{n^3}\binom{2n}n}
에 등장한다.

## 역사
이항 계수는 파스칼의 삼각형의 형태로 이미 중세 동서양 수학에 알려져 있었다. 오늘날 쓰이는 표기법 \textstyle\binom nk은 안드레아스 프라이헤르 폰 에팅스하우젠()이 1826년에 도입하였다.

## 같이 보기
* 포흐하머 기호
* 12정도

## 각주

* 
* 
* 
* 
* 

## 외부 링크
* 
* 
* 
* 
* 
* 

분류:조합론
분류:계승과 이항식 주제
분류:정수열