ｸｲｽﾞ大陸

いわゆる完全順列(モンモール数)の問題です。

各席に1〜n まで番号を振り、生徒も前回座っていた席と同じ番号を振る。
まず、N(n)=(n-1)(N(n-1)+N(n-2)) (n≧3) であることを示す。
[証明1]
n人のクラスで全員が前回と異なる席に座っており、n番の席にk番 (1≦k≦n-1) の生徒が座っているとする。
k番の席にn番の生徒が座っている時、n番とk番の生徒を除いた並べ方は、N(n-2)通り
k番の席にn番の生徒が座っていない時、k番の生徒を除いた並べ方は、N(n-1)通り
いずれの場合もkの値の選び方は(n-1)通りあるから、
N(n)=(n-1)(N(n-1)+N(n-2))

[証明2]
(n-1)人のクラスで全員が前回と異なる席に座っている時に、新たにn番の席を加え、n番の生徒を座らせる。
このとき、n番の生徒と、1〜(n-1)番の生徒1人が席を入れ替えれば、条件を満たす。
その並べ方は、(n-1)N(n-1)通り
また、(n-1)人のクラスで一人だけ席の番号(kとする)と生徒の番号が一致するような並べ方は、(n-1)N(n-2)通りある。
このとき新たにn番の席を加え、n番の生徒を座らせて、n番の生徒と、k番の生徒が席を入れ替えれば、条件を満たす。
その並べ方は、(n-1)N(n-2)通り
条件を満たす並べ方は、この2つのうちのいずれかであるから、
N(n)=(n-1)(N(n-1)+N(n-2))

条件を満たす並べ方は、n=1 のときは存在せず、n=2 のときは(2,1)の1通りである。
即ち、N(1)=0,N(2)=1
よって、
N(3)=2(N(2)+N(1))=2
N(4)=3(N(3)+N(2))=9
N(5)=4(N(4)+N(3))=44
N(6)=5(N(5)+N(4))=265
N(7)=6(N(6)+N(5))=1854
∴(1)9,(2)1854

(3)
n席にn人が座る場合の数はn! であるから、
P(n)=N(n)/n!
∴P(6)=N(6)/6!=265/720=53/144

(4)(以下では便宜的にN(0)=1と定める)
n人のクラスでk人が席の番号と生徒の番号が一致する並べ方は、
_nC_kN(n-k)通りであるから、
N(n)=n!-Σ[k=1,n](_nC_kN(n-k))
∴Σ[k=0,n](_nC_kN(n-k))=n!
また、
E(n)=1/n!*Σ[k=0,n](k_nC_kN(n-k))
E(n)=1/n!*Σ[k=1,n](k*n!/((n-k)!k!)*N(n-k))
E(n)=1/(n-1)!*Σ[k=1,n]((n-1)!/((n-k)!(k-1)!)*N(n-k))
E(n)=1/(n-1)!*Σ[k-1=0,n-1]((n-1)!/(((n-1)-(k-1))!(k-1)!)*N((n-1)-(k-1)))
E(n)=1/(n-1)!*Σ[k-1=0,n-1](_n-1C_k-1N((n-1)-(k-1)))
E(n)=1/(n-1)!*(n-1)!
E(n)=1
∴E(5)=1

おまけ
N(n)=(n-1)(N(n-1)+N(n-2)) より、
N(n)-nN(n-1)=-(N(n-1)-(n-1)N(n-2))=…=(-1)^n-2(N(2)-2N(1))
N(n)-nN(n-1)=(-1)ⁿ
よって、
N(n)/n!-N(n-1)/(n-1)!=(-1)ⁿ/n! であるから、
N(n)/n!=Σ[k=2,n](N(k)/k!-N(k-1)/(k-1)!)+N(1)/1!
N(n)/n!=Σ[k=2,n]((-1)^k/k!)
N(n)/n!=Σ[k=0,n]((-1)^k/k!)
∴P(n)=Σ[k=0,n]((-1)^k/k!)
よって、lim[n→∞]P(n)=Σ[k=0,∞]((-1)^k/k!)
で、これは関数e^xのマクローリン展開
e^x=Σ[k=0,∞](x^k/k!)
にx=-1 を代入したものである。
∴lim[n→∞]P(n)=1/e
よって、P(n)は�C,E(n)は�@((4)で証明済み)

1/eの値は小数で表すと大体0.3679くらいで、この値にはかなり早く収束します。
上の結果より、席替えをしたときには、クラスの人数に関係なく大体1人くらいが前回と同じ席になる、ということが解ります。
今度席替えの機会があれば、そうした人を探してみると面白いかもしれません