이항계수

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

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

정의

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

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

이항 계수를 $\textstyle {\binom {n}{k}}$$\textstyle {\binom nk}$ 대신 ${}_{n}C_{k}$${}_{n}C_{k}$나 $C(n,k)$$C(n, k)$로 쓰기도 한다. 이항 계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 한다.

$n=2k$$n=2k$인 경우의 이항 계수를 중심 이항 계수(中心二項係數, 영어: central binomial coefficient)라고 한다. 이는 다음과 같다 ($k=0,1,2,\dots$$k=0,1,2,\dots$).

1, 2, 6, 20, 70, 252, 924, 432, 12870, 48620, … (OEIS의 수열 A000984)

성질

항등식

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

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

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

${\binom {n}{k}}+{\binom {n}{k+1}}={\binom {n+1}{k+1}}$${\binom nk}+{\binom n{k+1}}={\binom {n+1}{k+1}}$

급수 공식

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

이항 계수의 합

이 공식들은 생성 함수 $(1+x)^{n}$$(1+x)^n$(의 도함수)의 $x=1$$x=1$ 값으로부터 유도할 수 있다.

$\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}$$\sum_{k=0}^n\binom nk=2^n$

$\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}$$\sum_{k=0}^nk\binom nk=n2^{n-1}$

또한, 피보나치 수를 다음과 같이 나타낼 수 있다.

$\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1)$$\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}k =F(n+1)$

여기서 $F(n)$$F(n)$은 $n$$n$번째 피보나치 수이다.

이항 계수의 곱의 합

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

$\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n}{k-j}}={\binom {m+n}{k}}$$\sum_{j=0}^k\binom mj\binom n{k-j}=\binom{m+n}k$

이항계수의 제곱의 합은 다음과 같이 중심 이항 계수로 주어진다.

$\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}$$\sum_{k=0}^{n} \binom nk^2 =\binom{2n}n$

이는 조합론적으로 증명할 수 있다. $\textstyle {\binom {2n}{n}}$$\textstyle\binom{2n}n$은 크기가 $2n$$2n$ 집합 속에서 $n$$n$개의 조합의 가짓수인데, 이는 크기 $2n$$2n$의 집합의 처음 절반에서 $k$$k$개를 고르고, 나머지 절반에서 $n-k$$n-k$개를 고르는 가짓수의 $k$$k$에 대한 합 $\textstyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}=\sum _{k=0}^{n}{\binom {n}{k}}^{2}$$\textstyle\sum_{k=0}^n\binom nk\binom n{n-k}=\sum_{k=0}^n\binom nk^2$과 같다.

생성 함수

이항 계수는 다음과 같은 생성 함수를 갖는다.

$\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}$$\sum _{{k=0}}^{n}{\binom nk}x^{k}=(1+x)^{n}$

$\sum _{n=k}^{\infty }{\binom {n}{k}}x^{n}={\frac {x^{k}}{(1-x)^{k+1}}}$$\sum _{{n=k}}^{\infty }{\binom nk}x^{n}={\frac {x^{k}}{(1-x)^{{k+1}}}}$

$\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}$$\sum _{{n=0}}^{\infty }\sum _{{k=0}}^{n}{\binom nk}x^{k}y^{n}={\frac 1{1-y-xy}}$

$\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\frac {1}{(n+k)!}}{\binom {n+k}{k}}x^{k}y^{n}=\exp(x+y)$$\sum _{{n=0}}^{\infty }\sum _{{k=0}}^{n}{\frac 1{(n+k)!}}{\binom {n+k}k}x^{k}y^{n}=\exp(x+y)$

중심 이항 계수의 생성 함수는 다음과 같다.

$\sum _{n=0}^{\infty }{\binom {2n}{n}}x^{n}={\frac {1}{\sqrt {1-4x}}}$$\sum_{n=0}^\infty\binom{2n}nx^n=\frac1{\sqrt{1-4x}}$

점근 공식

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

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

중심 이항 계수의 경우 다음 부등식이 성립한다.

${\frac {4^{n}}{\sqrt {4n}}}\leq {\binom {2n}{n}}\leq {\frac {4^{n}}{\sqrt {3n+1}}}\qquad \forall n\geq 1$$\frac{4^n}{\sqrt{4n}} \le \binom{2n}n \le \frac{4^n}{\sqrt{3n+1}}\qquad\forall n\ge1$

$n\gg 1$$n\gg 1$ 및 $|1/2-k/n|\ll 1$$|1/2-k/n|\ll 1$에 대하여, 스털링 근사를 사용하여 이항계수를 다음과 같이 근사할 수 있다.

${\binom {n}{k}}\approx {\frac {2^{n+1}}{\sqrt {2\pi n}}}\exp(-(2k-n)^{2}/2n)$${\binom nk}\approx {\frac {2^{{n+1}}}{{\sqrt {2\pi n}}}}\exp(-(2k-n)^{2}/2n)$

이에 따라, 이항분포를 정규분포로 근사할 수 있다. 특히, $k=n/2$$k=n/2$일 경우 중심 이항 계수의 스털링 근사는 다음과 같다.

${\binom {n}{n/2}}\approx {\frac {2^{n+1}}{\sqrt {2\pi n}}}$${\binom n{n/2}}\approx {\frac {2^{{n+1}}}{{\sqrt {2\pi n}}}}$

이다.

만약 $n\gg 1$$n\gg 1$이며 $n\gg k$$n\gg k$라면, 스털링 근사를 사용하여 이항 계수를 다음과 같이 근사할 수 있다.

${\binom {n}{k}}\sim {\frac {(n/k-1/2)^{k}\exp(k)}{\sqrt {2\pi k}}}$$\binom nk\sim\frac{(n/k-1/2)^k\exp(k)}{\sqrt{2\pi k}}$

수론적 성질

쿠머 정리(Kummer定理, 영어: Kummer’s theorem)에 따르면, 음이 아닌 정수 $n\geq k$$n\geq k$ 및 소수 $p$$p$에 대하여,

$p^{c}\mid {\binom {n}{k}}$$p^{c}\mid {\binom nk}$

인 최대 $c$$c$는 다음과 같다.

$c=|\{b\in \mathbb {Z} ^{+}\colon k/p^{b}-\lfloor k/p^{b}\rfloor >n/p^{b}-\lfloor n/p^{b}\rfloor \}|$$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)$$k+(n-k)$를 $p$$p$진법에서 계산할 때 받아올림의 수와 같다.

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

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

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

$\lim _{N\to \infty }{\frac {\left|\{n<N\colon d\mid {\binom {n}{k}}\}\right|}{N(N+1)/2}}=1$$\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}^{n}1$$\textstyle N(N+1)/2=\sum _{{n=0}}^{{N-1}}\sum _{{k=0}}^{n}1$은 $n<N$$n<N$인 이항계수 $\textstyle {\binom {n}{k}}$$\textstyle {\binom nk}$의 수이므로, 임의의 양의 정수는 거의 모든 이항계수를 약수로 가진다. 이는 데이비드 싱매스터(영어: David Singmaster)가 1974년에 증명하였다.

초한 이항 계수

이항 계수의 정의는 임의의 기수에 대하여 확장할 수 있다. 임의의 기수 $\kappa ,\lambda$$\kappa ,\lambda$에 대하여, 초한 이항 계수(超限二項係數, 영어: transfinite binomial coefficient)

${\binom {\kappa }{\lambda }}$$\binom\kappa\lambda$

는 크기가 $\kappa$$\kappa$인 집합의, 크기가 $\lambda$$\lambda$인 부분 집합들의 수이다. 만약 $\kappa$$\kappa$와 $\lambda$$\lambda$가 둘 다 유한 기수라면 이는 자연수의 이항 계수의 정의와 일치한다.

초한 이항 계수의 값은 다음과 같다.

${\binom {\kappa }{\lambda }}={\begin{cases}\kappa ^{\lambda }&\lambda \leq \kappa \geq \aleph _{0}\\0&\lambda >\kappa \\{\binom {n}{k}}&k=\lambda <\aleph _{0},\;n=\kappa <\aleph _{0}\end{cases}}$$\binom\kappa\lambda=\begin{cases} \kappa^\lambda&\lambda\le\kappa\ge\aleph_0\\ 0&\lambda>\kappa\\ \binom nk&k=\lambda<\aleph_0,\;n=\kappa<\aleph_0 \end{cases}$

첫 번째 경우는

$\kappa ^{\lambda }\leq {\binom {\kappa \lambda }{\lambda }}={\binom {\kappa }{\lambda }}\leq \kappa ^{\lambda }$$\kappa^\lambda\le\binom{\kappa\lambda}\lambda=\binom\kappa\lambda\le\kappa^\lambda$

이기 때문이다. (여기서 첫 부등식은 $\lambda$$\lambda$개의, 크기가 $\kappa$$\kappa$인 집합들에서 각각 하나의 원소를 뽑는 것이다.)

특히, 중심 이항 계수는 다음과 같다.

${\binom {2\kappa }{\kappa }}={\binom {\kappa }{\kappa }}=2^{\kappa }$$\binom{2\kappa}\kappa=\binom\kappa\kappa=2^\kappa$

초한 이항 계수의 경우, 유한 이항 계수에 대하여 성립하는 대칭성이 일반적으로 성립하지 않는다.

${\binom {\kappa +\lambda }{\lambda }}\neq {\binom {\kappa +\lambda }{\kappa }}$$\binom{\kappa+\lambda}\lambda\ne\binom{\kappa+\lambda}\kappa$

예를 들어

${\binom {1+\aleph _{0}}{1}}=\aleph _{0}$$\binom{1+\aleph_0}1=\aleph_0$

${\binom {1+\aleph _{0}}{\aleph _{0}}}=2^{\aleph _{0}}$$\binom{1+\aleph_0}{\aleph_0}=2^{\aleph_0}$

이다.

응용

조합론

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

• 카탈랑 수 $\textstyle C_{n}={\binom {2n}{n}}/(n+1)={2n \choose n}-{2n \choose n+1}$$\textstyle C_n=\binom{2n}n/(n+1)= {2n \choose n} - {2n \choose n+1}$는 다양한 조합론적 문제의 해이다.
• 크기가 $n$$n$인 집합에서, 크기가 $k$$k$인 중복집합을 고를 수 있는 가짓수는 $\textstyle {\binom {n+k-1}{k}}$$\textstyle {\binom {n+k-1}k}$이다.
• $k$$k$개의 기호 $\bullet$$\bullet$ 및 $n$$n$개의 기호 $\circ$$\circ$를 포함하는 문자열의 수는 $\textstyle {\binom {n+k}{k}}$$\textstyle {\binom {n+k}k}$이다. 또한, $\bullet \bullet$$\bullet \bullet$을 부분 문자열로 포함하지 않는 문자열의 수는 $\textstyle {\binom {n+1}{k}}$$\textstyle {\binom {n+1}k}$이다.

대수학

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

이항 계수는 대수학에서 다음과 같이 이항급수의 전개에 사용되며, "이항계수"라는 이름은 이로부터 유래한다.

$(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}$$(x+y)^{n}=\sum _{{k=0}}^{n}{\binom nk}x^{{n-k}}y^{k}=\sum _{{k=0}}^{n}{\binom nk}x^{k}y^{{n-k}}$

통계학

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

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

정수론

베르트랑의 공준을 증명할 때, 중심 이항 계수의 성질로부터 시작한다. 또한, 중심 이항 계수는 아페리 상수 $\zeta (3)$$\zeta (3)$가 무리수임을 증명할 때 쓰이는 급수

$\zeta (3)={\frac {5}{2}}\sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{{n^{3}}{\binom {2n}{n}}}}$$\zeta(3)=\frac52\sum_{n=1}^\infty \frac{(-1)^{n+1}}{{n^3}\binom{2n}n}$

에 등장한다.

역사

이항 계수는 파스칼의 삼각형의 형태로 이미 중세 동서양 수학에 알려져 있었다. 오늘날 쓰이는 표기법 $\textstyle {\binom {n}{k}}$$\textstyle {\binom nk}$은 안드레아스 프라이헤르 폰 에팅스하우젠(독일어: Andreas Freiherr von Ettingshausen)이 1826년에 도입하였다.

참고 문헌

• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). 《Concrete mathematics: a foundation for computer science》 (영어) 2판. Addison-Wesley Professional. ISBN 0-201-55802-5. MR 1397498. Zbl 0836.00001.  CS1 관리 - 추가 문구 (링크)
• Fowler, David (1996년 1월). “The binomial coefficient function”. 《The American Mathematical Monthly》 (영어) 103 (1). doi:10.2307/2975209. JSTOR 2975209. Zbl 0857.05003. 
• Goetgheluck, P. (1987년 4월). “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〉. 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.  CS1 관리 - 여러 이름 (링크)
• Enochs, Edgar E. (2004). “Binomial coefficients” (PDF). 《Boletín de la Asociación Matemática Venezolana》 (영어) 11 (1): 17–28. Zbl 1062.05007. 

바깥 고리

• “Binomial coefficients”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Eric Wolfgang Weisstein. “Binomial coefficient”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Eric Wolfgang Weisstein. “Central binomial coefficient”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “이항계수와 조합”. 《수학노트》. 
• “중심이항계수 (central binomial coefficient)”. 《수학노트》. 
• “중심이항계수가 등장하는 어떤 급수에 대한 문제”. 《수학노트》. 

같이 보기

• 파스칼의 삼각형
• 이항급수
• 이항분포
• 계승
• 포흐하머 기호
• 12정도