完全順列(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)個は違う数になる順列を求めよ

以下のリンク（英文）に説明があります。

Partial Derangement (Wolfram Mathworld)

これは割と簡単で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を解くのに役に立ちます。