階乗の復習から多項分布の導出まで

$r$ を正の整数とする。第$1$位置に置く要素は、集合の中から任意の$1$つを選べるので $r$ 通り。
第$2$位置に置く要素は、残りの $r-1$ 個から任意に選べるので $r-1$ 通り。
同様に、第 $k$ 位置には残りの $r-(k-1)$ 個から選ぶので $r-k+1$ 通り。
最終的に第 $r$ 位置には $r - (r-1) = 1$ 通り しか選択肢がない。
$ $
各段階での選択肢の数は、それ以前に何を選んだかに依らず一定である。
すなわち、第$1$段階で何を選んでも、第$2$段階の選択肢の数は変わらないため、乗法原理より
$$ r \times (r-1)\times (r-2)\times \cdots \times 1 \;=\;r! $$
が全並べ方の総数となる。
$$ \Box$$

$n,r$を整数とし、$1 \le r \le n$とする。
$ $
$n$個の異なるものから $r$ 個を順番に選んで並べるとき、
最初に何を選び、次に何を選ぶかというように段階的に考える。

1. 第$1$段階
   最初の$1$個を選ぶとき、選べるのは $n$ 個のうちのどれかであるから、$n$ 通り
2. 第$2$段階
   次に$1$個選ぶときは、すでに$1$個使っているので、残りは $n - 1$ 個
3. 第$3$段階
   次に$1$個選ぶときは、すでに$2$個使っているので、残りは $n - 2$ 個
   $$ \vdots $$
4. 第$r$段階
   最後に $r$ 個目を選ぶときは、残りは $n - (r - 1) = n - r + 1$ 個

-よって、これらは連続した選択の段階であり、各段階での場合の数を掛け合わせればよい（乗法原理）。
すなわち、$r$個を順番に選ぶ方法の総数は、
$$ n \times (n - 1) \times (n - 2) \times \cdots \times (n - r + 1) $$
これを階乗によって表すと、$n!$ の前から $r$ 個だけ掛け合わせたものに等しい。すなわち、
$$ \frac{n!}{(n - r)!} $$
である。
$$ \Box$$

$X$ を「$S$ の要素を重複なく並べた長さ $r$ の列（順列）」全体の集合とする。すなわち、
$$ X=\{(a_1,\dots,a_r)\in S^r\mid a_i\neq a_j\ (i\neq j)\} $$
とすると、集合$X$ の要素数は、順列の定義から
$$ |X| := P(n,r)\quad $$
である。次に、$Y$ を「$S$ の $r$ 要素部分集合全体の集合」とする。すなわち、
$$ Y=\{A\subseteq S\mid \#A=r\} $$
いま、集合$Y$の要素数を
$$ |Y| := \binom{n}{r} $$
で表す。ここで、写像
$$ f : X \to Y, \quad f(a_1,\dots,a_r) = \{a_1,\dots,a_r\} $$
を考える。
すると、任意の $A\in Y$ に対して、$A$ は相異なる $r$ 個の元からなるので、$A$ の元を並べて得られる順序付き $r$ 組はちょうど $ r!$ 通りある。
従って
$$ |f^{-1}(A)|=r! $$
である。よって
$$ |X| = \sum_{A \in Y} |f^{-1}(A)| = \sum_{A \in Y} r! = r! \cdot |Y| $$
すなわち
$$ P(n,r) = r! \binom{n}{r} $$
これを解いて
$$ \binom{n}{r} = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!} $$
を得る。
$$ \Box$$

全 $n$ 個の位置から $p_1$ 個を選んで種類 $1$ の要素を置く方法は
$$ \binom{n}{p_1} $$
通り。残り $n-p_1$ 個の位置から $p_2$ 個を選んで種類 $2$ を置く方法は
$$ \binom{n-p_1}{p_2} $$
通り。この操作を順次繰り返していくと、積の法則により総数は
$$ \binom{n}{p_1}\binom{n-p_1}{p_2}\binom{n-p_1-p_2}{p_3}\dotsm\binom{p_d}{p_d} $$
組み合わせの定義
$$ \displaystyle\binom{m}{k}:=\frac{m!}{k!\,(m-k)!} $$
を用いて順に展開し、分子同士・分母同士を整理すると
$$ \frac{n!}{p_1!\,(n-p_1)!}\cdot\frac{(n-p_1)!}{p_2!\,(n-p_1-p_2)!}\cdot\ldots\cdot\frac{p_d!}{p_d!\,0!} =\frac{n!}{p_1!\,p_2!\,\dotsm p_d!} $$
を得る。
$$ \Box$$

試行の結果列全体の集合を
$$ \Omega=\{1,2,\ldots,k\}^n $$
とする。ここで $\omega=(\omega_1,\ldots,\omega_n)\in\Omega$ とし、各 $j=1,\ldots,n$ について、$\omega_j\in\{1,\ldots,k\}$ は第 $j$ 回目の試行結果を表す。
また、第 $1$ 回の試行で結果 $i$ が起こる確率を $p_i$ とする。すなわち、第 $j$ 回目の試行で結果が $\omega_j$ となる確率は $p_{\omega_j}$ である。
$ $
すると、$n$ 回の試行が独立であるから、特定の結果列 $\omega=(\omega_1,\ldots,\omega_n)$ が起こる確率は
$$ P(\{\omega\})=\prod_{j=1}^n p_{\omega_j} $$
で与えられる。

各$i=1,\ldots,k$ に対し、$\omega\in\Omega$ から得られる出現回数を
$$ X_i(\omega)=\#\{j\in\{1,\ldots,n\}\mid \omega_j=i\} $$
で定める。定義より
$$ X_1(\omega)+\cdots+X_k(\omega)=n $$
が成り立つ。
$ $
そこで、任意に $(x_1,\ldots,x_k)\in\mathbb{Z}_{\ge0}^k$ をとる。

1. まず $x_1+\cdots+x_k\ne n$ のときを考える。
   このとき任意の $\omega\in\Omega$ について $X_1(\omega)+\cdots+X_k(\omega)=n$ であるから
   $$ \{\omega\in\Omega\mid X_1(\omega)=x_1,\ldots,X_k(\omega)=x_k\}=\varnothing $$
   となり、$P(\varnothing)=0$より
   $$ P(X_1=x_1,\ldots,X_k=x_k)=0 $$
   である。
2. 次に $x_1+\cdots+x_k=n$ のときを考える。
   事象
   $$ E=\{\omega\in\Omega\mid X_1(\omega)=x_1,\ldots,X_k(\omega)=x_k\} $$
   を定める。

1. 任意の $\omega\in E$ に対し $P(\{\omega\})=p_1^{x_1}\cdots p_k^{x_k}$ が成り立つことを示す。
   実際、$\omega\in E$ ならば結果 $i$ はちょうど $x_i$ 回現れるので、独立性の仮定から
   $$ P(\{\omega\})=\prod_{j=1}^n p_{\omega_j}=p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k} $$
   となる。
2. $|E|=\dfrac{n!}{x_1!\cdots x_k!}$ を示す。
   $1$ から $n$ までの位置に対し，結果 $1$ が現れる位置を $x_1$ 個選ぶ方法は $\binom{n}{x_1}$ 通りである。
   次に残り $n-x_1$ 個の位置から，結果 $2$ が現れる位置を $x_2$ 個選ぶ方法は $\binom{n-x_1}{x_2}$ 通りである。
   同様に続けると
   $$ |E|=\binom{n}{x_1}\binom{n-x_1}{x_2}\cdots\binom{n-(x_1+\cdots+x_{k-1})}{x_k} $$
   である。すなわち、
   $$ |E| =\frac{n!}{x_1!(n-x_1)!}\cdot \frac{(n-x_1)!}{x_2!(n-x_1-x_2)!}\cdot \frac{(n-x_1-x_2)!}{x_3!(n-x_1-x_2-x_3)!}\cdots \frac{(n-(x_1+\cdots+x_{k-1}))!}{x_k!(n-(x_1+\cdots+x_k))!} $$
   ここで $x_1+\cdots+x_k=n$ だから最後の分母は
   $$ (n-(x_1+\cdots+x_k))!=0!=1 $$
   となる。また、これらを約分すると、中間の階乗が相殺され
   $$ |E|=\frac{n!}{x_1!\,x_2!\cdots x_k!} $$
   を得る。
   $ $

-以上より確率を計算する。
$E$ は互いに素な単集合の和であり、(1) より各 $\omega\in E$ で $P(\{\omega\})$ は同じなので
$$ \begin{aligned} P(X_1=x_1,\ldots,X_k=x_k) &=P(E) =\sum_{\omega\in E}P(\{\omega\}) \\ &=\sum_{\omega\in E}p_1^{x_1}\cdots p_k^{x_k} =|E|\;p_1^{x_1}\cdots p_k^{x_k} \\ &=\frac{n!}{x_1!\cdots x_k!}\,p_1^{x_1}\cdots p_k^{x_k} \end{aligned} $$
となる。
$ $
従って
$$ P(X_1=x_1,\ldots,X_k=x_k)= \begin{cases} \dfrac{n!}{x_1!\cdots x_k!}\,p_1^{x_1}\cdots p_k^{x_k} & (x_1+\cdots+x_k=n),\\ 0 & (x_1+\cdots+x_k\ne n) \end{cases} $$
が成り立つ。
$$ \Box$$