順列と重複のある順列とやや重複のある順列

よくしらないんだけど、44枚買って44種類集まる確率の件があったよねえ。
順列(正解の数)を重複順列(考えられる順列の数)で割れば良いので、44! / 44**44。
じゃあ45枚買って44種類集まる確率とか10枚買って5種類集まる確率はどうやって求めるんだろ。考えられる事象は重複順列だから、もう決まり。難しそうなのは正解の種類だなあ。

まず、ダブりがないケース。@n種類のものをtest回買うときは、(test - 1)回買うときの数に、さらに正解になる選択肢(@n - (test - 1))をかけたものだ。(test - 1)回目では(test - 1)種類使っているから、残りの選択肢はNから引けばよい。ループで書けるのに、都合によりわざとらしく再帰で書いてみる。

class Permutation0
  def initialize(n)
    @n = n
  end

  def [](test)
    return @n if test == 1
    self[test - 1] * (@n - (test - 1))
  end
end

akb = Permutation0.new(12)
p akb[12]

ダブりがあるケースはどうなんだろ。
一回前までが正解している数 * 選択肢 + 一回前までにダブりを除いた部分が決まっている数 * 選択肢になるような気がする。
左側の残った選択肢は、さっきと同じで@n-既に使っている種類。右側の選択肢は、どの種類がきてもよいので@n。
うーん。どう考えても日本語風に書くとわかりにくいのでRubyにする。

class Permutation
  def initialize(n)
    @n = n
  end

  def [](test, err=0)
    return 0 if err < 0
    return 0 if test <= 0
    return 0 if test <= err
    return 0 if test - err > @n
    return @n if (test - err) == 1

    left(test - 1, err) + right(test - 1, err - 1)
  end
  
  def left(test, err)
    self[test, err] * (@n - (test - err))
  end

  def right(test, err)
    self[test, err] * (test - err)
  end
end

akb = Permutation.new(12)
p akb[15, 4].quo(12 ** 15)

12種類のカードが入ってるチョコを15個買って、11種類まであつまる確率は4.6%くらい、44種類を45回でそろえる確率は、44回でそろえる確率の22.5倍らしいよ。

こんなプログラムも、きっと数学風に説明したらもっとすっきりするんだろうな。

[rakuten:e-medio:1414269:image]←12種類のカードの例