 pc ( No.6 ) |
- 日時： 2010/03/04 21:03
- 名前： neutrino
- いわゆる完全順列(モンモール数)の問題です。
各席に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人が席の番号と生徒の番号が一致する並べ方は、
nCkN(n-k)通りであるから、
N(n)=n!-Σ[k=1,n](nCkN(n-k))
∴Σ[k=0,n](nCkN(n-k))=n!
また、
E(n)=1/n!*Σ[k=0,n](knCkN(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-1Ck-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(n-1)/(n-1)!=(-1)n/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!)
で、これは関数exのマクローリン展開
ex=Σ[k=0,∞](xk/k!)
にx=-1 を代入したものである。
∴lim[n→∞]P(n)=1/e
よって、P(n)は④,E(n)は①((4)で証明済み)
1/eの値は小数で表すと大体0.3679くらいで、この値にはかなり早く収束します。
上の結果より、席替えをしたときには、クラスの人数に関係なく大体1人くらいが前回と同じ席になる、ということが解ります。
今度席替えの機会があれば、そうした人を探してみると面白いかもしれません 
|
|
FAQ
RSS