[수학,조합론] 이항 계수 (1)

en.wikipedia.org/wiki/Binomial_coefficient

Binomial coefficient - Wikipedia

위글의 내용을 참고해 짧게 정리를 해봤다.

 

 

이항계수란?

• 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 말한다.
• 전체 집합에서 원소의 개수 n에 대해 k개의 원소를 뽑는 조합의 수

\(\begin{pmatrix}n \\k\end{pmatrix}=\dfrac{n!}{k!\left( n-k\right) !}=nCr\)

코드로 나타내면 아래와 같다. 팩토리얼은 함수로 나와있지만 직접구현

 

def binomial_coefficient(n,k) :
    return factorial(n)//factorial(k)//factorial(n-k)

def factorial(x):
    result = 1
    for i in range(2,x+1) :
        result *= i
    return result

 

이항 계수의 식을 알고 있다면 직관적이고 쉽게 풀 수 있는 정도의 레벨이라고 생각한다. 

하지만 팩토리얼은 n의 값이 커지면 커질수록 overflow 날 가능성이 크다. 다른방법이 필요하다.

이항계수의 성질을 살펴보자.

 

\(nCr=nCn-r\)

=> \(\begin{pmatrix} n \\ k \end{pmatrix}=\left( \dfrac{n}{n-k}\right)\)

=> \(\begin{pmatrix} n \\ 0 \end{pmatrix}=\begin{pmatrix} n \\ n \end{pmatrix}=1\)

'파스칼의 삼각형(법칙) 참고'

\(_{n+1}^{}\textrm{C}_{r+1} = nCr = nC_{r+1}\)

=> \(\begin{pmatrix} n+1 \\ r+1 \end{pmatrix}=\begin{pmatrix} n \\ r \end{pmatrix}+\begin{pmatrix} n \\ r+1 \end{pmatrix}\)

=> \(\begin{pmatrix} n \\ r \end{pmatrix}=\begin{pmatrix} n-1 \\ r-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ r \end{pmatrix}\)

위의 성질에서 알고리즘의 핵심인 '점화식'을 얻을 수 있다.

 

점화식을 이용한 코드는 다음장에서 확인가능합니다.