攪乱順列（完全順列）の個数を求める公式

攪乱順列の公式とその応用例を紹介し，公式を２通りの方法で導きます。攪乱順列は，完全順列やモンモールの問題とも呼ばれます。

n = 3 n=3 n = 3 の場合を考えてみる ( 1 , 2 , 3 ) (1,2,3) ( 1 , 2 , 3 ) を「かくらんする」順列を考える。1番目が1でなく，2番目が2でなく，3番目が3でないのは ( 2 , 3 , 1 ) (2,3,1) ( 2 , 3 , 1 ) と ( 3 , 1 , 2 ) (3,1,2) ( 3 , 1 , 2 ) の2つ。つまり a 3 = 2 a_3=2 a 3 = 2

攪乱順列のことを完全順列とも言います。攪乱順列の方が漢字は難しいですが，意味は分かりやすいと思います。
n n n 個の場合の攪乱順列の数 a n a_n a n はモンモール数とも呼ばれます。
モンモール数を求める問題はモンモールの問題とも呼ばれます。

n = 2 n=2 n = 2 のときは攪乱順列は ( 2 , 1 ) (2,1) ( 2 , 1 ) の1通りです。

また，公式 a n = n ! ∑ k = 2 n ( − 1 ) k k ! a_n=n!\displaystyle\sum_^n\dfrac a n = n ! k = 2 ∑ n k ! ( − 1 ) k で n = 2 n=2 n = 2 とすることでも a 2 = 2 ! ( 1 2 ) = 1 a_2=2!\left(\dfrac\right)=1 a 2 = 2 ! ( 2 1 ) = 1 と分かります。

n = 3 n=3 n = 3 の場合は，さきほど確認したように ( 2 , 3 , 1 ) , ( 3 , 1 , 2 ) (2, 3, 1), (3, 1, 2) ( 2 , 3 , 1 ) , ( 3 , 1 , 2 ) の2通りです。 n = 3 , 4 n=3, 4 n = 3 , 4 くらいは入試問題でも多く出題されており，まれに一般の n n n に対する問題も出題されます。

( 2 , 1 , 4 , 3 ) , ( 2 , 3 , 4 , 1 ) , ( 2 , 4 , 1 , 3 ) , (2,1,4,3),(2,3,4,1),(2,4,1,3), ( 2 , 1 , 4 , 3 ) , ( 2 , 3 , 4 , 1 ) , ( 2 , 4 , 1 , 3 ) , ( 3 , 1 , 4 , 2 ) , ( 3 , 4 , 1 , 2 ) , ( 3 , 4 , 2 , 1 ) , (3,1,4,2),(3,4,1,2),(3,4,2,1), ( 3 , 1 , 4 , 2 ) , ( 3 , 4 , 1 , 2 ) , ( 3 , 4 , 2 , 1 ) , ( 4 , 1 , 2 , 3 ) , ( 4 , 3 , 1 , 2 ) , ( 4 , 3 , 2 , 1 ) (4,1,2,3),(4,3,1,2),(4,3,2,1) ( 4 , 1 , 2 , 3 ) , ( 4 , 3 , 1 , 2 ) , ( 4 , 3 , 2 , 1 )

公式を知っていれば， a 4 = 4 ! ( 1 2 − 1 6 + 1 24 ) = 9 a_4=4!\left(\dfrac-\dfrac+\dfrac\right)=9 a 4 = 4 ! ( 2 1 − 6 1 + 24 1 ) = 9 と分かります。

nが十分大きいとき（有名問題）

a n n ! = ∑ k = 2 n ( − 1 ) k k ! = ∑ k = 0 n ( − 1 ) k k ! ≒ e − 1 = 0.367 ⋯ \dfrac=\displaystyle\sum_^n\dfrac =\sum_^n\dfrac\fallingdotseq e^=0.367\cdots n ! a n = k = 2 ∑ n k ! ( − 1 ) k = k = 0 ∑ n k ! ( − 1 ) k ≒ e − 1 = 0.367 ⋯

つまり，適当に選んだ順列が攪乱順列になっている確率は約37% です（式変形の途中で指数関数のマクローリン展開を用いました）。

くじ引きで席替えしたのに席が変わらない残念な人がいる確率は大体63%（ n n n を増やしたら100%に近づきそうな気もしますが，いくら大人数でやっても63%くらいになります。）
大人数でプレゼント交換をするときに自分のプレゼントに当たる悲しい人がいる確率は大体63%

一般の n n n に対して攪乱順列の数を求めたいのですが，気合で全部書き並べるわけにはいかないので，漸化式を用います。

1の移動先を「 i i i 番目」として，攪乱順列を以下の2通りに場合分けする。

パターン1： i i i の移動先が1番目となる場合の数（交換型）

i i i の選び方が n − 1 n-1 n − 1 通りで，それぞれに対して1と i i i 以外の n − 2 n-2 n − 2 個の攪乱順列の数だけあるので，全部で ( n − 1 ) a n − 2 (n-1)a_ ( n − 1 ) a n − 2 通り。

パターン2： i i i の移動先が1番目以外となる場合の数（非交換型）

i i i の選び方が n − 1 n-1 n − 1 通りで，それぞれに対して1以外の n − 1 n-1 n − 1 個の攪乱順列の数だけあるので，全部で ( n − 1 ) a n − 1 (n-1)a_ ( n − 1 ) a n − 1 通り。

よって， a n = ( n − 1 ) ( a n − 1 + a n − 2 ) a_n=(n-1)(a_+a_) a n = ( n − 1 ) ( a n − 1 + a n − 2 )

あとは， a 2 = 1 , a 3 = 2 a_2=1, a_3=2 a 2 = 1 , a 3 = 2 のもとでこの三項間漸化式を解けばよいだけです。解き方の詳細→階乗を用いる漸化式の解法の例題3より，

a n = n ! ∑ k = 2 n ( − 1 ) k k ! a_n=n!\displaystyle\sum_^n\dfrac> a n = n ! k = 2 ∑ n k ! ( − 1 ) k が分かります。

直接求めるのは難しいので余事象を考えます。「撹乱されない」=「1が移動しない」または「2が移動しない」または ⋯ \cdots ⋯ 「nが移動しない」

i i i が移動しない順列の集合を A i A_i A i とおくと，

a n = n ! − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n| a n = n ! − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣

i i i が移動しない順列の数は， ∣ A i ∣ = ( n − 1 ) ! |A_i|=(n-1)! ∣ A i ∣ = ( n − 1 )!

i i i も j j j も移動されない順列の数は， ∣ A i ∩ A j ∣ = ( n − 2 ) ! |A_i\cap A_j|=(n-2)! ∣ A i ∩ A j ∣ = ( n − 2 )!

以下同様にして，特定の k k k 個の要素が移動されない順列の数は， ( n − k ) ! (n-k)! ( n − k )! となる。すなわち「かつ」の確率は計算できるので，包除原理より，

a n = n ! − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ = n ! − ∑ k = 1 n ( − 1 ) k − 1 n C k ( n − k ) ! = n ! − n ! ∑ k = 1 n ( − 1 ) k − 1 k ! = n ! ∑ k = 2 n ( − 1 ) k k ! a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|\\ =n!-\displaystyle\sum_^n(-1)^_n\mathrm_k(n-k)!\\ =n!-n!\displaystyle\sum_^n\dfrac\\ =n!\displaystyle\sum_^n\dfrac a n = n ! − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ = n ! − k = 1 ∑ n ( − 1 ) k − 1 n C k ( n − k )! = n ! − n ! k = 1 ∑ n k ! ( − 1 ) k − 1 = n ! k = 2 ∑ n k ! ( − 1 ) k

東京大学大学院情報理工学系研究科修了／2014年にWebサイト『高校数学の美しい物語』を立ち上げ／著書累計 50,000部突破／「わかりやすいこと」と「ごまかさないこと」の両立を意識している。 →著者情報・書籍一覧を見る