完全順列　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　１ から ｎ までの自然数の書かれたカードが ｎ 枚ある。今そのカードをよく切って、下図の
ように番号順に置いていく。

　　　　

　もし、
　　　　　　　　　ａ_ｋ＝ｋ

となるような ｋ が存在するとき、「出合い」が起こったといわれる。

　このとき、出会いが全く起こらない数の並びを完全順列（または攪乱順列）という。

　出合いが起こらない場合の数を Ｆ(ｎ) とおくと、次の漸化式が成り立つ。

　　　　Ｆ(１)＝０、Ｆ(２)＝１、Ｆ(ｎ)＝（ｎ−１）（Ｆ(ｎ−１)＋Ｆ(ｎ−２)）

　この漸化式を解くと、
　　　　　　　　　　　　　

である。（→　参考：「自然対数の底 ｅ の体感」、「席替えの数理」）

　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが、平成２２年７月１０日付けで次の問題
を提起された。

　男子３人、女子３人がそれぞれ一列ずつで席が決まって並んでいたとする。

　これを席替えして、どの人も前の席からの位置が変わり、隣の異性も変わる並び方は、

の２通りしかない。そこで、問題である。

　男、女それぞれ４人が一列で並んでいたのを並び替え、どの人も前の位置と違う場
所で、しかも隣の人も違う異性になる並び方が何通りあるだろうか。


　完全順列の匂いがしたので解いてみた。

　まず、男子の並び方は、Ｆ(４)＝３（Ｆ(３)＋Ｆ(２)）＝３（２＋１）＝９ （通り）　ある。

ＢＡＤＣ　、ＣＡＤＢ　、ＤＡＢＣ　、ＢＤＡＣ　、ＣＤＡＢ　、ＤＣＡＢ　、ＢＣＤＡ　、ＣＤＢＡ　、ＤＣＢＡ

　例えば、ＢＡＤＣ　（Ａの移動した先の人がＡの移動前の位置にくる場合）について、女子の
並び方を考えよう。

　　ａ　→　３番目　または　４番目　しかない。

　　ａ　→　３番目　とすると、　ｂ　→　４番目　である。

　　　このとき、　ｃ　→　１番目　または　２番目　で、ｄ　は残りに確定である。

　　ａ　→　４番目　とすると、　ｂ　→　３番目　である。

　　　このとき、　ｃ　→　１番目　または　２番目　で、ｄ　は残りに確定である。

　よって、この場合の女子の並び方は、　ｃｄａｂ　、ｄｃａｂ　、ｃｄｂａ　、ｄｃｂａ　の４通りある。

　次に、ＣＡＤＢ　（Ａの移動した先の人がＡの移動前の位置に来ない場合）について、女子
の並び方を考えよう。

　　ａ　→　３番目　または　４番目　しかない。

　　ａ　→　３番目　とすると、　ｂ　→　１番目　である。

　　　このとき、　ｃ　→　４番目　、ｄ　→　２番目である。

　　ａ　→　４番目　とすると、　ｂ　→　１番目　または　３番目である。

　　　ｂ　→　１番目　とすると、　解なし

　　　ｂ　→　３番目　とすると、　ｃ　→　２番目　、ｄ　→　１番目である。

　よって、この場合の女子の並び方は、　ｂｄａｃ　、ｄｃｂａ　の２通りある。

　以上から、求める場合の数は、　４×３＋２×６＝２４ （通り）　ある。


（コメント）　答えは合っていますかね？自信はないです．．．ｆ(^^;)。

　．．．と上記で書きましたが、既にこの問題は当ＨＰの「お茶の時間」−「パズル＆クイズ」
の中の「色の組合せ」で解決済みでしたね！２４通りで正解です。

　当ＨＰがいつもお世話になっているＦＮさんからのご指摘（平成２２年７月１１日付け）まで
気がつきませんでした．．．ｆ(^^;)。

もしかしたらＦＮさんは、私以上に当ＨＰの内容を熟知されているかもしれないですね．．．。

　また、ＧＡＩ さんは、この問題を「男女 ｎ 人ずつ」と一般化したときの並びの総数が、ｎ を用
いて具体的に書けるかどうかも問題にしている。

　ＦＮさんによれば、５人は真面目に考えればできそうだが、ｎ人は絶望的に思えるとのこと。
私も同感です。

　５人の場合を考えるとすると

のように１行目は、１２３４５、２行目、３行目は、１２３４５の順列で各列がすべて異なるよう
な３行５列の配列は何通りあるか。

　４人のときの解答をヒントにして誘導をつけてみました。

　（１）　２行目が、２３１５４　のとき何通りあるか。
　（２）　２行目が、２３４５１　のとき何通りあるか。
　（３）　全部で何通りあるか。

　当ＨＰがいつもお世話になっているらすかるさんからの情報です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月１１日付け）

　ｎ＝３、４、５、・・・の場合の数から、ＦＮさんの問題（３）の解は、５５２通りとなる。


　らすかるさんからの情報を道しるべに、ＦＮさんの問題を考えてみよう。

（解）　完全順列の公式から、まず、２行目の順列は全部で、

　　　　　Ｆ(５)＝４（Ｆ(４)＋Ｆ(３)）＝４（９＋２）＝４４ （通り）　ある。

　　実際に、

　上記の表で赤字の場合は他の場合と異なり、２つの文字で自己完結していることに注意
しなければならない。

　例えば、次の表から、その違いが理解されることだろう。

（各テーブルで、１行目は元の順列、２行目は男子の順列、３行目以降は女子の順列）

　他の場合も同様で、したがって、求める場合の数は、　

　　４×（５×１２＋６×１３）＝５５２（通り）　となる。

　上記の表から、ＦＮさんの問題も明らかとなる。

　（１）　２行目が、２３１５４　のとき何通りあるか。・・・・・・１２通り

　（２）　２行目が、２３４５１　のとき何通りあるか。・・・・・・１３通り

　（３）　全部で何通りあるか。・・・・・・５５２通り


　上記では、ＦＮさんの問題を「数え上げる」という、とても「泥臭い」方法で解いたわけだが、
もっと綺麗に解きたいという思いはあった。ＦＮさんが、私のそんな思いに答えてくれた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２２年７月１２日付け）
（１）　２行目が、２３１５４　のとき何通りあるか。

（２）　２行目が、２３４５１　のとき何通りあるか。

　　これは樹形図等を使ってすべて書きあげるのが一番
　早い。

　　　左表から、求める場合の数は、

　　全部で、１３通り。















（３）　全部で何通りあるか。

　１行目と２行目の対応を置換とみたとき、すべての文字が動かなければならない。すべて
の置換は何個かの巡回置換の積になるが、すべての文字を動かすということは、長さ５の
巡回置換（上記の問題の（２）のタイプ）か長さ３の巡回置換と互換(長さ２の巡回置換)の積
（上記の問題の（１）のタイプ）しかない。即ち、（１２３４５）のタイプと（１２３）（４５）のタイプで
ある。

　ところで、（１２３４５）のタイプは、５個の円順列なので、４！＝２４（通り）。

　（１２３）（４５）のタイプは、１、２、３ の選び方が、₅Ｃ₃＝１０（通り）で、それぞれ（１２３）と
（１３２）の２通りあり、２０通り。互換は残った２つで決まるので１通り。よって、２０通り。

　以上から、求める場合の数は、　２４×１３＋２０×１２＝５５２（通り）　（終）

　ＦＮさんによれば、６人の場合も同様で、１２３４５６の置換ですべての文字を動かすものは
次のどれかである。

　　長さ６の巡回置換・・・・・・・・・・・・・（１２３４５６）のタイプ
　　長さ４の巡回置換と互換の積・・・・（１２３４）（５６）のタイプ
　　長さ３の巡回置換２個の積・・・・・・（１２３）（４５６）のタイプ
　　互換３個の積・・・・・・・・・・・・・・・・（１２）（３４）（５６）のタイプ

　この４つのタイプについて、それぞれが何通りあるか、そしてそれぞれの場合の３行目が
何通りあるかを求めなければならない。

　やっかいなのは１つだけ、即ち、１番目のタイプの３行目の個数を数えること。５人のとき
の（２）に当たる問題。普通は樹形図等ですべて書くことになる。


　６人のときを解くのに、「普通は樹形図等を作って数えることになる」と書きましたが、実は
（非常に難しいですが）計算で解けます。（平成２２年７月１３日付け）

　123456 　　ABCDEFは123456の順列で左の配列において各列はすべて異なる。
　234561 　　この条件を満たす３行６列の配列は何通りあるか。
　ABCDEF

　この問題は「Menage problem」あるいは「Probleme des menages」といわれる有名な
問題と同じになります。１９世紀に出され、１９３４年に一般の場合の式が作られ、１９４３年に
始めて証明されたというから相当難しい問題です。次の問題です。

　６組の夫婦を円形のテーブルに次の条件を満たすように着席させる並び方は何通り
あるか。
　　　　　　男女は交互に座り、夫婦は隣り合わない。

　６組の夫婦を、Ａａ、Ｂｂ、Ｃｃ、Ｄｄ、Ｅｅ、Ｆｆ　とし、まず、ａ、ｂ、ｃ、ｄ、ｅ、ｆ　を円形に間を１つ

ずつあけながら並べる。空いている席に、１、２、３、４、５、６　と名前をつける。

　　　　　　　

　１、２、３、４、５、６　に、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ　を置くのだが、Ａは１と２は駄目、Ｂは２と３は
駄目、・・・・・、Fは６と１は駄目。これはまさに上の問題の状況である。

　６組の夫婦を ｎ 組の夫婦としたものが、Menage problem である。

ただし、最初の問題では、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ　の並び方だけが問題だが、Menage problem
では、ａ、ｂ、ｃ、ｄ、ｅ、ｆ　の並び方も数えるので結果は異なる。

　「Menage problem」で検索すれば、たくさんヒットします。例えば下記のWikipedia。

　　　　http://en.wikipedia.org/wiki/M%C3%A9nage_problem

上の方に書いてある

　　１２、９６、３１２０、１１５２００、５８３６３２０、３８２０７２３２０、３１４８８５４９１２０、・・・　

が男女とも動かした本来の Menage problem の解で、ｎ の場合の式が、Mn　でかいてある
ものです。

　Menage numbers and ladies-first solutions　のところに書いてある　An　が男女の片方を
固定したときの解の式で、具体的な数は、その下の

　　　　１、２、１３、８０、・・・

です。最初に書いた問題は、こちらのタイプで、８０通りということになります。

（コメント）　ＦＮさんに感謝します。


　ＧＡＩ さんから問題をいただきました。（平成２８年７月１４日付け）

　{1,2,3,4}を並べ替えたとき、元の位置にどの要素もあてはまらない並び方は、

　　2143、3142、4123、2413、3412、4312、2341、3421、4321

の９パターンが考えられる。（完全順列）

　一般に異なるn個の要素を並べたとき、そのようになるパターン数f(n)は、

　　f(n)=(n-1)*(f(n-1)+f(n-2)),f(1)=0,f(2)=1

によって与えられる。（モンモール数）

　そこで、{1,1,2,2,3,3}を勝手に並び替えたとき、どの要素も元の位置と異なるものになってい
るパターン数は？

　さらに、{1,1,2,2,3,3,4,4,･････,n,n}なら、そのパターン数は？


　ａｔさんからのコメントです。（平成２８年７月１６日付け）

　n 種類の要素 1,2,3,･････,n がそれぞれ m 個ずつあって、

　　{1,1,･･･,1,2,2,･･･,2,3,3,･･･,3,･･････････,n,n,･･･,n}

というふうに並んでいるとします。これら mn 個の要素を勝手に並び替えたとき、どの要素に
ついても、元の位置にあった要素とは異なる種類になっているような並べ方のパターン数を
A(n,m) とすると、

　A(n,m)=(1/(m!))ⁿ(Σ_k=0〜mn (-1)^k(mn-k))ⁿ)


A(n,2) の初めの10項は次のようになりました。

{A(n,2)}(n=1,･･･,10)
=[0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561]

（Maximaでの計算結果）
(A(n,2),n,1,5)：[0, 1, 10, 297, 13756]
(A(n,3),n,1,5)：[0, 1, 56, 13833, 6699824]
(A(n,4),n,1,5)：[0, 1, 346, 748521, 3993445276]
(A(n,5),n,1,5)：[0, 1, 2252, 44127009, 2671644472544]
(A(n,6),n,1,5)：[0, 1, 15184, 2750141241, 1926172117389136]
(A(n,7),n,1,5)：[0, 1, 104960, 178218782793, 1463447061709156064]


（コメント）　{1,1,2,2,3,3}を勝手に並び替えたとき、どの要素も元の位置と異なるものになって
　　　　　　いるパターン数は、ａｔ さんの結果から、A(3,2)=10　となる。実際に並べてみると、

{3,3,1,1,2,2}、{2,2,3,3,1,1}、{2,3,1,3,1,2}、{3,2,1,3,1,2}、{2,3,1,3,2,1}、{3,2,1,3,2,1}、{2,3,3,1,1,2}、
{3,2,3,1,1,2}、{2,3,3,1,2,1}、{3,2,3,1,2,1}


（追記）　ＧＡＩ さんから、ご投稿いただきました。（令和３年１２月１３日付け）

　「A000166」に載せられている完全順列(Derangements)数が、二項係数とガンマ関数との
組み合わせにより上手く計算されていくことに気付きました。

　以下、その式と計算結果の様子です。

gp > F(n)=sum(i=0,n,(-1)^(n-i)*binomial(n,i)*gamma(i+1));
gp > for(n=1,20,print(n";"F(n)))

1;0.E-38
2;1.0000000000000000000000000000000000000
3;2.0000000000000000000000000000000000000
4;9.0000000000000000000000000000000000000
5;44.000000000000000000000000000000000000
6;265.00000000000000000000000000000000000
7;1854.0000000000000000000000000000000000
8;14833.000000000000000000000000000000000
9;133496.00000000000000000000000000000000
10;1334961.0000000000000000000000000000000
11;14684570.000000000000000000000000000000
12;176214841.00000000000000000000000000000
13;2290792932.0000000000000000000000000000
14;32071101049.000000000000000000000000000
15;481066515734.00000000000000000000000000
16;7697064251745.0000000000000000000000000
17;130850092279664.00000000000000000000000
18;2355301661033953.0000000000000000000000
19;44750731559645106.000000000000000000000
20;895014631192902121.00000000000000000000



　　　以下、工事中