이항계수의 합은 다음과 같다. 2n=∑k=0n(nk) 2^{n} = \sum_{k=0}^{n} \binom{n}{k} 2n=k=0∑n(kn)
유한집합 SSS 의 기수가 n=∣S∣n = |S|n=∣S∣ 이면 그 멱집합 2S2^{S}2S 의 기수는 2n2^{n}2n 이다.
이항정리: (x+y)n=∑k=0n(nk)xkyn−k (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} (x+y)n=k=0∑n(kn)xkyn−k
x=y=1x = y = 1x=y=1 을 대입하면 2n=∑k=0n(nk)1k1n−k2^{n} = \sum_{k=0}^{n} \binom{n}{k} 1^{k} 1^{n-k}2n=∑k=0n(kn)1k1n−k 을 얻는다.
■
Bóna, M. (2025). Introduction to enumerative and analytic combinatorics: p28. ↩︎