二項係数についての覚書
$n$次多項式$p_{n}(x) \coloneqq (x+1)^{n} \in \mathbb{Z}[x]$を展開したときの$x^{k}$の係数を$\binom{n}{k}$で表わす：
$$
(x+1)^{n} = \sum_{k=0}^{n} \binom{n}{k}x^{k}.$$
また，$k \in \mathbb{Z} \smallsetminus \{0,\ldots,n\}$に対しては$\binom{n}{k} \coloneqq 0$とおく．整数$\binom{n}{k} \in \mathbb{Z}$を二項係数という．
$$ \binom{n}{n} = 1 = p_{n}(0) = \binom{n}{0}.$$
\begin{align} 2^{n} = p_{n}(1) &= \sum_{k=0}^{n} \binom{n}{k};\\ 0 = p_{n}(-1) &= \sum_{k=0}^{n} \binom{n}{k}(-1)^{k},\ n\geq 1. \end{align}
$$ n(x+1)^{n-1} = \frac{\d}{\d{x}}p_{n}(x) = \sum_{k=1}^{n} \binom{n}{k} kx^{k-1} \quad\leadsto\quad 2^{n-1} = \sum_{k=1}^{n} \frac{k}{n}\binom{n}{k}.$$
$$ \frac{2^{n+1}-1}{n+1} = \int_{0}^{1} (x+1)^{n}\,\d{x} = \sum_{k=0}^{n} \binom{n}{k} \int_{0}^{1} x^{k}\,\d{x} = \sum_{k=0}^{n} \frac{1}{k+1}\binom{n}{k}.$$
$$ \frac{1}{n+1} = \int_{0}^{1} (-x+1)^{n}\,\d{x} = \sum_{k=0}^{n} \binom{n}{k}(-1)^{k} \int_{0}^{1} x^{k}\,\d{x} = \sum_{k=0}^{n} \frac{(-1)^{k}}{k+1} \binom{n}{k}.$$
整数$k,\ell\in\mathbb{Z}$が$k+\ell\in\mathbb{N}$を満たしているとき
$$
[k,\ell] \coloneqq \binom{k+\ell}{k}$$
とおく．
$k<0\leq\ell+k<\ell$のとき
$$
[k,\ell] = \binom{k+\ell}{k} = 0 = \binom{\ell+k}{\ell} = [\ell,k]$$
が成り立つ．
$1 \leq k+\ell$のとき，
$$
[k,\ell] = [k-1,\ell] + [k,\ell-1]$$
が成り立つ．
$k<0 \lor \ell < 0$のときは両辺とも$0$に等しいので，$k,\ell\in\mathbb{N}$に対して成り立つことを示せばよい．ところで，
$$
\{(k,\ell) \in \mathbb{N}^{2} \mid 1 \leq k+\ell\} = \bigsqcup_{n\in\mathbb{N}} \{(k,\ell) \in \mathbb{N}^{2} \mid k+\ell = n+1\}$$
であり，
\begin{align}
\sum_{k+\ell=n+1} [k,\ell] x^{k}
&= \sum_{k=0}^{n+1} \binom{n+1}{k} x^{k} \\
&= (x+1)^{n+1} \\
&= (x+1)^{n}x + (x+1)^{n}1 \\[5pt]
&= \sum_{k+\ell=n} [k,\ell] x^{k+1} + \sum_{k+\ell=n}[k,\ell] x^{k} \\[5pt]
&= \sum_{k+\ell=n+1} [k-1,\ell] x^{k} + \sum_{k+\ell=n+1} [k,\ell-1] x^{k}
\end{align}
において$x^{k}$の係数を比較することで
$$
[k,\ell] = [k-1,\ell] + [k,\ell-1]$$
を得る．
$$ \binom{n}{k} = [k,n-k] = [k-1,n-k]+[k,n-k-1] = \binom{n-1}{k-1} + \binom{n-1}{k}.$$
$$ \sum_{k=m}^{n} \binom{k}{m} = \sum_{k=m}^{n} \left(\binom{k+1}{m+1}-\binom{k}{m+1}\right) = \binom{n+1}{m+1}.$$
単位的環$\mathbb{A}$の可換な元$a,b\in\mathbb{A}$に対して
$$
(a+b)^{n} = \sum_{k+\ell=n} [k,\ell] a^{k}b^{\ell}$$
が成り立つ．
- Base：両辺とも$1_{\mathbb{A}}$に等しい．
- Induction：
\begin{align} (a+b)^{n+1} &= (a+b)^{n}a + (a+b)^{n}b \\ &= \sum_{k+\ell=n} [k,\ell]a^{k+1}b^{\ell} + \sum_{k+\ell=n} [k,\ell] a^{k}b^{\ell+1} \\ &= \sum_{k+\ell=n+1} ([k-1,\ell]+[k,\ell-1]) a^{k}b^{\ell} \\ &= \sum_{k+\ell=n+1} [k,\ell] a^{k}b^{\ell}. \end{align}
任意の$0 \leq j \leq k \leq n$に対して
$$
\binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}$$
が成り立つ．
多項式$(xy+x+1)^{n}$を二通りに展開すると，
\begin{align}
((xy+x)+1)^{n}
&= \sum_{k=0}^{n} \binom{n}{k}x^{k}(y+1)^{k} \\
&= \sum_{k=0}^{n} \binom{n}{k}x^{k} \sum_{j=0}^{k} \binom{k}{j} y^{j} \\
&= \sum_{k=0}^{n} \sum_{j=0}^{k} \binom{n}{k}\binom{k}{j} x^{k}y^{j} \\
&= \sum_{j=0}^{n} \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j} x^{k}y^{j}; \\ \\
(xy+(x+1))^{n}
&= \sum_{j=0}^{n} \binom{n}{j} (xy)^{j}(x+1)^{n-j} \\
&= \sum_{j=0}^{n} \binom{n}{j} x^{j}y^{j} \sum_{k=0}^{n-j} \binom{n-j}{k} x^{k} \\
&= \sum_{j=0}^{n} \sum_{k=0}^{n-j} \binom{n}{j}\binom{n-j}{k} x^{j+k}y^{j} \\
&= \sum_{j=0}^{n} \sum_{k=j}^{n} \binom{n}{j}\binom{n-j}{k-j} x^{k}y^{j};
\end{align}
となるので，$x^{k}y^{j}$の係数を比較して結論を得る．
- 多項式$(xy+x+1)^{n}$に$x=1$を代入すると
$$ \sum_{j=0}^{n} \binom{n}{j} y^{j} 2^{n-j} = (y+2)^{n} = \sum_{j=0}^{n} \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j} y^{j}$$
となるので，
$$ \forall\,j\in\{0,\ldots,n\},\ \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j} = \binom{n}{j}2^{n-j}$$
が成り立つ． - 多項式$(xy+x+1)^{n}$に$x=-1$を代入すると
$$ (-y)^{n} = \sum_{j=0}^{n} \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j} (-1)^{k}y^{j}$$
となるので，
$$ \forall\,j \in \{0,\ldots,n-1\},\ \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j}(-1)^{k} = 0$$
が成り立つ．
各$k\in\{0,\ldots,n\}$に対して
$$
\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$
が成り立つ．
定義式
$$
(x+1)^{n} = \sum_{\ell=0}^{n} \binom{n}{\ell} x^{\ell}$$
の両辺を$k$回微分すると
$$
\frac{n!}{(n-k)!} (x+1)^{n-k} = \sum_{\ell=k}^{n} \binom{n}{\ell} \frac{\ell!}{(\ell-k)!} x^{\ell-k}$$
となるので，$x=0$を代入して
$$
\frac{n!}{(n-k)!} = \binom{n}{k}\frac{k!}{0!} \quad\leadsto\quad \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$
を得る．
$$ \frac{k}{n}\binom{n}{k} = \frac{k}{n}\frac{n!}{k!\,(n-k)!} = \frac{(n-1)!}{(k-1)!\,((n-1)-(k-1))!} = \binom{n-1}{k-1}.$$
$$ 2^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} = \sum_{k=1}^{n} \binom{n-1}{k-1} = \sum_{k=1}^{n} \frac{k}{n} \binom{n}{k}.$$
$$ \sum_{k=0}^{n} \frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1} \sum_{k=0}^{n} \binom{n+1}{k+1} = \frac{1}{n+1} \left(\sum_{k=0}^{n+1} \binom{n+1}{k} - \binom{n+1}{0}\right) = \frac{2^{n+1}-1}{n+1}.$$
$$ \binom{n-1}{k-1}+\binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} = \frac{(n-1)!}{k!\,(n-k)!}(k+(n-k)) = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}.$$
$$ \binom{n}{i}\binom{i}{j} = \frac{n!}{i!\,(n-i)!}\frac{i!}{j!\,(i-j)!} = \frac{n!}{j!\,(n-j)!}\frac{(n-j)!}{(n-i)!\,((n-j)-(n-i))!} = \binom{n}{j}\binom{n-j}{i-j}.$$
$p\in\mathbb{N}$を素数，$\mathbb{A}$を標数$p$の単位的可換環とし，$a,b\in\mathbb{A}$とする．このとき，各$k\in\{1,\ldots,p-1\}$に対して
$$
k\binom{p}{k} = p\binom{p-1}{k-1}$$
より$\binom{p}{k}$は$p$の倍数なので，
$$
(a+b)^{p} = \sum_{k=0}^{p} \binom{p}{k} a^{k}b^{p-k} = \binom{p}{0} a^{0}b^{p} + \binom{p}{p} a^{p}b^{0} = a^{p}+b^{p}$$
が成り立つ（cf. binom-exp）．
$$ [k,\ell] = \binom{k+\ell}{k} = \frac{(k+\ell)!}{k!\,\ell!} = \frac{(\ell+k)!}{\ell!\,k!} = \binom{\ell+k}{\ell} = [\ell,k].$$
任意の自然数$n,m\in\mathbb{N}$に対して，
\begin{align}
\sum_{k=0}^{n+m} \binom{n+m}{k} x^{k}
&= (x+1)^{n+m} \\
&= (x+1)^{n}(x+1)^{m} \\
&= \left(\sum_{i=0}^{n} \binom{n}{i} x^{i} \right) \left(\sum_{j=0}^{m} \binom{m}{j} x^{j} \right) \\
&= \sum_{k=0}^{n+m} \sum_{i+j=k} \binom{n}{i}\binom{m}{j} x^{k} \\
\end{align}
より，
$$
\forall\,k \in \{0,\ldots,n+m\},\ \binom{n+m}{k} = \sum_{i+j=k} \binom{n}{i}\binom{m}{j}$$
が成り立つ．とくに，$k=n$として
$$
\binom{n+m}{n} = \sum_{i+j=n} \binom{n}{i}\binom{m}{j}$$
を得，さらに$n=m$として
$$
\binom{2n}{n} = \sum_{i+j=n} [i,j][j,i] = \sum_{i+j=n} [i,j]^{2}$$
を得る．
$k,m \in \mathbb{Z}_{\geq 1}$とする．このとき，
$$
k(k+1) \cdots (k+m-1) = \frac{(k+m-1)!}{(k-1)!} = m!\binom{k+m-1}{m} = m![m,k-1]$$
であるから，連続する$m$個の自然数の積は$m!$で割り切れる．
$m\in\mathbb{Z}_{\geq 1}$とすると，pascalより
$$
\sum_{k=0}^{n} [m,k] = \sum_{k=0}^{n} ([m+1,k]-[m+1,k-1]) = [m+1,n]$$
であるから，
\begin{align}
\sum_{k=1}^{n} k(k+1) \cdots (k+m-1)
&= m! \sum_{k=1}^{n} [m,k-1] \\
&= m! \sum_{k=0}^{n-1} [m,k] \\
&= m![m+1,n-1] \\
&= m! \frac{(m+n)!}{(m+1)!\,(n-1)!} \\
&= \frac{n(n+1) \cdots (n+m)}{m+1}
\end{align}
が成り立つ．
上例より
$$
\sum_{k=1}^{n} k = \frac{n(n+1)}{2},\ \sum_{k=1}^{n} k(k+1) = \frac{n(n+1)(n+2)}{3}$$
であるから，
\begin{align}
\sum_{k=1}^{n} k^{2}
&= \sum_{k=1}^{n} (k(k+1)-k) \\
&= \frac{n(n+1)(n+2)}{3} - \frac{n(n+1)}{2} \\
&= \frac{n(n+1)}{6}(2(n+2)-3) \\
&= \frac{n(n+1)(2n+1)}{6}
\end{align}
が成り立つ．同様にして
\begin{align}
\sum_{k=1}^{n} k^{3}
&= \sum_{k=1}^{n} (k(k+1)(k+2) - 3k(k+1) + k) \\
&= \frac{n(n+1)(n+2)(n+3)}{4} - n(n+1)(n+2) + \frac{n(n+1)}{2} \\
&= \frac{n(n+1)}{4} ((n+2)(n+3)-4(n+2)+2) \\
&= \frac{n(n+1)}{4}((n+2)(n-1)+2) \\
&= \left(\frac{n(n+1)}{2} \right)^{2} \\
&= \left(\sum_{k=1}^{n} k \right)^{2}
\end{align}
を得る．
正整数$n\in\mathbb{Z}_{\geq 1}$に対して
$$
\bar{n} \coloneqq \{1,\ldots,n\}$$
とおく．各$k \in \{1,\ldots,n\}$に対して，$n$次対称群$\mathfrak{S}_{n}$は集合
$$
\mathcal{P}_{k}(\bar{n}) \coloneqq \{K \subset \bar{n} \mid \#K = k\}$$
に推移的に作用する：
$$
\sigma \cdot K \coloneqq \sigma[K].$$
部分集合$\bar{k}\in\mathcal{P}_{k}(\bar{n})$の安定化群について
$$
\{\sigma\in\mathfrak{S}_{n} \mid \sigma[\bar{k}] = \bar{k}\} \cong \mathfrak{S}_{k} \times \mathfrak{S}_{n-k}$$
が成り立つので，Orbit–Stabilizer Theorem より
$$
\#\mathcal{P}_{k}(\bar{n}) = \frac{\#\mathfrak{S}_{n}}{\#\mathfrak{S}_{k} \times \#\mathfrak{S}_{n-k}} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}$$
を得る．
