そもそも攪乱とは
攪乱順列というモノがあります（検索検索ぅ）
以下有名題でだいたいの輪郭を説明いたします
有名題
N人でプレゼント交換会やります。プレゼントはランダムで回しあいます。
自分の準備したプレゼントが自分に帰ってくるかわいそうな人が一人でもいる確率は？
なおNは非常に大きい数だとする
答え
大体 $1-\frac{1}{e}$ (なんで？というのは省略)
問題文の言い変え
対称群$S_n$の元のうち、攪乱ではない元は全体の何%存在するか
だったらさ
交代群$A_n$だったらどうなるのか気になるやん
とりあえずの予想
割合一緒っしょ。てか$\frac{|S_n|}{2}=|A_n|$だし、攪乱の個数も$\frac{1}{2}$じゃないの？
数学チックに考えてみる前にプログラミングでごり押しごり押し
以下の関数を作りたい
・対称群を作る関数
・対称群を交代群とそれ以外に分ける関数
（以下、偶集合($E_n=A_n$)と奇集合($O_n$)と書くことにします）
(つまり$S_n$を$E_n$と$O_n$に分ける関数を作りたい)
・与えられた集合の中で攪乱でない物の個数を返す関数
この3つがあれば自由に遊べそうなのでまずは作ってみます。
（$|S_n|=n!$なので、ある程度意識しないと遅くなりそうだが、今回は最大n=12程度の軽い調査の予定なので、高度なアルゴリズムなど用いません（用いれません））
とりあえず作るぞ～
頑張れChatGPT O3!!!(階乗じゃないです)
from itertools import permutations
def is_even_permutation(perm):
"""置換が偶置換ならTrue、奇置換ならFalseを返す"""
count = 0 # 転倒数のカウント
n = len(perm)
for i in range(n):
for j in range(i + 1, n):
if perm[i] > perm[j]: # 転倒のペアをカウント
count += 1
return count % 2 == 0 # 偶数ならTrue（偶置換）、奇数ならFalse（奇置換）
def generate_permutations(n):
"""(1,2,...,n) の全順列をリストに格納して返す"""
return list(permutations(range(1, n + 1)))
def split_even_odd_permutations(perms):
"""全順列のリストを偶置換のリストと奇置換のリストに分けて返す"""
even_perms = []
odd_perms = []
for perm in perms:
if is_even_permutation(perm):
even_perms.append(perm)
else:
odd_perms.append(perm)
return even_perms, odd_perms
def count_non_derangements(perms):
"""固定点を持つ置換（攪乱でないもの）の個数を返す"""
count = 0
n = len(perms[0]) # 順列の長さ（n）
for perm in perms:
if any(perm[i] == i + 1 for i in range(n)): # 固定点があるか判定
count += 1
return count
# 例
n = 3
perms = generate_permutations(n)
even_list, odd_list = split_even_odd_permutations(perms)
non_derangements_count = count_non_derangements(perms)
print("全順列:", perms)
print("偶置換のみ:", even_list)
print("奇置換のみ:", odd_list)
print("攪乱でない置換の個数:", non_derangements_count)
実行結果
N=8
偶置換かつ攪乱じゃないやつ: 12747
奇置換かつ攪乱じゃないやつ: 12740
攪乱でない置換の個数: 25487
え？偶数と奇数の個数丁度半分ずつじゃないの？
色々調べるか
N=6
偶置換かつ攪乱の個数: 130
奇置換かつ攪乱の個数: 135
攪乱の個数: 265
N=7
偶置換かつ攪乱の個数: 930
奇置換かつ攪乱の個数: 924
攪乱の個数: 1854
N=8
偶置換かつ攪乱の個数: 7413
奇置換かつ攪乱の個数: 7420
攪乱の個数: 14833
N=9
偶置換かつ攪乱の個数: 66752
奇置換かつ攪乱の個数: 66744
攪乱の個数: 133496
N=10
偶置換かつ攪乱の個数: 667476
奇置換かつ攪乱の個数: 667485
攪乱の個数: 1334961
んーーー、法則性ありそうだね。
とりあえずタイトルの回収はしておきますか
交代群(A_n)の攪乱度合いについて
$A_n$でも大体$1-\frac{1}{e}$だよ！！！（多分）
だけど興味の対象は完全にズレましたね。この規則的なズレ。絶対に何か理由があるはず。見つけたい。一般化したい。解明したい。
このズレを含む式を求めることが出来たら、上記の度合いも正当化される。
目標を変換しましょう。日曜数学っぽくなってきた。自由に遊ぼう。
あらたな目標
$E_n$と$O_n$の攪乱元の個数を求める一般式が欲しい！！！
ちょっと定義
攪乱元の個数を返す関数を$C(X)$と定義します
$C(S_n)=n! \sum_{k=2}^{n} \frac{(-1)^k}{k!}$ということですね（これは有名な奴）
$C(E_n)$, $C(O_n)$を求めたい
現状分かっていること
・$C(E_n)$, $C(O_n)$はnによって大小関係が変わりそう
・当然だが $C(S_n)=C(E_n)+C(O_n)$
ここから武器を増やしていきたいですね
色々実験した
~大体一日つぶれた~
天啓が降りてきた
行列式使えるんじゃね？？
・行列式っていろんな定義のやつあるけど$sgn(\sigma)$を使っためんどくさいやつあったよな
・あの偶奇(sgn)に目を付けたやつ
・行列の中身を1or0にすればいい感じに出来る...?
例えばだけど、これってどうなの...?
X=
\begin{bmatrix}
0 & 1 & 1 & \cdots & 1 \\
1 & 0 & 1 & \cdots & 1 \\
1 & 1 & 0 & \cdots & 1 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & 1 & 1 & \cdots & 0
\end{bmatrix}
これを考えてみると
・対角線上は0, 言い換えると固定点を持つもの、言い換えると「攪乱ではない元」をすべて削除できる
・偶は+, 奇は-で纏められる。
すなわち
$C(E_n)+C(O_n)=C(S_n)$
$C(E_n)-C(O_n)=X$
だよね..., これXが求められたら連立方程式で終わりじゃん！！！！
こんな綺麗な行列式なんて、絶対Google先生知ってるやろ！！！
実際$(n-1)\cdot(-1)^{n-1}$になるらしい
解いてみた
$C(E_n)=\frac{C(S_n)+X}{2}$, $C(O_n)=\frac{C(S_n)-X}{2}$
$C(E_n)=\frac{C(S_n)+(n-1)\cdot(-1)^{n-1}}{2}$, $C(O_n)=\frac{C(S_n)-(n-1)\cdot(-1)^{n-1}}{2}$
$C(E_n)=\frac{n! \sum_{k=2}^{n} \frac{(-1)^k}{k!}+(n-1)\cdot(-1)^{n-1}}{2}$, $C(O_n)=\frac{n! \sum_{k=2}^{n} \frac{(-1)^k}{k!}-(n-1)\cdot(-1)^{n-1}}{2}$
一般式、みーつけた
検算タイム (再掲 N=10)
偶置換かつ攪乱の個数: 667476
奇置換かつ攪乱の個数: 667485
攪乱の個数: 1334961
$C(E_{10})=\frac{1334961-9}{2}=667,476$
$C(O_{10})=\frac{1334961+9}{2}=667,485$
一致してるわ
まとめ
・$A_n$も攪乱度合いは$\frac{1}{e}$に収束する
・偶置換、奇置換の攪乱の個数の一般式が得られた
・行列式、すげー
追記
OIESにこの数列が普通にあったので最初に調べておけばよかった。
まあ、楽しい休日だったのでこれはこれでよし