重複組み合わせとは？例を使ってわかりやすく解説

競技プログラミングなどでは、数え上げ問題と言われる問題が出題されます。ちょっと複雑になると「！？」となってしまうくらいに不得意です。慣れるしかないとは思いますが、パターンも覚える必要があります。

ここでは、数え上げ問題で出題される、重複組み合わせの問題を１つ紹介したいと思います。

問題は以下のとおり。

１つ以上間隔を空けて受験生を座らせた場合の、組み合わせの数を数え上げる問題です。

整理できれば、簡単なのですが悩みました。

理解するために、具体的に人数を当てはめて考えてみます。ここでは、受験生5人、席数１１席としました。

まず、受験生を座らせるには何席必要かを考えます。両端に受験生を配置するとすれば、空席と交互に配置した以下のパターン、つまり９席が最低必要な数になります。

このパターンをベースに考えます。９席のパターンは決まっているので、１１席の場合、２席余分にあることになります。$P$と$C$の記号で考えると$C-(2P-1)$席です。

これは、空席の隣か、両端の好きな位置に挿入できます。空席の左右どちらに入れても（空席、空席）というパターンに変化はないので、どちらに入れる場合も区別しないで考えると、あまり２席を挿入できる場所は、下図の矢印部分の６箇所となります（$P+1$箇所）。

実は、空席の左右どちらに入れるかを区別しない、という部分で悩みました。受験者と空席の間の数＋両端の１０箇所じゃないかと最初思ってしまいました。

ただ、ちゃんと考えると、どちらに挿入しても、空席が２つになることは同じなので区別しません（下図）。なので、６箇所になります。

ここまで整理できればあとは簡単です。

$P+1$箇所の中に、$C-(2P-1)=C-2P+1$個を配置する組み合わせの数ですので重複組み合わせで以下のように表すことができます。

$$ _{P+1}H_{C-2P+1} $$

ちなみに、重複組み合わせ$H$は以下のように書くこともできます。

$$ _nH_r = _{n+r-1}C_r $$

ちょっと複雑になっただけで分からなくなってしまいます。

このあたりを簡単に解けるようになりたいね。