주 메뉴 열기

이항 계수

(이항계수에서 넘어옴)

정의편집

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

 

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

 인 경우의 이항 계수를 중심 이항 계수(中心二項係數, 영어: central binomial coefficient)라고 한다. 이는 다음과 같다 ( ).

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

성질편집

항등식편집

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

 

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

 

급수 공식편집

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

이항 계수의 합편집

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

 
 

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

 

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

이항 계수의 곱의 합편집

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

 

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

 

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

생성 함수편집

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

 
 
 
 

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

 

점근 공식편집

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

 

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

 

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

 

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

 

이다.

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

 

수론적 성질편집

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

 

인 최대  는 다음과 같다.

 

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

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

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

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

 

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

초한 이항 계수편집

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

 

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

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

 

첫 번째 경우는

 

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

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

 

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

 

예를 들어

 
 

이다.

응용편집

조합론편집

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

  • 카탈랑 수  는 다양한 조합론적 문제의 해이다.
  • 크기가  인 집합에서, 크기가  중복집합을 고를 수 있는 가짓수는  이다.
  •  개의 기호   개의 기호  를 포함하는 문자열의 수는  이다. 또한,  을 부분 문자열로 포함하지 않는 문자열의 수는  이다.

대수학편집

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

 

통계학편집

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

정수론편집

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

 

에 등장한다.

역사편집

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

같이 보기편집

참고 문헌편집

  1. Erdős, P.; Graham, R. L. (1980). 《Old and new problems and results in combinatorial number theory》. L’Enseignement Mathématique (영어) 28. Geneva: Université de Genève. Zbl 0434.10001. 
  2. Granville, A.; Ramaré, O. (1996년 6월). “Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients” (PDF). 《Mathematika》 (영어) 43 (1): 73–107. doi:10.1112/S0025579300011608. 
  3. Singmaster, David (1974). “Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients”. 《Journal of the London Mathematical Society》 (영어) 8 (3): 555–560. doi:10.1112/jlms/s2-8.3.555. 

외부 링크편집