이항 계수(Binomial Coefficient)

이항 계수
: n개 중에 k개를 순서 없이 고르는 방법
: $_{n}C_{m}$ 또는 $n\choose m$ = $n!\over k!(n-k)!$ 으로 쓴다.

Pascal's Triangle
: C[n][k] = C[n-1][k-1] + C[n-1][k], 여기서 C[n][k]는 $n\choose k$

각종 특징들
: $(x+y)^{n}$ = $\sum_{k=0}^{n}$$n\choose k$$x^{n-k} y^{k}$
: $n\choose k$ = $n-1\choose k-1$ + $n-1\choose k$ (1$\le$k$\le$n-1)
: $n\choose k$ = $n\choose n-k$
: n개 중에 k개를 중복없이 뽑는 방법의 수 $n\choose k$
: n개 중에 k개를 중복을 허용하면서 뽑는 방법의 수 $n+k-1\choose k$
: 0과 1로만 이루어진 문자열의 개수 $n+k\choose k$
: 0과 1로만 이루어진 문자열의 개수 (1은 연속하지 않음) $n+1\choose k$