★Beat Angels

前途は遠かった。でもそれはどうでもいい。道こそが人生だからだ。 - Jack Kerouac

みちのくフィギュアみやげ(補遺)

前回、n種類のフィギュアをランダムにr個購入したときの順列の中でn種類がすべて含まれる順列の数は

f:id:taamori1229:20191013085711p:plain

であることを説明した。これのn=2,3,4の場合の具体的な式は、

f:id:taamori1229:20191013090123p:plain

であり、大変分かりにくい。これを数表として書いてみると、

 f:id:taamori1229:20191013090449p:plain

これを眺めて、何らかの法則を導き出すのが本稿の目的である。

まず、定義から次の①が予想される。

f:id:taamori1229:20191013090857p:plain

分母はn種類をr回購入したときの順列の総数なのでこれはr個購入したときにn個がすべて揃う確率を表している。それが1に収束するということは、rがnを超えて大きくなればいつかはn個が揃うのは時間の問題である、ということを示している。これを数学的に証明すると、

f:id:taamori1229:20191013091344p:plain

となる。また、n、rが1の場合については、直接計算すると次の公式群が成り立つ。

f:id:taamori1229:20191013091713p:plain

ここまではあまり面白くないが、特徴的なのは次の公式である。

f:id:taamori1229:20191013091812p:plain
前者は数表の右上半分が0であることに対応し、後者は斜めの数、1,2,6,24,・・・がn!になっていることに対応する。

これらは直感的に理解しやすい。前者はn種類そろえるのにnより小さいr回では揃うはずがないことを表している。後者はrとnが等しい場合であり、このときn種類が1個ずつきれいに選ばれる。となると求める数列はn個の単純な並べかえの順列に等しい、ということである。

数学的に導くには次のような解析的な方法がある。
f:id:taamori1229:20191013093525p:plain

という2項級数の式に対して、①xで微分する、②x=1を代入する、③両辺にxを掛ける。という操作を繰り返す。

f:id:taamori1229:20191013093631p:plain

そして、一般的に、

f:id:taamori1229:20191013093708p:plain

が得られる。

後者の延長で「ではrがn+1の場合はどうなるか?」という疑問がわく。この場合は、

f:id:taamori1229:20191013092444p:plain

という何とも言えない式となる。n+2以降はさらに複雑化して書き下せない。

S(n,r)については漸化式として次が成立する。

f:id:taamori1229:20191013092641p:plain

この式の直観的な説明は次のようになる。r回目をひいてn種類揃っているということからその1回前はどうだったということを考えると、すでにn種類揃っていたか、あと一種類足りなかったかのどちらかである。n回目はn通りあるのでこの式が成り立つ。

数表の上で見てみると、どこでもいいので左右で隣り合う2つの数字を足し合わせる。それをn倍化したものが、右側の数字の下の数字に等しい。この漸化式は数表を作っていく上で非常に重要である。

以上が基本的な性質となるが、他にはどのようなものがあるか。

計算の支障となっているのはSの式の複雑さである。そこでSに変わって次のS’を導入する。

f:id:taamori1229:20191013094822p:plain

これを用いると、数表は次のようになる。

f:id:taamori1229:20191013094934p:plain

この表を眺めながら規則を探してみる。例えば横一列をすべて足すと0になることはすぐに気が付く。同様にして他の法則を探し続けた。その結果、次のような公式群を発見した。⑧以降はもともとの問題の枠をはみ出してrが0や負の数の場合も扱っている。

f:id:taamori1229:20191013095734p:plain

これらは計算上は成り立つのだが、みちのくフィギュアみやげの問題にどのように絡んでくるかは不明である。

前回記事でn個そろえるのに必要な回数の期待値E(n)を計算してそれが、

f:id:taamori1229:20191013101207p:plain

であることを示したが、今回の結論を使うと、

f:id:taamori1229:20191013102113p:plain

と書き表せる。rがー1と負数なのがポイントである。これがはたして偶然なのか、なんらかの意味を持つのかについては今後の宿題とする。

以下、rが0や負数とした場合も含めた数表(S、S’)を参考付録として示す。

f:id:taamori1229:20191013100239p:plain

f:id:taamori1229:20191013100253p:plain