next up previous
次: 期待値が自然対数の底上: 確率分野 前: ビュッホンの針

めぐりあいの確率など

$ 1 $ から $ n $ までの番号のついたカード $ n $ 枚を無作為に並べる.すべての $ k\ (1\leqq k \leqq n) $ について, $ k $ 番目にあるカードの番号が $ k $ではないような順列を完全順列という. 完全数列の総数をモンモール数という.
なお完全順列とならない順列をめぐりあいの順列とも言う.それが表題の意味である.
これは, 2004年東工大後期2007年名古屋市大2014年大阪医大などに出題されている.
モンモール数を求める方法は,2004年東工大後期の解答のなかに2通り,本問の解答のなかに2通り,一つは基本的に同じなので,あわせて3通りが示されている.
同様に考えることのできる問題をあわせてここに紹介する.

問題 4.8       解答4.8

【問題甲】  $ 1 $ から $ n $ までの番号のついたカード $ n $ 枚を勝手に並べるとき,少なくとも一枚 $ k $ 番目に番号 $ k $ のカードのある確率を求めよ.

【問題乙】  $ 1 $ から $ n $ までの番号のついた赤球と白球,あわせて $ 2n $ 個を円周上に並べる. 赤球と白球が隣りあうことはないという条件の下で,同じ番号の赤球と白球が隣りあうことのない場合の数を $ C(n) $ , 少なくとも一組同じ番号の赤球と白球が隣りあう場合の数 $ f(n) $ とする. $ C(n) $の漸化式,および $ f(n) $ の明示式を求めよ.

【問題丙】  $ m $台の客車で編成された列車がある. $ n $人の乗客がそれぞれいずれかの列車にる. 各々の客車に少なくとも1人は乗るような乗り方の総数を $ a_m(n) $ とする. $ a_m(n) $ はその定義から $ m=n $ のとき $ a_m(n)=n! $ , $ m>n $ のとき $ a_m(n)=0 $ であるが, 一方 $ m< n $ のときを含めて \[ a_m(n) =\sum_{k=1}^{m}{}_m \mathrm{C}_k(-1)^{m-k}k^n \] となることを示せ.
$ k $ 番の乗客が $ f(k) $ が番の列車に乗るとすると, $ f $ は,個数 $ n $の有限集合から個数 $ m $ の有限集合への写像であり, いずれかの列車に乗るということは $ f $ が全射であるということである. したがって, $ a_m(n) $ はまた,個数 $ n $ の有限集合から個数 $ m $ の有限集合への全射の総数でもある.

 

Aozora Gakuen