同じものを含む順列と多項定理

A, A, B を一列に並べる方法を書き出すと
$$ AAB,\qquad ABA,\qquad BAA $$
の $3$ 通りである。B の位置（1 番目・2 番目・3 番目）を決めれば、残りの 2 か所には A が入るので、並べ方は B の位置の選び方 $3$ 通りと同じ数になる。

MISSISSIPPI の 11 文字は、M が $1$ 個、I が $4$ 個、S が $4$ 個、P が $2$ 個である（$1+4+4+2=11$）。これらを一列に並べる方法は
$$ \frac{11!}{1!\,4!\,4!\,2!}=\frac{39916800}{1\cdot24\cdot24\cdot2}=\frac{39916800}{1152}=34650 $$
通りである。

$(x+y+z)^5$ を展開したときの $x^2yz^2$ の係数を求める。$(x+y+z)^5$ は 5 個の因数 $(x+y+z)$ の積である。各因数から $x,y,z$ のどれか 1 つを選んで掛けたものを全部足すと、展開した式になる。$x^2yz^2$ ができるのは、5 個の因数のうち 2 個から $x$、1 個から $y$、2 個から $z$ を選んだときである。「どの因数から何を選ぶか」は、$x,x,y,z,z$ の 5 文字を因数の番号順に並べることと同じなので、その数は
$$ \frac{5!}{2!\,1!\,2!}=\frac{120}{4}=30 $$
である。よって係数は $30$ である。

1. $\dbinom{4}{2,1,1}=\dfrac{4!}{2!\,1!\,1!}=\dfrac{24}{2}=12$。
2. $\dbinom{5}{2,3}=\dfrac{5!}{2!\,3!}=10=\dbinom52$。
3. $\dbinom{6}{2,2,2}=\dfrac{720}{2\cdot2\cdot2}=90$。
4. $\dbinom{3}{3,0,0}=\dfrac{3!}{3!\,0!\,0!}=1$。$0$ 個の文字は並べ方に影響しないので、$A,A,A$ の並べ方 $1$ 通りと一致する。

A を 2 個、B を 3 個並べる。5 か所のうち A を置く 2 か所を選べば、残りの 3 か所は B で埋まる。よって並べ方は
$$ \binom52=10 $$
通りである。定理の式 $\dfrac{5!}{2!\,3!}=\dfrac{120}{12}=10$ と一致する。

A を 2 個、B と C を 1 個ずつ並べる。4 か所から A の 2 か所を選ぶ方法が $\dbinom42=6$ 通り、残り 2 か所から B の 1 か所を選ぶ方法が $\dbinom21=2$ 通り、最後の 1 か所は C である。よって $6\times2=12$ 通りで、$\dfrac{4!}{2!\,1!\,1!}=12$ と一致する。

2 つの A に番号を付けて $A_1,A_2$ とすると、$A_1,A_2,B$ は異なる 3 文字なので、並べ方は $3!=6$ 通りある。
$$ A_1A_2B,\quad A_2A_1B,\quad A_1BA_2,\quad A_2BA_1,\quad BA_1A_2,\quad BA_2A_1 $$
番号を消すと、はじめの 2 つは $AAB$、次の 2 つは $ABA$、最後の 2 つは $BAA$ になる（図 1）。番号を消した並べ方 1 つにつき、番号を付けた並べ方がちょうど $2!=2$ 個ずつあるので、番号を消した並べ方は $6\mathbin{÷}2=3$ 通りである。これは ex-mc-aab の答えと一致する。

小さな例で、番号付きの並べ方 $n!$、かたまりの大きさ $k_1!\cdots k_m!$、同じものを含む順列の数を比べる。

A A B B の 6 通りは $AABB$、$ABAB$、$ABBA$、$BAAB$、$BABA$、$BBAA$ である。表の数は、すべて全部の並べ方を書き出して確かめた。

$(a+b+c)^2=(a+b+c)(a+b+c)$ を分配法則で展開すると、1 つめの因数から 1 文字、2 つめの因数から 1 文字を選んで掛けた $3\times3=9$ 個の項の和になる。選んだ文字を順に書くと
$$ aa,\ ab,\ ac,\ ba,\ bb,\ bc,\ ca,\ cb,\ cc $$
である。掛け算の順序は入れ替えてよいので、$ab$ と $ba$ はどちらも $ab$ になる。$ab$ になるのは、$a,b$ の 2 文字の並べ方の数 $\dbinom{2}{1,1,0}=2$ 個である。$a^2$ になるのは $aa$ の $\dbinom{2}{2,0,0}=1$ 個である。まとめると
$$ (a+b+c)^2=a^2+b^2+c^2+2ab+2bc+2ca $$
で、よく知られた公式になる。係数の和は $1+1+1+2+2+2=9=3^2$ である。

$n=3$ のとき、$i+j+k=3$ をみたす組は 10 個ある。係数は

• $a^3,b^3,c^3$：$\dbinom{3}{3,0,0}=1$
• $a^2b,a^2c,ab^2,b^2c,ac^2,bc^2$：$\dbinom{3}{2,1,0}=\dfrac{6}{2}=3$
• $abc$：$\dbinom{3}{1,1,1}=6$
  である。よって
  $$ (a+b+c)^3=a^3+b^3+c^3+3(a^2b+a^2c+ab^2+b^2c+ac^2+bc^2)+6abc $$
  である。係数の和は $3\times1+6\times3+6=27=3^3$ である。係数を三角形に並べると図 2 のようになる。
  展開の項の個数、つまり $k_1+\cdots+k_m=n$ をみたす $0$ 以上の整数の組の個数は、$m$ 種類から重複を許して $n$ 個選ぶ 重複組合せ の数 ${}_m\mathrm{H}_n=\dbinom{n+m-1}{n}$ である（場合の数の数え方の体系）。$(a+b+c)^3$ では ${}_3\mathrm{H}_3=\dbinom{5}{3}=10$ で、上の「組は 10 個」と一致する。

$(2x-y+z)^4$ の展開における $x^2yz$ の係数を求める。多項定理で $a_1=2x$、$a_2=-y$、$a_3=z$ とすると、$(2x)^2(-y)^1z^1$ の項の係数は
$$ \binom{4}{2,1,1}\cdot2^2\cdot(-1)^1\cdot1^1=12\cdot4\cdot(-1)=-48 $$
である。$x^2yz$ になる項はこの 1 つだけなので、係数は $-48$ である。

$(1+x+x^2)^4$ の展開における $x^3$ の係数を求める。多項定理で $a_1=1$、$a_2=x$、$a_3=x^2$ とすると、項は $\dbinom{4}{k_1,k_2,k_3}x^{k_2+2k_3}$ である。$x^3$ になるのは
$$ k_1+k_2+k_3=4,\qquad k_2+2k_3=3 $$
をみたす組である。$k_3=0$ なら $k_2=3$、$k_1=1$。$k_3=1$ なら $k_2=1$、$k_1=2$。$k_3\ge2$ では $k_2+2k_3\ge4$ となって合わない。よって
$$ \binom{4}{1,3,0}+\binom{4}{2,1,1}=4+12=16 $$
である。1 つの組だけを見て $4$ や $12$ と答えると誤りになる。

多項定理で $a_1=\cdots=a_m=1$ とすると、左辺は $m^n$、右辺は多項係数の和なので
$$ \sum_{k_1+\cdots+k_m=n}\binom{n}{k_1,\dots,k_m}=m^n $$
である。$m=3$、$n=2$ では ex-mc-abc2 の $1+1+1+2+2+2=9$、$n=3$ では ex-mc-abc3 の $27$ である。数え上げで読むと、長さ $n$ の文字列（$m$ 種類の文字、同じ文字を何回使ってもよい）は全部で $m^n$ 個あり（場合の数の数え方の体系 の重複順列）、それを文字ごとの個数で分けて数えた式である。

1. $\dbinom{4}{2,1,1}=12$ を最後の文字で分けると
   $$ \binom{3}{1,1,1}+\binom{3}{2,0,1}+\binom{3}{2,1,0}=6+3+3=12 $$
   である。A, A, B, C の並べ方のうち、最後が A のものが 6 通り（前の 3 文字 A, B, C の並べ方）、最後が B のものが 3 通り（A, A, C の並べ方）、最後が C のものが 3 通り（A, A, B の並べ方）である。
2. $m=2$ では、$\dbinom{n}{k,\,n-k}=\dbinom{n-1}{k-1,\,n-k}+\dbinom{n-1}{k,\,n-k-1}$（$1\le k\le n-1$）となり、Pascal の関係 $\dbinom nk=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$ そのものである。

6 人を 2 人ずつ部屋 A, B, C に分ける。人 $1,\dots,6$ の入る部屋を順に書くと、A, B, C をちょうど 2 個ずつ含む長さ 6 の文字列になり、逆にそのような文字列から割り当てが 1 つ決まる。よって分け方は
$$ \binom{6}{2,2,2}=\frac{720}{8}=90 $$
通りである。
部屋に名前がなく、「どの 2 人が同じ部屋か」だけを考えるときは、2 人組 3 つへの分け方を数える。2 人組 3 つへの分け方を 1 つ決めると、3 つの組に部屋の名前 A, B, C を付ける方法が $3!=6$ 通りあり、どれも異なる割り当てになる（3 つの組は互いに異なる 2 人組なので、名前の付け方が違えば割り当ても違う）。よって、部屋を区別しない分け方は $90\mathbin{÷}6=15$ 通りである。全部の分け方を書き出しても $15$ 通りになる。

1. 6 人を 1 人・2 人・3 人の 3 組に分ける。組の大きさがすべて違うので、「1 人の組」「2 人の組」「3 人の組」は大きさで区別できる。部屋に名前を付けても付けなくても分け方は同じで、
   $$ \binom{6}{1,2,3}=\frac{720}{1\cdot2\cdot6}=60 $$
   通りである。ここで $3!$ で割ると $10$ になり、誤りである。
2. 6 人を 1 人・1 人・4 人の 3 組に分ける。名前の付いた部屋 A（1 人）、B（1 人）、C（4 人）への割り当ては $\dbinom{6}{1,1,4}=30$ 通りある。部屋に名前がないときは、1 人の組 2 つだけが入れ替え可能で、4 人の組は大きさで区別できる。よって $30\mathbin{÷}2!=15$ 通りである。
   どちらの数も、全部の分け方を書き出して確かめた。割る数は「大きさが等しい組どうしの入れ替えの数」であり、組の数の階乗とは限らない。

1. さいころを 6 回投げて、1 から 6 の目がちょうど 1 回ずつ出る確率は、$p_1=\cdots=p_6=\dfrac16$、$k_1=\cdots=k_6=1$ として
   $$ \binom{6}{1,1,1,1,1,1}\Bigl(\frac16\Bigr)^6=\frac{720}{46656}=\frac{5}{324}\approx0.0154 $$
   である。
2. 赤玉 3 個、白玉 2 個、青玉 1 個が入った袋から、1 個取り出して色を見て戻すことを 6 回くり返す。赤がちょうど 3 回、白が 2 回、青が 1 回出る確率は、$p=\dfrac12,\dfrac13,\dfrac16$ として
   $$ \binom{6}{3,2,1}\Bigl(\frac12\Bigr)^3\Bigl(\frac13\Bigr)^2\frac16=60\cdot\frac18\cdot\frac19\cdot\frac16=\frac{60}{432}=\frac{5}{36} $$
   である。

赤玉 2 個と白玉・青玉を 1 個ずつ並べる。赤玉 2 個が区別できないなら $\dbinom{4}{2,1,1}=12$ 通りである。しかし、2 個の赤玉に番号が書いてあって区別できるなら、4 個はすべて異なるので $4!=24$ 通りである。lem-mc-fiber で「番号を消す」操作が、ちょうど「区別しない」ことにあたる。何を同じとみなすかは問題の状況で決まり、それによって答えが変わる。

2 次の正方行列
$$ A=\begin{pmatrix}0&1\\ 0&0\end{pmatrix},\qquad B=\begin{pmatrix}0&0\\ 1&0\end{pmatrix} $$
を考える。行列の積を計算すると
$$ AB=\begin{pmatrix}1&0\\ 0&0\end{pmatrix},\qquad BA=\begin{pmatrix}0&0\\ 0&1\end{pmatrix},\qquad A^2=B^2=\begin{pmatrix}0&0\\ 0&0\end{pmatrix} $$
である。よって
$$ (A+B)^2=A^2+AB+BA+B^2=\begin{pmatrix}1&0\\ 0&1\end{pmatrix} $$
であるが、多項定理（$m=2$、$n=2$）の形の右辺は
$$ A^2+2AB+B^2=\begin{pmatrix}2&0\\ 0&0\end{pmatrix} $$
で、両者は等しくない。prf-mc-multinomial-words の段 2 で「$ab$ と $ba$ はどちらも $ab$」とまとめたところが、$AB\ne BA$ のために成り立たない。展開そのもの（段 1 の、長さ $n$ の文字列すべての和）は正しいが、同じ単項式にまとめることができない。