logo

이항계수 합 공식 📂보조정리

이항계수 합 공식

공식

이항계수 합 공식 1

이항계수의 합은 다음과 같다. 2n=k=0n(nk) 2^{n} = \sum_{k=0}^{n} \binom{n}{k}

따름정리: 멱집합의 기수

유한집합 SS기수n=Sn = |S| 이면 그 멱집합 2S2^{S} 의 기수는 2n2^{n} 이다.

유도

이항정리: (x+y)n=k=0n(nk)xkynk (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k}

x=y=1x = y = 1 을 대입하면 2n=k=0n(nk)1k1nk2^{n} = \sum_{k=0}^{n} \binom{n}{k} 1^{k} 1^{n-k} 을 얻는다.


  1. Bóna, M. (2025). Introduction to enumerative and analytic combinatorics: p28. ↩︎