メモ

アルゴリズムパズルの初級13を解くときに、これって確か重複組合せで解くんだよなあって思いつつ、中身を思い出すのに相当手間取ってしまったので、書けば覚える式に記事にしてしまいます。

重複組合せ

$n$種のものから重複を許して（つまり毎回元に戻して）$r$個取り出す組合せのことで、その総数を $nH_r$ と表し、${n+r-1}C_r$ と等しくなります（Wikipedia）。組合せなので順序は問いません。

ちなみに、順序を問う場合は、重複順列といって、総数は単純に $n^r$ となります。

$nH_r＝{n+r-1}C_r$ であることは、次のように説明できます。

$n$種のものから重複を許して$r$個取り出すとは、箱を一列にピタっと$n$個並べておいて、$r$個のボールを重複を許してそれらの箱に入れる組合せのことです。これは見方を変えると、$r$個のボールと$n-1$個のパーティションを1列に並べるときの、並べ方の組合せと見ることができます。$n=8, r=10$ だと次のような並びを含むすべての組合せを考えることになります。

|OOO||OOOO|||OO|O

もし、ボールとパーティションにすべて区別があれば、1列に並べる並べ方（順列）の総数は、$(n+r-1)!$ となります。しかし、ボールどうしには区別はなく、パーティションどうしにも区別はありません。そのためこの総数を $r!$ と、$(n-1)!$ で割れば、組合せの総数が出ます。

つまり、$nH_r=\frac{(n+r-1)!}{r!(n-1)!}$ となり、これは ${n+r-1}C_r$ と同じものになるわけです。

応用

碁盤の目状に東西と南北に道路が並んでいる都市があり、そのある交差点Aにいるとします。ここから、$n$ブロック東、$m$ブロック南の交差点Bに行く最短経路は何通りあるかという問題がよくあります。

この場合、AからBに到達するまでに、南北の道路$n+1$本のいずれかで、ちょうど$m$回南進しないといけません。重複してもいいですが、南進する順序は西から東しかないので、その順列には意味はなく組合せさえ決まれば経路が一意に決まります。つまり、$n+1$本の道路から重複を許して$m$本選ぶ組合せになるわけです。

したがって、この組合せの総数は $_{n+1}H_m = _{n+m}C_m$ と得られます。

アルゴリズムパズルの初級13は交差点の1箇所に通行止めがあるという問題ですが、この応用で解くと、とても簡単に求めることができます。詳細は、宿題に残しておきます。

本の中の解答例では組合せの考え方を使わずにアルゴリズミックに解いています。通行止めの箇所やパターンが非常に多くなってくるとその方がいいかもしれません。