이항계수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
이항 계수의 표를 파스칼의 삼각형이라고 한다.

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

정의[편집]

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

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

인 경우의 이항 계수를 중심 이항 계수(中心二項係數, 영어: 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. 

바깥 고리[편집]

같이 보기[편집]