ケンタッキーのサイドメニュー問題と重複組合せ

去年の年末、ケンタッキーに行ったときのことです。オリジナルチキン4ピースパックを注文することにしました。
www.kfc.co.jp

このパックでは、以下の4種のサイドメニューのうち1個を選ぶことができます。

・ポテトS
・クリスピー
・ビスケット
・コールスローS

どれもおいしそうですね。

f:id:tsujimotter:20200306160743j:plain:w360

写真はオリジナルチキンとサイドメニューのビスケットです

私は2パック購入したので、サイドメニューは重複を含めて2個選ぶことができました。

ここで購入する際に悩んだのは、次の問題です。

サイドメニューを選ぶ組合せは何通りだろうか？

（あ、サイドメニューを選ぶのに悩んだんじゃないんですね・・・）

この問題に対して、ケンタッキーを出てから家までの道のりの間考えてみたところ、二通りの解法を思いつきました。それを紹介したいと思います。

解法１

サイドメニューを2個選ぶときに、(i)重複しない場合と(ii)重複する場合に分けて考えてみましょう。

(i)重複しない場合は、4種のサイドメニューから2個を選ぶ組み合わせなので ${}_4\mathrm{C}_2 = 6$ 通りです。

(ii)重複する場合は、4種のサイドメニューから1種を選んで、それを2個購入すればよいわけです。したがって、 ${}_4\mathrm{C}_1 = 4$ 通りです。

よって、 $6 + 4 = 10$ より $10$ 通りが正解です。

解法２

もう一つの解法では「重複組合せ」の一般論を使います。

4種の中から重複を許して数える際に、「仕切り」を入れて考える方法があります。たとえば

ポテトS：1個、クリスピー：1個、ビスケット：0個、コールスローS：0個

に対して

〇|〇||

と表すことにしましょう。

他の例として

ポテトS：0個、クリスピー：0個、ビスケット：2個、コールスローS：0個

に対しては

||〇〇|

と表します。

このようにすると、仕切りの間にある〇の個数が、選んだサイドメニューの個数となります。

したがって、仕切りと〇の順列を考えて、仕切りの順列と〇の順列で割ったものが組合せの総数となります。つまり

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

が答えです。

一般化できるか？

こんな風に二通りの方法で組合せが10通りであることが示せましたが、同じことをまったく別の方法で計算できるというのは少し不思議な気がします。

上の２通りの結果が一致するということは、

${}_5\mathrm{C}_2 = {}_4\mathrm{C}_2 + {}_4\mathrm{C}_1$

が成り立つということですね。

これは、一般の二項係数に対してで成り立つ漸化式

${}_n\mathrm{C}_r = {}_{n-1}\mathrm{C}_r + {}_{n-1}\mathrm{C}_{r-1}$

そのものですね。

今回は「4種の中から重複を許して2個選ぶ」ことを考えましたが、一般化することはできるでしょうか。

試しに「10種の中から重複を許して5個選ぶ」ことを考えてみます。ケンタッキーで考えると、サイドメニューが10種類に増えて、それを5セット買ったときに発生する問題ですね。

解法２では、 $10-1$ 個の仕切りと $5$ 個の〇を考えますので、 ${}_{10-1+5}\mathrm{C}_{5} = {}_{14}\mathrm{C}_{5}$ ですね。

解法１は少しややこしくなります。

ケース $1+1+1+1+1$ ：重複がまったくないケースでは ${}_{10}\mathrm{C}_{5}$
ケース $1+1+1+2$ ：3種のメニューを1個ずつ選んで、残りから1種のメニューを2個重複して選ぶ ${}_{10}\mathrm{C}_{3} \times {}_{7}\mathrm{C}_{1}$
ケース $1+1+3$ ：2種のメニューを1個ずつ選んで、残りから1種のメニューを3個重複して選ぶ ${}_{10}\mathrm{C}_{2} \times {}_{8}\mathrm{C}_{1}$
ケース $1+4$ ：1種のメニューを1個選び、残りから1種のメニューを4個重複して選ぶ ${}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{1}$
ケース $1+2+2$ ：1種のメニューを1個選び、残りから2種のメニューを2個ずつ重複して選ぶ ${}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{2}$
ケース $2+3$ ：1種のメニューを2個重複して選び、残りからもう1種のメニューを3個重複して選ぶ ${}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{1}$
ケース $5$ ：1種のメニューを5個重複して選ぶ ${}_{10}\mathrm{C}_{1}$

場合分けがずいぶん多くなりましたね。

これをまとめると

$\begin{align} {}_{14}\mathrm{C}_{5} = \;& {}_{10}\mathrm{C}_{5} + {}_{10}\mathrm{C}_{3} \times {}_{7}\mathrm{C}_{1} + {}_{10}\mathrm{C}_{2} \times {}_{8}\mathrm{C}_{1} \\ &+ {}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{1} + {}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{2} \\ &+ {}_{10}\mathrm{C}_{1} \times {}_{9}\mathrm{C}_{1} + {}_{10}\mathrm{C}_{1} \end{align}$

という、二項係数の関係式が得られるというわけです。

計算してみると確かに両辺が一致することが分かります。しかしながら、「4種の中から重複を許して2個選ぶ」ときと比べると、だいぶ非自明になった感じがしますね。

「この式を組合せ的な考え方を用いずに直接証明せよ」といわれたら、かなり難しいのではないでしょうか。

「分割数」との関連

ケンタッキーのサイドメニュー問題の一般化「 $n$ 種の中から重複許して $r$ 個選ぶ」を考えるにあたって、解法２のパートがややこしくなりそうですね。

既に気づいている人がいるかもしれませんが、解法２の場合分けは「分割数」に関係しています。各場合分けの左側に「意味ありげに」書いた式は「 $5$ の分割」をすべて表したものになっています。

$\begin{align} &1+1+1+1+1 \\ &= 1+1+1+2 \\ &= 1+1+3 \\ &= 1+4\\ &= 1+2+2 \\ &= 2+3 \\ &= 5 \end{align}$

$r$ の分割の総数を $p(r)$ と書くと、 $p(5) = 7$ 個の項が出てくるわけですね。

ここで、いくつか記号を導入したいと思います。

まず、 $r$ の分割を表現する方法なのですが、0以上の整数の $r$ 個組 $(n_1, \ldots, n_r)$ で表すことにします。

たとえば $2+1+1+1$ の場合 $(3, 1, 0, 0, 0)$ と表現します。つまり、 $1$ が $3$ 個、 $2$ が $1$ 個に分割されているということですね（ $3, 4, 5$ はそれぞれ $0$ 個です）。

次に $P(r)$ を $r$ の分割全体の集合とします。 $P(r)$ の元としては、上で述べた $r$ 個組

$(n_1, \ldots, n_r) \in P(r)$

を考えます。このとき $\# P(r) = p(r)$ となりますね。

さて、このように準備しておくと、一般的に解法２を考えることができそうです。

ある分割 $(n_1, \ldots, n_r) \in P(r)$ に対する組合せは

${}_{n}\mathrm{C}_{n_1} \times {}_{n-n_1}\mathrm{C}_{n_2} \times \cdots \times {}_{n-(n_1+\cdots+n_{r-1})}\mathrm{C}_{n_r}$

と表せます。

たとえば、5の分割 $1+1+1+1+1$ に対応する $(5, 0, 0, 0, 0)$ については

${}_{10}\mathrm{C}_{5} \times {}_{5}\mathrm{C}_{0} \times {}_{5}\mathrm{C}_{0} \times {}_{5}\mathrm{C}_{0} \times {}_{5}\mathrm{C}_{0}$

となります。

また、5の分割 $1+1+1+2$ に対応する $(3, 1, 0, 0, 0)$ については

${}_{10}\mathrm{C}_{3} \times {}_{7}\mathrm{C}_{1} \times {}_{6}\mathrm{C}_{0} \times {}_{6}\mathrm{C}_{0} \times {}_{6}\mathrm{C}_{0}$

となります。

どちらも上で計算した結果と一致していますね。

総積記号を使って表すと

$\displaystyle \prod_{i=1}^{r} {}_{n-(n_1+\cdots+n_{i-1})}\mathrm{C}_{n_i}$

ということですね。

これをすべての分割に対して足し合わせると

$\displaystyle \sum_{(n_1, \ldots, n_r) \in P(r)}\prod_{i=1}^{r} {}_{n-(n_1+\cdots+n_{i-1})}\mathrm{C}_{n_i}$

となります。

解法２と合わせると

$\displaystyle {}_{n-1+r}\mathrm{C}_{r} = \sum_{(n_1, \ldots, n_r) \in P(r)}\prod_{i=1}^{r} {}_{n-(n_1+\cdots+n_{i-1})}\mathrm{C}_{n_i} \tag{1}$

という関係式が得られました。

まぁ、全然きれいな式ではないですけどね。笑

しかしながら、こんな式が成り立つというのは、少し興味深いなと思います。この式が何か役に立つかどうかは差し置いても、同じものに対して異なる見方をしてみるというのは面白いなと思いました。

それでは、今日はこの辺で。

追記（2020/03/07）

最後に得られた式 $(1)$ なのですが、実はもっときれいに表現できることがわかりました。教えて下さったshuさん（@LT_shu）ありがとうございます。

ポイントはコンビネーションを階乗で書き直すことです。

$\displaystyle {}_{n}\mathrm{C}_{m} = \frac{n!}{m! (n-m)!}$

を使って

${}_{n}\mathrm{C}_{n_1} \times {}_{n-n_1}\mathrm{C}_{n_2} \times \cdots \times {}_{n-(n_1+\cdots+n_{r-1})}\mathrm{C}_{n_r}$

を書きかえましょう。

$\displaystyle \frac{n!}{n_1! (n-n_1)!} \times \frac{(n-n_1)!}{n_2! (n-(n_1+n_2) )!} \times \cdots \times \frac{(n-(n_1+\cdots +n_{r-1}) )!}{n_r! (n-(n_1+\cdots +n_r) )!}$

これがうまいこと消えるので・・・

$\require{cancel} \displaystyle \frac{n!}{n_1! \cancel{(n-n_1)!}} \times \frac{\cancel{(n-n_1)!}}{n_2! \cancel{(n-(n_1+n_2) )!}} \times \cdots \times \frac{\cancel{(n-(n_1+\cdots +n_{r-1}) )!}}{n_r! (n-(n_1+\cdots +n_r) )!}$

こうなります。

$\displaystyle \frac{ n! }{n_1! n_2! \cdots n_r! (n-(n_1+\cdots+n_r) )!}$

分母の会場の中身は足すと分子の $n$ に一致する組合せになっています。

よって式 $(1)$ を書き直すと、次の式が得られます。

$\displaystyle {}_{n-1+r}\mathrm{C}_{r} = \sum_{(n_1, \ldots, n_r) \in P(r)} \frac{ n! }{n_1! n_2! \cdots n_r! (n-(n_1+\cdots+n_r) )!} \tag{2}$

これはだいぶきれいになりましたね。

多項係数の記法を用いると

$\displaystyle {}_{n-1+r}\mathrm{C}_{r} = \sum_{(n_1, \ldots, n_r) \in P(r)} \begin{pmatrix} n \\ n_1, n_2, \ldots, n_r, n-(n_1+\cdots +n_r)\end{pmatrix} \tag{3}$