이항계수

이항계수의 표를 파스칼의 삼각형이라고 한다.

조합론에서, 이항계수(二項係數, 영어: binomial coefficient)는 주어진 크기의 (순서 없는) 조합의 가짓수이다.

정의

자연수 $n$ 및 정수 $k$가 주어졌을 때, 이항계수 $\textstyle\binom nk$는 다음과 같다.

$\binom nk=\begin{cases} n!/\left(k!(n-k)!\right)&0\le k\le n\\ 0&k<0\\ 0&k>n \end{cases}$

이항계수를 $\textstyle\binom nk$ 대신 ${}_nC_k$나 $C(n, k)$로 쓰기도 한다. $n=2k$인 경우의 이항계수를 중심이항계수라고 한다.

성질

항등식

이항계수는 다음과 같은 항등식을 만족시킨다. 이는 이항계수의 정의로부터 쉽게 증명할 수 있다.

$\binom nk=\binom n{n-k}$

다음과 같은 점화식이 성립하며, 이는 파스칼의 법칙(영어: Pascal’s rule)이라고 한다.

$\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$번째 피보나치 수이다.

이항계수의 곱의 합

다음 항등식은 주세걸-방데르몽드 항등식(영어: Zhu–Vandermonde identity)이라고 한다.

$\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)$

근사

일반적으로, 모든 $n\in\mathbb N$ 및 $k\in\{1,\dots,n\}$에 대하여, 다음과 같은 부등식이 성립한다.

$(n/k)^k\le\binom nk\le n^k/k!\le(en/k)^k$

$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\approx\frac{(n/k-1/2)^k\exp(k)}{\sqrt{2\pi k}}$

수론적 성질

쿠머 정리(영어: Kummer’s theorem)에 따르면, 음이 아닌 정수 $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 squarefree conjecture)라고 한다. 에르되시 팔이 1980년에 추측하였고, 앤드루 그랜빌(영어: Andrew Granville)과 올리비에 라마레(프랑스어: Olivier Ramaré)가 1996년에 증명하였다.

임의의 양의 정수 $d\in\mathbb Z^+$에 대하여, 다음이 성립한다.

$\lim_{N\to\infty}\frac{\left|\{n<N\colon d \mid\binom nk\}\right|}{N(N+1)/2}=1$

$\textstyle N(N+1)/2=\sum_{n=0}^{N-1}\sum_{k=0}^n1$은 $n<N$인 이항계수 $\textstyle\binom nk$의 수이므로, 임의의 양의 정수는 거의 모든 이항계수를 약수로 가진다. 이는 데이비드 싱매스터(영어: David Singmaster)가 1974년에 증명하였다.

응용

조합론

조합론에서, 이항계수는 크기가 $n$인 유한 집합의 크기가 $k$인 부분집합의 수이다. 즉, $n$개의 원소의 $k$개의 조합의 수이다. 이 밖에도, 이항계수는 다음과 같은 다양한 조합론적 문제에 등장한다.

• 카탈랑 수 $\textstyle C_n=\binom{2n}n/(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}$

통계학

이 부분의 본문은 이항분포입니다.

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

같이 보기

• 이항급수
• 중심이항계수
• 이항분포

참고 문헌

• Graham, Ronald L.; Donald E. Knuth, Oren Patashnik (1994). 《Concrete mathematics: a foundation for computer science》 (영어) (2판판). Addison-Wesley Professional. ISBN 0-201-55802-5. MR 1397498. Zbl 0836.00001. 
• Fowler, David (1996-01). “The binomial coefficient function” (영어). 《The American Mathematical Monthly》 103 (1). doi:10.2307/2975209. JSTOR 2975209. Zbl 0857.05003. 
• Goetgheluck, P. (1987-04). “Computing binomial coefficients” (영어). 《The American Mathematical Monthly》 94 (4). doi:10.2307/2323099. JSTOR 2323099. Zbl 0617.05004. 
• Granville, Andrew (1997). 〈Arithmetic properties of binomial coefficients. I: Binomial coefficients modulo prime powers〉. In J. Borwein, P. Borwein, L. Jörgenson, R. Corless. 《Organic mathematics. Proceedings of the Organic Mathematics Workshop, December 12-14, 1995, Simon Fraser University, Burnaby, British Columbia》 (영어). Canadian Mathematical Society Conference Proceedings 20. American Mathematical Society. 253–276쪽. ISBN 978-0-8218-0668-5. Zbl 0903.11005. 
• Enochs, Edgar E. (2004). “Binomial coefficients” (영어). 《Boletín de la Asociación Matemática Venezolana》 11 (1): 17–28. Zbl 1062.05007. 

바깥 고리

• Eric Wolfgang Weisstein. “Binomial coefficient” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• “Binomial coefficients” (영어). 《Encyclopedia of Mathematics》. Springer. 2001. ISBN 978-1-55608-010-4.