同じものを含む順列（最短経路の問題はここにつながる）

同じ文字が混ざった並べ替えでは、全部を区別して数えると多すぎる答えが出ます。A、A、B、B の 4 文字なら $4!=24$ ではなく 6 通り。

多すぎるぶんをどう割るかが、この単元のすべてです。そして同じ考え方が、そのまま格子の最短経路の数え上げになる。

まず区別してから割る

$n$ 個のものを並べる並べ方は $n!$ 通りでした。この数え方は、同じに見えるものにも別の名前が付いているときの答えです。

同じものが $p$ 個あると、その $p$ 個を入れ替えた $p!$ 通りが、見た目では 1 つの並びに重なります。だから $p!$ で割る。

種類ごとに同じことが起きるので、種類の数だけ割り算が並びます。

$$\frac{n!}{p!q!r!\cdots }$$

分母の $p$、$q$、$r$ は各文字の個数で、足すと $n$ になる。これが同じものを含む順列の公式です^[1]。

例：A、A、B、B を並べる

$4!=24$ から始めます。2 つの A に仮の番号を付けて $A_1$、$A_2$ とし、B も同じように分けたとする。

$A_1{A}_2{B}_1{B}_2$ と $A_2{A}_1{B}_1{B}_2$ は、番号を消すとどちらも AABB です。A の入れ替えで 2 通り、B の入れ替えで 2 通りが重なる。

$$\frac{4!}{2!2!}=\frac{24}{4}=6$$

6 通りになります。書き出すと AABB、ABAB、ABBA、BAAB、BABA、BBAA。

例：MISSISSIPPI

英語の綴りで有名な例です。11 文字で、M が 1 個、I が 4 個、S が 4 個、P が 2 個。

$$\frac{11!}{1!4!4!2!}=34650$$

34650 通りの並べ替えができます^[1]。$11!=39916800$ からの割り算なので、1000 分の 1 以下まで減る。

例：TOMATO

6 文字で、T が 2 個、O が 2 個、M と A が 1 個ずつ。

$$\frac{6!}{2!2!}=\frac{720}{4}=180$$

1 個しかない文字については $1!=1$ なので、書いても書かなくても値は変わりません。

もう一つの導き方：場所を選ぶ

割り算を使わずに、置き場所を選ぶ形でも同じ答えが出ます。

4 つの席のうち A が座る席を 2 つ選ぶと ${}_4{\mathrm{C}}_2=6$ 通り。残った 2 席には B が入るしかないので、そこで並びが決まる。

$${}_4{\mathrm{C}}_2\times {}_2{\mathrm{C}}_2=6\times 1=6$$

割り算の答えと一致します。3 種類あるときも同じで、選んでは残りから選ぶ、を繰り返す。

この見方は、あとで出てくる最短経路とそのままつながります。どの場所を「上へ進む」に使うかを選ぶ話になるため。

例：赤玉 3 個と白玉 2 個

同じ色の玉は区別しないとして、5 個を一列に並べます。

$$\frac{5!}{3!2!}=10$$

場所を選ぶ見方なら、5 か所から赤の 3 か所を選んで ${}_5{\mathrm{C}}_3=10$ 通り。2 種類しかないときは、組み合わせの数そのものになる。

例：先頭に 0 を置けない場合

0、1、1、2、2 の 5 枚のカードを並べて 5 桁の整数を作ります。

制限を無視すると $\frac{5!}{1!2!2!}=30$ 通り。このうち先頭が 0 のものを引きます。

先頭が 0 なら、残りの 1、1、2、2 を並べる $\frac{4!}{2!2!}=6$ 通り。

$30-6=24$ 通りになります。制限付きは、全体から外れるものを引くほうが速い。

最短経路の数え方

碁盤の目の道を、左下から右上まで最短で行きます。遠回りをしないので、進む向きは右か上のどちらかだけ。

右へ 3 区画、上へ 2 区画の格子なら、進む回数は必ず 5 回です。その 5 回のうち、どこで上へ曲がるかを選べば道が決まる。

つまり「右右右上上」という 5 文字の並べ替えと、道が 1 対 1 に対応します。

$$\frac{5!}{3!2!}={}_5{\mathrm{C}}_2=10$$

10 通りです。同じものを含む順列と最短経路は、同じ問題の言いかえになっている^[2]。

図の文字列がそのまま道の指示になっています。「右右右上上」の並べ替えを 10 通り作れば、道も 10 本そろう。

一般に右へ $a$ 区画、上へ $b$ 区画なら、最短経路は ${}_{a+b}{\mathrm{C}}_a$ 通りです^[2]。

例：4 かける 3 の格子

右へ 4、上へ 3 進む格子で数えます。全部で 7 回進むうち、上へ進む 3 回を選ぶ。

$${}_7{\mathrm{C}}_3=35$$

35 通りになります。$\frac{7!}{4!3!}$ と書いても同じ値。

交点に数を書き込む

公式を使わずに数える方法もあります。各交点まで何通りで来られるかを、左下から順に書き込んでいく。

ある交点へは、左の点か下の点からしか来られません。だからその交点の数は、左と下の数の和になる。

左下から順に埋めると、右上に 35 が出ます。公式の値と一致した。

書き込み法は、道が欠けている問題で強い。使えない交点を 0 にしてから、同じ手順を続ければよいだけです。

例：ある交点を必ず通る

右へ 4、上へ 3 の格子で、途中の点 P を必ず通る道を数えます。P は左下から右へ 2、上へ 1 の位置とする。

前半と後半に分けます。前半は右 2 と上 1 で ${}_3{\mathrm{C}}_1=3$ 通り。

後半は P から右へ 2、上へ 2 なので ${}_4{\mathrm{C}}_2=6$ 通り。

前半のどの道を選んでも後半は 6 通りなので、掛けて $3\times 6=18$ 通り。

例：ある交点を通れない

同じ格子で、点 P が工事中で通れないとします。

全体の 35 通りから、P を通る 18 通りを引きます。$35-18=17$ 通り。

「通らない」を直接数えると場合分けが増える。全体から引く形に持ち込むほうが短くなります。

例：道が 1 本使えない

右へ 4、上へ 3 の格子で、真ん中あたりの横 1 区画が通行止めだとします。その区画の左端を A、右端を B とする。

始点から A までが右 2 上 1 で 3 通り、B から終点までが右 1 上 2 で 3 通り。

その道を通る経路は $3\times 3=9$ 通りです。全体から引いて $35-9=26$ 通り。

二項係数との関係

書き込み法で出てくる数の並びは、パスカルの三角形を斜めに置いたものです。

左と下を足すという規則が、${}_n{\mathrm{C}}_r={}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$ にあたる。同じ規則が、格子の上では経路の数え上げとして現れる。

例：階段の上り方との違い

1 段または 2 段ずつ上って 5 段を上る方法は 8 通りですが、これは最短経路の公式では出ません。

進む回数が決まっていないため。1 段を 5 回、2 段を 1 回と 1 段を 3 回、と場合分けが要ります。

合計 8 通りです。各行は同じものを含む順列で、$\frac{4!}{1!3!}=4$、$\frac{3!}{2!1!}=3$ と計算する。

歩数がそろっていない問題では、まず回数で場合分けする。そのうえで各場合に公式を当てます。

例：立体の格子

縦、横、高さの 3 方向に進む場合も同じです。右へ 2、奥へ 2、上へ 1 なら、5 回の進み方の並べ替えになる。

$$\frac{5!}{2!2!1!}=30$$

30 通り。方向が 3 種類に増えても、分母が 1 つ増えるだけで考え方は変わらない。

例：同じ数字を含む整数

1、1、1、2、2 の 5 枚を並べてできる 5 桁の整数を数えます。

$$\frac{5!}{3!2!}=10$$

10 個です。先頭に 0 がないので、引き算は要りません。

これを小さい順に書き出すと 11122、11212、11221、12112、12121、12211、21112、21121、21211、22111 の 10 個。数えた値と合っている。

よくある誤り

どれも、何を並べ替えているのかを言葉にすれば防げます。並べる対象と、その個数を先に書き出す。

参考文献

^[1] は多重集合の順列の公式と MISSISSIPPI の例、^[2] は格子路の数え方、^[3] から ^[5] は各国語での公式のまとめです。