京都医塾公式ブログ

モンモール数

モンモール数

こんにちは。数学科の玉島です.本日の数学ネタはモンモール数です.

モンモールについて

 モンモール:フランスの数学者.Wikipediaを見ても詳しくは載っていませんでした.

モンモール数とは

 モンモール数とは完全順列または攪乱順列の総数です.例えば3人でプレゼントを持ち寄り,プレゼント交換をするとしてみましょう.

\( a \)さん、\( b \)さん、\( c \)さんがプレゼント1,2,3を持ち寄ったとしましょう。

例えば

\( \begin{bmatrix} a & b & c \\ 1 & 2 & 3 \\ \end{bmatrix} \)

と配ったとすると,自分で買ってきたプレゼントを3人とも自分でもらうことになります.別にありと言えば,ありですけど,何のために3人が集まったか分かりません.せっかくですから,自分で買ってきたプレゼントは他の人に渡しましょう.すると,その配り方は

\( \begin{bmatrix} a & b & c \\ 2 & 3 & 1 \\ \end{bmatrix} と \begin{bmatrix} a & b & c \\ 3 & 1 & 2 \\ \end{bmatrix} \)

の2通りとなります.つまり,\( n=3 \)におけるモンモール数は2となります.では,数学っぽく記号で表します.ここでは\( n \)に対するモンモール数を\( M_{n} \)と表すことにします.上の\( n=3 \)の場合でしたら\( M_{3}=2 \)となります。同様に調べていくと

\( M_{1}=0,M_{2}=1,M_{3}=2,M_{4}=9,M_{5}=44,M_{6}=265 \)

となることが分かります.いやいや3桁って(笑)

 さらに\( M_{7}=1854 \)ですよ.大すぎでしょ.

 というわけで,モンモール数ははじめうちはかわいいのですが,すぐに手に負えなくなります.では,求める方法は何があるのか?それは後ほど紹介するとして,ちょっと確率を考えてみましょう.

 \( n \)人に何も考えずただ配るだけでしたら,その配り方は\( n! \)通りあります.だから4人に配るときに全員が自分のプレゼントを手に取らない確率は

\( \displaystyle \frac{9}{4!}=\frac{3}{8}=0.375 \)

となります.5人だと

\( \displaystyle \frac{44}{5!}=\frac{11}{30}=0.3666 \cdots \)

です.Wikipediaによりますと\( n \)を十分に大きくとると

\( \displaystyle \lim_{n \to \infty} \frac{M_{n}}{n!} =\frac{1}{e} =0.3678 \cdots \)

だそうです.つまり,誰かが自分のプレゼントにあたる確率は

\( \displaystyle 1-0.3678 \cdots =0.6321 \cdots \)

なんです。結構高いですよね.

 プレゼント交換会を開くときには,自分のプレゼントが当たった人に対して事前にルールを決めておかないと,のちのちわだかまりを残しそうです.

モンモール数の求め方

 ではお待ちかね,モンモール数の求め方を確認しましょう!(誰も待ってないって)

 モンモール数を求めるには漸化式を作ります.

 「漸化式って何?美味しいの?」という方.ごめんなさい.

 今日は漸化式の話を始めると長くなりすぎて,玉島の寝る時間が失われるのでご容赦下さい.今度,漸化式をテーマにブログを書いてみましょう.テーマが広すぎてまとめる自信がありませんが\( \cdots \).

 \( M_{n+1} \)を求める漸化式を作ります.

 つまり,\( n \)人でパーティをしているときに1人が遅れてくる場面を想像して下さい.この\( n \)人のパーティは次の2通りの可能性があります.

(i) \( n \)人が既にプレゼント交換している.

(ii) \( n \)人のうち1人だけ自分のプレゼントをもっており、残り\( n-1 \)人が交換をしている.

(i) のとき

  \( n \)人のプレゼント交換の方法は\( M_{n} \)通りです.ここに1人だけ遅れてきたとしたら,この\( M_{n+1} \)人目はどうすればよいか?誰か1人と交換すれば全員が自分のプレゼントをもらわずに済みます.ですから場合の数は\( nM_{n} \)通りあります。

(ii)のとき

 怖いですね〜。いじめでしょうか?

 \( M_{n-1} \)人で交換しているので\( M_{n-1} \)通りの交換方法があります.遅れてきた人は,この仲間外れにされている人と交換すれば\( n+1 \)人とも全員が幸せです.ここで本当に怖いのは仲間外れにされる人が誰になるか分からないことです.つまり,この場合も仲間外れにされる人の選び方\( n \)通りを考慮して\( nM_{n-1} \)通りあります。

(i), (ii)から\( n+1 \)人でプレゼント交換をする方法は

\( M_{n+1}=nM_{n}+nM_{n-1}=n\left( M_{n}+M_{n-1} \right) \)

の場合だけあります.\( M_{3}=2,M_{4}=9 \)は分かっていますので

\( M_{5}=4\left( M_{4}+M_{3} \right)=4\left( 9+4 \right)=44 \)

と求まります.

 このように漸化式を繰り返して用いればモンモール数を求めることができます..

最後に

 実際のプレゼント交換の場では「自分の欲しいものがあたる」か「みんなで盛り上がれる」となれば何でもよいので,場合の数を気にすることはないでしょうね.うっかり、「今回は何通りの場合があるよ」と言ってしまうと,周りから白い目で見られるでしょうから気を付けてください.

投稿者:玉島 亮

  • 役職
    数学科講師
  • 講師歴・勤務歴
    25年
  • 出身大学
    九州大学理学部
  • 特技・資格
    ソフトウェア開発技術者
  • 趣味
    読書・数学
  • 出身地
    奈良県
  • お勧めの本
    ここは今から倫理です

受験生への一言
「知らない」、「分からない」は成長できるチャンスです。