## 二項式係數與組合問題

$\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots(1)}$

$\displaystyle \binom{6}{1}+\binom{6}{2}+\binom{6}{3}+\binom{6}{4}+\binom{6}{5}+\binom{6}{6}=6+15+20+15+6+1=63$

$\displaystyle \binom{n}{k+1}=\frac{n!}{(k+1)!(n-k-1)!}=\frac{(n-k)n!}{(k+1)k!(n-k)!}=\frac{n-k}{k+1}\binom{n}{k}$

$\displaystyle \binom{n+1}{k}=\frac{(n+1)!}{k!(n+1-k)!}=\frac{(n+1)n!}{(n+1-k)k!(n-k)!}=\frac{n+1}{n+1-k}\binom{n}{k}$

$\displaystyle (a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$

$\displaystyle (a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)}_{n}$

$\displaystyle (1+t)^n=1+nt+\frac{n(n-1)}{2}t^2+\cdots+t^n=\sum_{k=0}^n\binom{n}{k}t^k$

$\displaystyle (1+t)^n=(1+t)(1+t)^{n-1}$

$\displaystyle \sum_{k=0}^n\binom{n}{k}t^k=(1+t)\sum_{k=0}^{n-1}\binom{n-1}{k}t^k=\sum_{k=0}^{n-1}\binom{n-1}{k}t^k+\sum_{k=0}^{n-1}\binom{n-1}{k}t^{k+1}$

$\displaystyle \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$

$\begin{array}{ccccccccccccc}\displaystyle &&& &&& \binom{0}{0}&&&&&&\\ &&&&& \binom{1}{0} & & \binom{1}{1} &&&&&\\ &&&& \binom{2}{0} & & \binom{2}{1} & & \binom{2}{2} &&&&\\ &&&\binom{3}{0} && \binom{3}{1} && \binom{3}{2}&& \binom{3}{3} &&&\\ &&\binom{4}{0}&& \binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4}&&\\ &\binom{5}{0}&&\binom{5}{1}&&\binom{5}{2}&&\binom{5}{3}&&\binom{5}{4}&&\binom{5}{5}&\\ \binom{6}{0}&&\binom{6}{1}&&\binom{6}{2}&&\binom{6}{3}&&\binom{6}{4}&&\binom{6}{5}&&\binom{6}{6} \end{array}$

$\begin{array}{ccccccccccccc} &&& &&& 1&&&&&&\\ &&&&& 1 & & 1 &&&&&\\ &&&& 1 & & 2 & & 1 &&&&\\ &&&1 && 3 && 3&& 1 &&&\\ &&1&& 4&&6&&4&&1&&\\ &1&&5&&10&&10&&5&&1&\\ 1&&6&&15&&20&&15&&6&&1 \end{array}$

$\displaystyle (1+1)^n=\sum_{k=0}^n\binom{n}{k}=2^n$

$\displaystyle (1-1)^n=\sum_{k=0}^n(-1)^k\binom{n}{k}=0$

$\displaystyle n(1+t)^{n-1}=\sum_{k=1}^nk\binom{n}{k}t^{k-1}$

$\displaystyle n2^{n-1}=\sum_{k=1}^nk\binom{n}{k}$

$\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup$

$\sqcup 1 \sqcup 1\sqcup 1\sqcup 1\sqcup 1\sqcup$

$5+1=6$ 個槽選取 $3$ 個置放 $0$ 的組合數即為所求，答案是 $\binom{6}{3}=20$。所以，包含 $n$$1$$k$$0$，且沒有兩個 $0$ 相鄰的字符串共有 $\binom{n+1}{k}$ 個。根據對稱性，沒有兩個 $1$ 相鄰的字符串共有 $\binom{k+1}{n}$ 個。

$\bullet\bullet\vert \bullet\bullet\bullet\vert ~~\vert\bullet\vert \bullet\bullet\bullet\bullet\vert$

$\displaystyle \binom{2}{0}+\binom{3}{1}+\binom{4}{2}+\binom{5}{3}+\binom{6}{4}+\binom{7}{5}=1+3+6+10+15+21=56$

$\displaystyle \binom{2}{0}+\binom{3}{1}+\binom{4}{2}+\binom{5}{3}+\binom{6}{4}+\binom{7}{5}=\binom{8}{5}$

$\displaystyle C_n=\frac{1}{n+1}\binom{2n}{n},~~n\ge 1$