完全順列

完全順列とモンモール数

完全順列は、整数の集合 {1, 2, 3, …, n} の順列の一つであり、特に i 番目の要素が i でない場合のものを指します。これを英語で complete permutations または derangement と言います。この性質を持つ順列は不動点を持たず、位置における特定の条件を満たす必要があります。

モンモール数

完全順列の総数を表すのがモンモール数です。この数はしばしば !n のように表記され、フランスの数学者ピエール・モンモールにちなんで名付けられています。モンモール数を小さい順に並べると、以下のような系列になります：

0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961…（詳細な数列はオンライン整数列大辞典 A166 を参照ください）。

完全順列の具体例

例えば、3つの整数を持つ場合、完全順列を計算すると、次の2通りの並べ方が可能です。

• - (2, 3, 1)
• - (3, 1, 2)

4つの整数の場合になると、可能な完全順列は以下のように9通りとなります：

• - (2, 1, 4, 3)
• - (2, 3, 4, 1)
• - (2, 4, 1, 3)
• - (3, 1, 4, 2)
• - (3, 4, 1, 2)
• - (3, 4, 2, 1)
• - (4, 1, 2, 3)
• - (4, 3, 1, 2)
• - (4, 3, 2, 1)

このように、次第に組み合わせの数は増えていきます。特に n=1 の場合は完全順列が存在せず、n=2 では1通り、n=3 では2通りと、データは指数的に増加します。

漸化式

モンモール数を求めるための漸化式は次のように表されます：

$$
a_{n} = (n - 1)(a_{n-1} + a_{n-2})， ext{for } n ext{ ≧ } 3$$

この式は、n 番目の数字をどのように選ぶかによる場合分けがもとになっています。具体的には、i 番目に n が配置されているかどうかにより、残りの数字の並べ方が変わります。この方法を用いて、初期条件 a1 = 0, a2 = 1 を利用し、n に応じたメール数を計算できます。

確率論

完全順列の確率についても言及する必要があります。n個の要素を無作為に配置するとき、それが完全順列になる確率は次のように表されます：

$$rac{a_n}{n!} = ext{Sum } rac{(-1)^{k}}{k!}$$

nが無限大に近づくとこの確率は約36.788%になります。つまり大量の要素で無作為に並べた際、自分の持ち物が自分の所属する場所に戻る確率は予想外に高くなります。

具体的な確率の計算

例えば、n = 5 の場合、5人の中で各自が持ち込んだプレゼントを分けるとき、誰かが自分の持ち物を引く確率は次の式で計算されます：

$$p_{5} = rac{5! - 44}{5!} = rac{76}{120} = 0.6333$$

同様に、n = 10 の場合の確率はおおよそ0.6321となります。これらのデータは、参加者の数が多くなるほど、特定の条件を満たす確率が過去に予測されていたよりも高いことを示唆しています。

包除原理による解析

モンモール数を求める他の手段として、包除原理も有用です。この原理を用いると、特定の条件を満たさないように置換の集合を計算することができます。具体的には、固定されない数字の選び方を数え上げ、次第に全体の可能性へと展開していく方法です。

結論

完全順列とモンモール数は、数学において非常に興味深く重要な概念であり、確率論や組合せ論に深く関連しています。適切な条件下における数の並べ替えの理解は、さまざまな応用にも通じる基盤を提供します。

もう一度検索