完全順列(Derangement)とは
【例題】5 人でプレゼントを持ち寄ってランダムに交換したとき、誰も自分のプレゼントに当たらない順列は何通り？
これが完全順列の例でその個数をフランスの数学者ピエール・モンモールに因んでモンモール数と言うそうです。この求め方について調べました。
以下のリンクに詳しい説明と公式が載っていますが、今回は後の応用も考えて包除原理を用いたものを使います。
攪乱順列（完全順列）の個数を求める公式（高校数学の美しい物語）
1 から n までの整数を並び替えてできる順列のうち，すべての i について「i 番目が i でない」を満たすものの個数
包除原理を用いて完全順列の式を求める
「完全順列ではない」= 「1が移動しない」または「2が移動しない」または …「nが移動しない」と考えて
A_i : iが移動しない順列の集合 \\
a_n = n!-|A_1 \cup A_2 \cup \dots \cup A_n | \\
この和集合の部分を包除原理を用いて \\
積集合に変換します \\
a_n = n!-(\sum_i |A_i| \\
-\sum_{i<j} |A_i \cap A_j| \\
+\sum_{i<j<k} |A_i \cap A_j \cap A_k| \\
- \cdots + (-1)^{n-1}|A_1 \cap A_2 \cap \dots \cap A_n| )\\
以下のように積集合の数が計算できるので
\sum_{i<j}|A_i| = {}_nC_1 (n-1)! \dots (式1)\\
\sum_{i<j<k}|A_i \cap A_j| = {}_nC_2 (n-2)! \dots (式２)\\
従って$a_n$は以下の式で表されます。
a_n = n!- \sum_{k=1}^{n}(-1)^{k-1} {}_nC_k (n-k)! \\
= n!- n!\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k!} \\
= n!\sum_{k=2}^{n}\frac{(-1)^{k}}{k!} \\
これをそのままpythonで完全順列を求める関数derangeを定義して$n=2 \dots 6$で走らせます。
from math import factorial
def derange(n):
fctn = factorial(n)
return sum([(-1)**i*fctn//factorial(i) for i in range(n+1)])
for n in range(2,6+1):
print(f"n={n},derange={derange(n)}")
#n=2,der=1
#n=3,der=2
#n=4,der=9
#n=5,der=44
#n=6,der=265
【例題の解答】従って最初の例題の解答は44通りになります。
この考え方を用いていくつか他の応用問題を考えてみます。
（応用その１）部分完全順列(Partial Derangement)
【問題 1】n個のうちk個は元の数、(n-k)個は違う数になる順列を求めよ
以下のリンク（英文）に説明があります。
これは割と簡単でk個を選ぶ組み合わせが$ {}_nC_k$で残りの$(n-k)$の完全順列の数を掛ければよいですね。プログラムにすると。
from sympy import binomial
def derange_p(n, k):
return binomial(n,k)*derange(n-k)
for n in range(6+1):
print(n, [derange_p(n, n-k) for k in range(n+1) ])
#0 [1]
#1 [1, 0]
#2 [1, 0, 1]
#3 [1, 0, 3, 2]
#4 [1, 0, 6, 8, 9]
#5 [1, 0, 10, 20, 45, 44]
#6 [1, 0, 15, 40, 135, 264, 265]
（応用その2）少なくともm個は完全順列
【問題 1】n個のうち少なくともm個は元の数にならない順列の数を求めよ
この問題では包除原理を用いてきたのが役に立ちます。上記の（式1）や（式2）で積集合の数が、$n$個から$k$個を選んできたのが$m$個から$k$個を選べば良いことなるので以下のように変わります。
\sum_{i<j}|A_i| = {}_mC_1 (n-1)! \dots (式1')\\
\sum_{i<j<k}|A_i \cap A_j| = {}_mC_2 (n-2)! \dots (式２')\\
従って$a2_n$は以下の式で表されます。
a2_n = n!- \sum_{k=1}^{n}(-1)^{k-1} {}_mC_k (n-k)! \\
プログラムで、$n=8$まで求めます。
def derange_al(n,m): #: don't care
return factorial(n)-sum([(-1)**(i-1)*binomial(m,i)*factorial(n-i) for i in range(1,m+1)])
for n in range(8+1):
ar = []
for m in range(n+1):
ar.append(derange_al(n, m))
print(n, ar)
#0 [1]
#1 [1, 0]
#2 [2, 1, 1]
#3 [6, 4, 3, 2]
#4 [24, 18, 14, 11, 9]
#5 [120, 96, 78, 64, 53, 44]
#6 [720, 600, 504, 426, 362, 309, 265]
#7 [5040, 4320, 3720, 3216, 2790, 2428, 2119, 1854]
#8 [40320, 35280, 30960, 27240, 24024, 21234, 18806, 16687, 14833]
（追記 2023/05/08）
ちなみにsympyには以下の関数があるのでより簡単に求めることが出来ます。
| 完全順列 | 関数 |
|---|---|
| 個数（モンモール数） | subfactorial(n) |
| リストを列挙 | generate_derangements(list) |
使用例は以下になります。
from sympy import subfactorial
print(subfactorial(5)) # Output: 44
# 44
from sympy.utilities.iterables import generate_derangements
for i,a in enumerate(generate_derangements([1, 2, 3, 4]),1):
print(i,":",a)
#1 : [2, 1, 4, 3]
#2 : [2, 3, 4, 1]
#3 : [2, 4, 1, 3]
#4 : [3, 1, 4, 2]
#5 : [3, 4, 1, 2]
#6 : [3, 4, 2, 1]
#7 : [4, 1, 2, 3]
#8 : [4, 3, 1, 2]
#9 : [4, 3, 2, 1]
（開発環境：Google Colab）
この考え方はProject Euler: Problem 239を解くのに役に立ちます。