[수학] 조합 (Combination)

조합론

 

[개념 소개]

n개의 원소 중 k개를 뽑는 경우의 수

 

---

[성질]

• $\dbinom{n}{k} = \dfrac{n!}{(n - k)!k!}$
• $\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$
• $\Sigma_{k = 0}^{n} \dbinom{n}{k} = 2^n$

---

[관련 알고리즘]

• 파스칼의 삼각형: kangwlgns.tistory.com/46
• 페르마의 소정리를 이용한 이항 계수: kangwlgns.tistory.com/48
• 뤼카의 정리: kangwlgns.tistory.com/49