去年1年間に殺人事件は1414件起きたという（警察庁の統計より）。
最も多くの殺人事件が起きた日は何件だっただろうか。
4日間に5件の場合
例えば、最大が2件のとき、次のような場合が考えられる。
* * * *
* * * * * * * * * * * . . .
1 2 3 4 1 2 3 4 1 2 3 4
A B C
ここで母関数を考える。
母関数というのは、要は1次元の配列を関数としてひとまとめにしたものである。
ここでは指数型母関数を考える。
P(x) = a0 + a1x + a2x2/2! + ...
ai = 1 なら、P(x) = ex なのでこう呼ぶ。
P(x) = (1 + x + x2/2!)4
を考える。
そして、このx5の項を考える。
(1 + x + x2/2!)(1 + x + x2/2!)(1 + x + x2/2!)(1 + x + x2/2!)
これを展開したときに、
この積の最初の式から x2/2!、
2番目以降は x を持ってくるのが、
上のAに対応する。
Aの場合の数は、5C2 * 3 * 2、
今考えた項は、
x2/2! * x * x * x = x5/2! = 5!/2!x5/5!
となり、
場合の数と係数が一致する。
すなわち、ここでは P(x) の x5 の項を考えればよい。
(1 + x + x2/2!)4 = 1 + 4x + 16x2/2! + 60x3/3! + 204x4/4! + 600x5/5! + ...
(1 + x + x2/2! + x3/3!)4 = 1 + 4x + 16x2/2! + 64x3/3! + 252x4/4! + 960x5/5! + ...
(1 + x + x2/2! + x3/3! + x4/4!)4 = 1 + 4x + 16x2/2! + 64x3/3! + 256x4/4! + 1020x5/5! + ...
(1 + x + x2/2! + x3/3! + x4/4! + x5/5!)4 = 1 + 4x + 16x2/2! + 64x3/3! + 256x4/4! + 1024x5/5! + ...
場合の数は、
最大が2件までが600、
最大が3件までが960、
最大が4件までが1020、
最大が5件までが1024、
となる。
だから、
最大が2件は600、
最大が3件は360、
最大が4件は60、
最大が5件は4、
というわけである。
366日間に1414件の場合
ライブラリを改善したり、プログラムを工夫したりしたが、
結局9時間かかった。
p6 = 0.0000000000000000
p7 = 0.0000000054620961
p8 = 0.0009264517219113
p9 = 0.0862636264074067
p10 = 0.3616344434654950
p11 = 0.3332283828985481
p12 = 0.1499842272691410
p13 = 0.0493156344891109
p14 = 0.0139433687430278
p15 = 0.0035948084362996
p16 = 0.0008629123235979
p17 = 0.0001945084055079
p18 = 0.0000413632427388
p19 = 0.0000083265071579
p20 = 0.0000015911679772
p21 = 0.0000002893789805
p22 = 0.0000000501998723
p23 = 0.0000000083237908
p24 = 0.0000000013217343
p25 = 0.0000000002013381
p26 = 0.0000000000294687
p27 = 0.0000000000041504
p28 = 0.0000000000005632
p29 = 0.0000000000000737
p30 = 0.0000000000000093
p31 = 0.0000000000000011
p32 = 0.0000000000000001
p33 = 0.0000000000000000
期待値
10.77373942
