『n人による完全仮装』解答


◆東京都 かえる さんからの解答。

【問題1】

n人の並び替えでn!通り

この中には、自分で自分の仮装をする場合が含まれている
よって、n1(n−1)!を引く

しかし、これでは、2人が自分で自分の仮装をする場合を引きすぎている
よって、n2(n−2)!を足す

・・・

と続けていくと、

f(n)=n0n!−n1(n−1)!+n2(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)

((注)<2>の場合は、原始完全仮装の組の数が1つ増える)

ここでnが十分大きいとき、f(n)≒ n!
(証明略)

よって、
E(n)≒ (n−1)!E(n−1)+(n−2)!(E(n−2)+1)
(n−1)!+(n−2)!
E(n)−E(n−1)≒
E(n−1)−E(n−2)

和分を積分で近似し、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人の完全仮装における原始完全仮装の平均組数



+…+


 『n人による完全仮装』へ

 数学の部屋へもどる