多項係数

1 と 2 と 3 の対応。 $f\in W(k)$ に $(f^{-1}(1),\dots,f^{-1}(m))$ を対応させると、2 の集合への写像になる。逆に 2 の組 $(B_1,\dots,B_m)$ が与えられると、各 $j\in[n]$ を含む $B_i$ はただ 1 つなので、$f(j):=i$ で $f\in W(k)$ が定まる。この 2 つの対応は互いに逆であり、1 と 2 の集合は全単射で結ばれる。また $f\in W(k)$ に語 $a_{f(1)}a_{f(2)}\cdots a_{f(n)}$ を対応させると、$a_i$ の個数は $\lvert f^{-1}(i)\rvert=k_i$ であり、語の $j$ 文字目が $a_i$ のとき $f(j)=i$ とおけば逆の対応になる。よって 1 と 3 も全単射で結ばれる。
2 の個数と積の公式。 2 の組を $B_1,B_2,\dots$ の順に選ぶ。$B_1,\dots,B_{i-1}$ を選んだあと、残りの集合 $R_i:=[n]\setminus(B_1\cup\cdots\cup B_{i-1})$ は $n-s_{i-1}$ 個の元をもち、$B_i$ は $R_i$ の $k_i$ 元部分集合であればよい。その選び方は、それまでの選び方によらず $\binom{n-s_{i-1}}{k_i}$ 通りある。最後の $B_m$ は $\lvert R_m\rvert=n-s_{m-1}=k_m$ なので $B_m=R_m$ に限られ、このとき和集合は $[n]$ になる。逆に 2 の組はどれもこの手順で得られる。$m$ についての帰納法でこの数え方を正確にすると、2 の集合の元の個数は $\prod_{i=1}^m\binom{n-s_{i-1}}{k_i}$ である。ここで
$$ \binom{n-s_{i-1}}{k_i}=\frac{(n-s_{i-1})!}{k_i!\,(n-s_{i-1}-k_i)!}=\frac{(n-s_{i-1})!}{k_i!\,(n-s_i)!} $$
なので、積をとると分子と分母の $(n-s_1)!,\dots,(n-s_{m-1})!$ が打ち消し合い、
$$ \prod_{i=1}^m\binom{n-s_{i-1}}{k_i}=\frac{(n-s_0)!}{k_1!\cdots k_m!\,(n-s_m)!}=\frac{n!}{k_1!\cdots k_m!} $$
を得る（$s_0=0$、$(n-s_m)!=0!=1$）。
4 の個数。 $S_n$ は $W(k)$ に $\sigma\cdot f:=f\circ\sigma^{-1}$ で（左から）作用する。実際 $(\sigma\tau)\cdot f=f\circ\tau^{-1}\circ\sigma^{-1}=\sigma\cdot(\tau\cdot f)$ であり、$(f\circ\sigma^{-1})^{-1}(i)=\sigma(f^{-1}(i))$ は $f^{-1}(i)$ と同じ個数の元をもつので $\sigma\cdot f\in W(k)$ である。
この作用は推移的である。$f,g\in W(k)$ をとる。各 $i$ について $\lvert f^{-1}(i)\rvert=\lvert g^{-1}(i)\rvert=k_i$ なので、全単射 $f^{-1}(i)\to g^{-1}(i)$ がとれる。$[n]$ は $f^{-1}(1),\dots,f^{-1}(m)$ に分かれ、$g^{-1}(1),\dots,g^{-1}(m)$ にも分かれるので、これらをつなぐと $\sigma\in S_n$ で $\sigma(f^{-1}(i))=g^{-1}(i)$（すべての $i$）となるものが得られる。$f(j)=i$ なら $\sigma(j)\in g^{-1}(i)$ なので $g(\sigma(j))=f(j)$、すなわち $g\circ\sigma=f$ であり、$g=f\circ\sigma^{-1}=\sigma\cdot f$ となる。
$f_0\in W(k)$ を、$s_{i-1}< j\le s_i$ のとき $f_0(j):=i$ で定める。$\sigma\cdot f_0=f_0$ は $f_0\circ\sigma^{-1}=f_0$、すなわち $\sigma^{-1}$（したがって $\sigma$）が各ブロック $f_0^{-1}(i)=\{s_{i-1}+1,\dots,s_i\}$ をそれ自身に写すことと同値である。よって $f_0$ の安定化群は $H_k$ である。群の作用 の系「推移的な作用と剰余類」により、$\sigma H_k\mapsto\sigma\cdot f_0$ は $S_n/H_k$ から $W(k)$ への全単射である。
以上で 4 つの集合の元の個数がすべて等しく、その値が $n!/(k_1!\cdots k_m!)$ であることが示された。個数は正の整数である（$f_0\in W(k)$ なので $W(k)$ は空でない）。$\square$

分配法則を $n$ 回使うと、$n$ についての帰納法により
$$ (x_1+\cdots+x_m)^n=\sum_{f\colon[n]\to[m]}x_{f(1)}x_{f(2)}\cdots x_{f(n)} $$
となる（$n=0$ では右辺は空写像だけの和で、空の積 $1$ に等しい。$n$ から $n+1$ へは、両辺に右から $x_1+\cdots+x_m$ を掛け、$f$ を $f(n+1)$ の値で延ばす）。$x_i$ はどの 2 つも可換なので、積 $x_{f(1)}\cdots x_{f(n)}$ の因子を並べ替えて $x_1^{k_1}\cdots x_m^{k_m}$（$k_i:=\lvert f^{-1}(i)\rvert$）にできる。$k_1+\cdots+k_m=n$ である。写像 $f$ を $(k_1,\dots,k_m)$ ごとにまとめると、同じ組 $k$ を与える $f$ の全体は $W(k)$ であり、その個数は thm-mc-count により $\binom{n}{k_1,\dots,k_m}$ である。$\square$

要点：前半は cor-mc-multinomial-theorem で $x_1=\cdots=x_m=1$ とおけばよい。後半は、組 $(k_1,\dots,k_m)$ を $n$ 個の「$\circ$」と $m-1$ 個の仕切りの列に対応させて数える。

要点：$k_i\ge1$ なら $\binom{n-1}{k_1,\dots,k_i-1,\dots,k_m}=\frac{k_i}{n}\binom{n}{k_1,\dots,k_m}$ であり、$i$ について足すと $k_1+\cdots+k_m=n$ から主張が出る。

要点：1 は $n!=\binom{n}{k_1,\dots,k_m}\prod_ik_i!$ の両辺の付値に Legendre の公式の桁の和の形を使う。2 は、繰り上がりがやがて $0$ になることを確かめたうえで、筆算の各桁の等式を足し合わせると $\sum_is_p(k_i)-s_p(n)=(p-1)\sum_jc_j$ になることによる。

thm-mc-valuation の 2 により、$p\nmid\binom{n}{k_1,\dots,k_m}$ はすべての $c_j=0$ と同値である。すべての $c_j=0$ なら定義式から $\sum_ik_{i,(j)}=d_j\le p-1$ である。逆にすべての桁で $\sum_ik_{i,(j)}\le p-1$ なら、$c_{-1}=0$ から始めて、$c_{j-1}=0$ ならば左辺が $p-1$ 以下なので $c_j=0$ となり、帰納法ですべての $c_j=0$ である。$\square$

$\omega=(\omega_1,\dots,\omega_n)\in\Omega$ を写像 $[n]\to[m]$、$t\mapsto\omega_t$ と見ると、事象 $\{N_1=k_1,\dots,N_m=k_m\}$ はちょうど $W(k)$ である。$\omega\in W(k)$ では、積 $p_{\omega_1}\cdots p_{\omega_n}$ に $p_i$ がちょうど $k_i$ 回現れるので $P(\{\omega\})=p_1^{k_1}\cdots p_m^{k_m}$ であり、どの $\omega\in W(k)$ でも同じ値である。thm-mc-count により $\lvert W(k)\rvert=\binom{n}{k_1,\dots,k_m}$ なので主張を得る。総和は cor-mc-multinomial-theorem により $(p_1+\cdots+p_m)^n=1$ である。$\square$