[확률과 통계] 비트 경우의 수

n개의 비트 중에서 k개의 비트는 1, 나머지 n - k개의 비트는 0을 가지는 모든 조합의 수는?

 

k = 0부터 시작하여 n개까지를 뽑을 수 있으므로, 

$\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})1^n{1}^{n-k}=(1+1{)}^n=2^n$

 

 

만약 모든 비트가 0이 아닌 경우의 수를 구하고 싶다면 1을 빼면 된다.

참고로 1을 빼는 것은 $(\genfrac{}{}{0ex}{}{n}{0})$을 빼는 것이다.

 

 

추가적으로 $\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})=0$임을 증명하면, 

$\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})=\sum _{i=0}^n(-1{)}^i{1}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})$이므로 $(-1+1{)}^n=0$이다.