食玩問題の複数個パッケージについて

はじめに

食玩問題について亜種の問題を考えている記事を見つけた。その問題について一般項を求めることができたので、今回そのことについて記事を書く。

https://zenn.dev/4ergfbv547uezdf/articles/da849d2dd2e8a9

問題

全 $n$ 種のおまけが $s$ 個ついている食玩があり、その $s$ 個は被らないように同様に確からしく入っている。このとき $r$ パッケージ買ったとき、全種類揃っている確率 $p_{n,s}(r)$ を求める問題となる。

結論

計算結果は以下となる。

$$p_{n,s}(r) = \frac{1}{({}_{n}\mathrm{C}_{s})^r} \sum_{k=s}^n (-1)^{n-k} \,\, {}_{n}\mathrm{C}_{k} \,\, ({}_{k}\mathrm{C}_{s})^r$$

系

最初 $a$ 個持っていて、追加で $r$ パッケージ買ったとき、ちょうど $b$ 個揃っている確率は以下になる。ただし $\mathrm{C}$ が定義できない値の時は $0$ とする。

$$\frac{1}{({}_{n}\mathrm{C}_{s})^r} \,\, {}_{n-a}\mathrm{C}_{n-b} \,\, \sum_{k=a}^b (-1)^{b+k} \,\, {}_{b-a}\mathrm{C}_{b-k} \,\, ({}_{k}\mathrm{C}_{s})^r$$

式の導出

以前書いた記事の「式の導出」の章をベースに求めていく。ここでは簡潔に書くので、先にそちらを参照されたい。

https://zenn.dev/firedial/articles/04b5c2103a44cf

行列

1つのパッケージを買って、ちょうど $k$ 個揃っている確率を考える。考えることは、

• $k-s$ 揃っているところから、新規で $s$ 個揃える(被り $0$ 個)
• $k-s+1$ 揃っているところから、新規で $s-1$ 個揃える(被り $1$ 個)
  ...
• $k-1$ 揃っているところから、新規で $1$ 個揃える(被り $s-1$ 個)
• $k$ 揃っているところから、新規で $0$ 個揃える(被り $s$ 個)

のパターンである。

それぞれの確率を求めると、

• ${}_{n-(k-s)}\mathrm{C}_{s} \,\,\,\, {}_{k-s}\mathrm{C}_{0} \,\,\,\, / \,\,\,\, {}_{n}\mathrm{C}_{s}$
• ${}_{n-(k-s+1)}\mathrm{C}_{s-1} \,\,\,\, {}_{k-s+1}\mathrm{C}_{1} \,\,\,\, / \,\,\,\, {}_{n}\mathrm{C}_{s}$
  ...
• ${}_{n-(k-1)}\mathrm{C}_{1} \,\,\,\, {}_{k-1}\mathrm{C}_{s-1} \,\,\,\, / \,\,\,\, {}_{n}\mathrm{C}_{s}$
• ${}_{n-k}\mathrm{C}_{0} \,\,\,\, {}_{k}\mathrm{C}_{s} \,\,\,\, / \,\,\,\, {}_{n}\mathrm{C}_{s}$

となる。前回と同じように縦ベクトル $a_r$ を使って行列表現すると(あらかじめ${}_{n}\mathrm{C}_{s}$倍しておく)、

$$a_{r + 1} = \begin{pmatrix*}[c] & \cdots & \\ & {}_{n-(k-s)}\mathrm{C}_{s} * {}_{k-s}\mathrm{C}_{0} & \cdots & {}_{n-(k-1)}\mathrm{C}_{1} * {}_{k-1}\mathrm{C}_{s-1} & {}_{n-k}\mathrm{C}_{0} * {}_{k}\mathrm{C}_{s} & \\ & \cdots & \\ & {}_{s+1}\mathrm{C}_{s} * {}_{n-1-s}\mathrm{C}_{0} & \cdots & {}_{2}\mathrm{C}_{1} * {}_{n-2}\mathrm{C}_{s-1} & {}_{1}\mathrm{C}_{0} * {}_{n-1}\mathrm{C}_{s} & \\ & & {}_{s}\mathrm{C}_{s} * {}_{n-s}\mathrm{C}_{0} & \cdots & {}_{1}\mathrm{C}_{1} * {}_{n-1}\mathrm{C}_{s-1} & {}_{0}\mathrm{C}_{0} * {}_{n}\mathrm{C}_{s} \end{pmatrix*} a_r$$

というふうに漸化式が立てられる。その行列を $B$ とおく。また、 $n+1$ 次の正方行列 $Q$ を次のようにおく。

$$Q = \begin{pmatrix*}[c] {}_n\mathrm{C}_n \\ \vdots & \ddots & & \text{\huge{0}} \\ \vdots & & (-1)^{i+j} \,\, {}_{n-j}\mathrm{C}_{n-i} & & \\ \vdots & & & \ddots \\ (-1)^n \,\, {}_n\mathrm{C}_0 & \dots & \dots & \dots & {}_0\mathrm{C}_0 \end{pmatrix*}$$

この時、次の2つが成り立つ。

$$i) \,\,\,\, Q^{-1} = \begin{pmatrix*}[c] {}_n\mathrm{C}_n \\ \vdots & \ddots & & \text{\huge{0}} \\ \vdots & & {}_{n-j}\mathrm{C}_{n-i} & & \\ \vdots & & & \ddots \\ {}_n\mathrm{C}_0 & \dots & \dots & \dots & {}_0\mathrm{C}_0 \end{pmatrix*}$$

$$ii) \,\,\,\, BQ = Q \begin{pmatrix*}[c] {}_{0}\mathrm{C}_{s} \\ & {}_{1}\mathrm{C}_{s} & & & \text{\huge{0}} \\ & & {}_{2}\mathrm{C}_{s} & \\ & & & {}_{3}\mathrm{C}_{s} & \\ & \text{\huge{0}} & & & \ddots \\ & & & & & {}_{n}\mathrm{C}_{s} \end{pmatrix*}$$

実は前回と同じ行列 $Q$ である。固有値は違うが、固有ベクトルは一致したことに驚き。

今回は $ii)$ の証明だけしておく。

$ii)$ の証明

$BQ$ の $k$ 行 $j$ 列成分を求めて、右辺と比較することで証明すべき式、

$$\sum_{i=k-s}^k {}_{n-i}\mathrm{C}_{k-i} \,\, {}_{i}\mathrm{C}_{s-k+i} * (-1)^{i+j} {}_{n-j}\mathrm{C}_{n-i} = (-1)^{k+j} {}_{n-j}\mathrm{C}_{n-k} \,\, {}_{j}\mathrm{C}_{s}$$

が得られる。その式をいい感じに変形することで、

$$\sum_{i=k-s}^k {}_{i}\mathrm{C}_{j} \,\, {}_{s}\mathrm{C}_{k-i} \,\, (-1)^{i+k} = {}_{k-s}\mathrm{C}_{j-s}$$

とすることができ、変数変換によって和の範囲を変えると、

$$\sum_{t=0}^s {}_{t+k-s}\mathrm{C}_{j} \,\, {}_{s}\mathrm{C}_{s-t} \,\, (-1)^{t+s} = {}_{k-s}\mathrm{C}_{j-s}$$

となる。ここで、 Chu–Vandermonde identity という、可愛くてごめんって言いたくなりそうな恒等式を使う。変数の定義域が拡張されているので、 $\binom{n}{k}$ という表記でやっていく。

まず Chu–Vandermonde identity から得られる公式、

$$\binom{n}{k} = (-1)^k \binom{k-n-1}{k}$$

を用いると、

$$\binom{t+k-s}{j} = \binom{t+k-s}{t+k-s-j} = (-1)^{t+k-s-j} \binom{-j-1}{t+k-s-j}$$

と変形できる。よって元の式に入れると、

$$\sum_{t=0}^s (-1)^{t+k-s-j} \binom{-j-1}{t+k-s-j} \binom{s}{s-t} (-1)^{t+s} \\ = (-1)^{k-j} \sum_{t=0}^s \binom{-j-1}{t+k-s-j} \binom{s}{s-t}$$

となる。最後に Chu–Vandermonde identity の式、

$$\binom{s+t}{n} = \sum_{k=0}^n \binom{s}{k} \binom{t}{n-k}$$

を使うことで、

$$(-1)^{k-j} \binom{s-j-1}{k-j}$$

が得られる。公式を適用するには和の範囲はもっと広くしないといけないが、 $t$ が $0$ から $s$ 以外の範囲では $\binom{s}{s-t} = 0$ であるので特に拡張していない。再び最初に出てきた公式を適用すると、

$$(-1)^{k-j} \binom{s-j-1}{k-j} = \binom{k-s}{k-j} = \binom{k-s}{j-s}$$

が得られて元々証明したかった式の右辺となる。

一般項

それらが分かれば前回とほぼ同じ計算ができる。固有値が違うことと、 $1/n$ しているところが $1/{}_{n}\mathrm{C}_{s}$ になっていることだけ注意すればいい。
そうすると、最初に述べた式と系が同様に導出できる。

計算

引用元の記事で、全11種類の3個入り1パックの商品を10パック購入した場合のコンプリート確率を求めていたので、今回導出した式と一致するかを確認する。

k = var('k', domain='integer')
p(n, r, s) = (1 / (binomial(n, s) ^ r)) * sum((-1) ^ (n - k) * binomial(n, k) * binomial(k, s) ^ r, k, s, n)

print(float(simplify(p(11, 10, 3))))

実行結果。完全に一致。

0.6056587736776045

抽象化された式

今回の導出したものは $s=1$ を代入することで前回と同じ式になる。なので、より抽象化できたことになる。

それにより、1点もやもやしていたことが解決した。最初に求めた式、

$$p_n(r) = \frac{1}{n^r} \sum_{k=0}^n (-1)^{n-k} \,\, {}_{n}\mathrm{C}_{k} \,\, k^r$$

の和の開始部分が $k=0$ になっているが、 $k=0$ の時は中身が $0$ になるので $k=1$ にしても大丈夫である。ただ、組み合わせの記号を考えると $k=0$ から始めるのが自然ではある。その $k$ を $0$ か $1$ のどっちから始めればいいか悩んだ。

ただ、今回求めた式、

$$p_{n,s}(r) = \frac{1}{({}_{n}\mathrm{C}_{s})^r} \sum_{k=s}^n (-1)^{n-k} \,\, {}_{n}\mathrm{C}_{k} \,\, ({}_{k}\mathrm{C}_{s})^r$$

をみると $k=s$ となっている。そこの開始部分はパッケージに含まれている数に依存していることが分かったのだ！なので、前回の式は $k=1$ にした方が自然であることが分かった。

さいごに

引用元の記事で問題提起されていたことで、今回より抽象化された式が見つかり大変良かった。
あと、ヰ世界情緒もいいぞ。

https://zenn.dev/4ergfbv547uezdf/articles/da849d2dd2e8a9