이항 계수

조합론에서 이항 계수(二項係數, )는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

정의 
자연수  및 정수 가 주어졌을 때, 이항 계수 는 다음과 같다.

여기서 는 계승이다. 이항 계수를  대신 나 로 쓰기도 한다. 이항 계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 한다.

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

성질

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

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

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

이항 계수의 합 
이 공식들은 생성함수 (의 도함수)의  값으로부터 유도할 수 있다.

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

여기서 은 번째 피보나치 수이다.

이항 계수의 곱의 합 
다음 항등식은 주세걸-방데르몽드 항등식(朱世傑-Vandermonde恒等式, )이라고 한다.

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

이는 조합론적으로 증명할 수 있다. 은 크기가  집합 속에서 개의 조합의 가짓수인데, 이는 크기 의 집합의 처음 절반에서 개를 고르고, 나머지 절반에서 개를 고르는 가짓수의 에 대한 합 과 같다.

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

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

점근 공식 
일반적으로, 모든  및 에 대하여, 다음과 같은 부등식이 성립한다.

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

 및 에 대하여, 스털링 근사를 사용하여 이항계수를 다음과 같이 근사할 수 있다.

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

이다.

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

수론적 성질 
쿠머 정리(Kummer定理, )에 따르면, 음이 아닌 정수  및 소수 에 대하여,

인 최대 는 다음과 같다.

즉, 이는 를 진법에서 계산할 때 받아올림의 수와 같다.

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

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

임의의 양의 정수 에 대하여, 다음이 성립한다.

은 인 이항계수 의 수이므로, 임의의 양의 정수는 거의 모든 이항계수를 약수로 가진다. 이는 데이비드 싱매스터()가 1974년에 증명하였다.

초한 이항 계수 
이항 계수의 정의는 임의의 기수에 대하여 확장할 수 있다. 임의의 기수 에 대하여, 초한 이항 계수(超限二項係數, )

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

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

첫 번째 경우는

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

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

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

예를 들어

이다.

응용

조합론 
조합론에서, 이항 계수는 크기가 인 유한 집합의 크기가 인 부분집합의 수이다. 즉, 개의 원소의 개의 조합의 수이다. 이 밖에도, 이항계수는 다음과 같은 다양한 조합론적 문제에 등장한다.
 카탈랑 수 는 다양한 조합론적 문제의 해이다.
 크기가 인 집합에서, 크기가 인 중복집합을 고를 수 있는 가짓수는 이다.
 개의 기호  및 개의 기호 를 포함하는 문자열의 수는 이다. 또한, 을 부분 문자열로 포함하지 않는 문자열의 수는 이다.

대수학 

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

통계학 

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

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

에 등장한다.

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

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

참고 문헌

외부 링크 
 
 
 
 
 
 

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