◆東京都 かえる さんからの解答。
【問題1】
n人の並び替えでn!通り
この中には、自分で自分の仮装をする場合が含まれている
よって、nC1(n−1)!を引く
しかし、これでは、2人が自分で自分の仮装をする場合を引きすぎている
よって、nC2(n−2)!を足す
・・・
と続けていくと、
f(n)=nC0n!−nC1(n−1)!+nC2(n−2)!−・・・
【問題2】
(論述が不正確な点があると思いますが、雑駁以下のような感じになるのではないでしょうか。)
n人による完全仮装の場合の数をf(n)通り
原始完全仮装の組の数の期待値をE(n)と置く
n人による完全仮装をするには、
<1>
(n−1)人の完全仮装に1人加わり、その人と(n−1)人のうちの誰かの仮装を交換する場合
(n−1)f(n−1)通り
or
<2>
(n−2)人の完全仮装に2人加わり、加わった2人が仮装しあう場合
(n−1)f(n−2)通り
((注)(n−1)人から(n−2)人を選ぶ選び方の(n−1)通りを乗じている)
より
f(n)=(n−1)f(n−1)+(n−1)f(n−2)
(←この漸化式を解けば【問題1】が解決 「モン・モールの問題」というやつ?)
n人の完全仮装になるには、<1>の場合から(n−1)f(n−1)通り、
<2>の場合から(n−1)f(n−2)通り、
その比は、f(n−1):f(n−2)であることを考えれば、
E(n)= | f(n−1)E(n−1)+f(n−2)(E(n−2)+1) f(n−1)+f(n−2) |
ここでnが十分大きいとき、f(n)≒ | n! e | (証明略) |
よって、
E(n)≒ | (n−1)!E(n−1)+(n−2)!(E(n−2)+1)
(n−1)!+(n−2)! |
E(n)−E(n−1)≒ | 1 n |
− | E(n−1)−E(n−2)
n | ≒ | 1 n |
和分を積分で近似し、E(n)≒logn
◆東京都 T.Kobayashi さんからの解答。
【問題1】
既に上に出ている通り、n! | n Σ k=2 |
(-1)k k! | である。 |
【問題2】
完全仮装とは、各番号が一度は出現し、二度以上は出現しないような、 長さ 2 以上の循環置換(これが原始分割である)の積で書けるものであると言える。
そこで、構成番号が 1 から n に収まっているもので、長さが 2 ないし n-2 、または n である循環置換を全て考え、それを因数として持つような完全仮装置換を数え上げ、 それを(1)の結果で割り算すれば求まる。
完全仮装置換であることの判定は、因数を 取り除いた後の置換が再び完全仮装であることで行え、そのような置換の数は(1)で 求まっている。
同じ番号構成で長さが n の循環置換は (n-1)! だけあるから、
((n-1)!+ | n-2 Σ m=2 |
(m-1)!combi(n,m)(n-m)! | n-m Σ k=2 |
(-1)k k! |
)/(n! | n Σ k=2 |
(-1)k k! |
) |
=( | 1 n | + | n-2 Σ m=2 |
1 m |
n-m Σ k=2 |
(-1)k k! |
)/( | n Σ k=2 |
(-1)k k! |
) |
が求めるものである。
さて、 | 1 n |
→0, | n Σ k=2 |
(-1)k k! |
→ | 1 e |
(n→∞) である。 |
n-2 Σ m=2 |
1 m |
n-m Σ k=2 |
(-1)k k! |
= | n-2 Σ k=2 |
( | 1 2 |
+ | 1 3 |
+...+ | 1 n-k |
) | (-1)k k! |
である。 |
(*)ここで、n が十分大きく、k が 小さいとき、
1 2 |
+ | 1 3 |
+...+ | 1 n-k |
=log(n)+(γ-1)+o(1) と思われる。 |
また、k が n に近づくにつれ、 | (-1)k k! |
は非常に小さくなる。 |
従って、
n-2 Σ m=2 |
1 m |
n-m Σ k=2 |
(-1)k k! |
= | 1 e |
(log(n)+γ-1)+o(1) |
結局、log(n)+γ-1 が求めるものであると思われる。
誤差は n→∞ のとき o(1) の程度。(**)
# (*)から(**)まで、議論の進め方はかなり怪しいですが…。
# シミュレーションはこれが正しそうなことを示唆しているので、おそらくこれが解答だとは思うんですが…。
# ((*)以前の議論が正しいと仮定しての話ですが。)
◆出題者のコメント。
かえるさん、T.Kobayashiさん、解答ありがとうございます。
【問題1】は、お二人ともみごと正解です。
【問題2】は、残念ながらお二人とも私が期待した答えとは若干違います。
以下が【問題2】のヒントです。
自分自身に仮装することも許すものとすると、
n人の完全仮装における原始完全仮装の平均組数
= | 1 1 |
+ | 1 2 |
+ | 1 3 |
+…+ | + | 1 n |