錯乱

組合せ 数学において、並び替えとは、集合の要素の並び替えのうち、どの要素も元の位置には現れない並び替えのことである。言い換えれば、並び替えとは、固定点を持たない並び替えのことである。

大きさnの集合の乱れの数は、nのサブ階乗、またはn 番目の乱れ数、あるいはn番目のド・モンモール数(ピエール・ルモン・ド・モンモールにちなんで )として知られています。サブ階乗の一般的な表記法には、! n、D _n、d _n、またはn ¡ などがあります 。^{[a] [1] [2]}

n > 0の場合、サブファクタリ! n はn !/ eに最も近い整数に等しくなります。ここでn ! はnの階乗を表し、e ≈ 2.718281828...はオイラー数です。^[3]

錯乱の数を数える問題は、ピエール・レイモンド・ド・モンモールが1708年に書いた「危険の分析論文」 [ ^4]で初めて考察され、1713年にニコラ・ベルヌーイもほぼ同じ頃にこの問題を解決した。

教授が 4 人の学生 (A、B、C、D) にテストを出し、お互いのテストを採点させたいとします。もちろん、どの学生も自分のテストを採点してはいけません。教授がテストを学生に返して採点してもらうには、どの方法でも何通りの方法がありますか? テストを返せる組み合わせは 24 通り (4 通り!) ありますが、

異常は 9 つしかありません (上の青い斜体で表示)。この 4 つのメンバー セットの他のすべての順列では、少なくとも 1 人の生徒に独自のテストが返されます (太字の赤で表示)。

問題の別のバージョンは、それぞれ異なる宛先に宛てられたn通の手紙を、宛先が正確に記入された封筒に手紙が 1 通も入らぬよう、宛先が記入されたn個の封筒に入れる方法の数を尋ねるときに発生します。

集合の乱れを数えることは帽子チェック問題に相当し、これはn個の帽子（h ₁からh _nと呼ぶ）をn人の人（P _1からP _nと呼ぶ）に返却し、どの帽子も持ち主に返らないようにする方法の数を考える問題である。^[5]

各人は自分のものではないn − 1 個の帽子のうちどれかを受け取ることができます。P 1_が受け取る 帽子をh _iと呼び、h _iの所有者を考えます。P _{i は}P 1_の帽子h ₁か他の帽子を受け取ります。したがって、問題は 2 つのケースに分かれます。

1. P _{i は}h ₁以外の帽子を受け取ります。この場合は、n  − 1 人の人々とn  − 1 個の帽子で問題を解くことと同じです。なぜなら、 P _1以外のn  − 1 人のそれぞれについて、残りのn  − 1 個の帽子の中から受け取ることができない帽子がちょうど 1 つあるからです( P _i以外の任意のP _jについて、受け取れない帽子はh _jですが、 P _iの場合はh ₁です)。これを確認する別の方法は、h _1をh _iに名前変更することです。この場合、混乱はより明確になります。2 からnまでの任意のjについて、P _jはh _{j を}受け取ることができません。
2. P _{i は}h _{1 を}受け取ります。この場合、問題はn  − 2 人の人々とn  − 2 個の帽子に簡略化されます。なぜなら、P _{1 は}h _iの帽子を受け取り、P _{i は}h ₁の帽子を受け取ったため、実質的にどちらもそれ以上の考慮の対象から外れるからです。

P _{1 が受け取る可能性のある}n  − 1 個のハットのそれぞれについて、 P ₂、...、  P _{n が}すべてハットを受け取る可能性のある方法の数は、2 つのケースのカウントの合計です。

これにより、ハットチェック問題の解が得られる。代数的に述べると、n要素集合 の乱れの数! nは、および^[6]に対してである。$${\displaystyle !n=\left(n-1\right){\bigl (}{!\left(n-1\right)}+{!\left(n-2\right)}{\bigr )}}$$${\displaystyle n\geq 2}$${\displaystyle !0=1}$${\displaystyle !1=0.}$

小さな長さの乱れの数は、以下の表に示されています。

! nには、上記の式に相当する さまざまな表現があります。これらには 、および が含まれます。$${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$${\displaystyle n\geq 0}$

${\displaystyle !n=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor }$のために${\displaystyle n\geq 1,}$

ここで は最も近い整数関数であり、は床関数である。^{[3] [6]}${\displaystyle \left[x\right]}$${\displaystyle \left\lfloor x\right\rfloor }$

その他の関連する式としては^{[3] [7]} や $${\displaystyle !n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor ,\quad \ n\geq 1,}$$ $${\displaystyle !n=\left\lfloor \left(e+e^{-1}\right)n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,}$$$${\displaystyle !n=n!-\sum _{i=1}^{n}{n \choose i}\cdot {!(ni)},\quad \ n\geq 1.}$$

次の再帰も成り立つ：^[6] $${\displaystyle !n={\begin{cases}1&{\text{if }}n=0,\\n\cdot \left(!(n-1)\right)+(-1)^{n}&{\text{if }}n>0.\end{cases}}}$$

n集合の乱れの数についても、非再帰的な式を導くことができる。 を、k 番目のオブジェクトを固定するn個のオブジェクトの順列の集合と定義する。これらの集合のi 個の集合の交差は、 i個のオブジェクトの特定の集合を固定し、 したがって順列を含む。そのような集合が存在するため、包含排他原理により、乱れはn 個のオブジェクト のいずれも固定しない順列であるため、次の式が成立する。 ${\displaystyle 1\leq k\leq n}$${\displaystyle S_{k}}$${\displaystyle (ni)!}$${\textstyle {n \choose i}}$$${\displaystyle {\begin{aligned}|S_{1}\cup \dotsm \cup S_{n}|&=\sum _{i}\left|S_{i}\right|-\sum _{i<j}\left|S_{i}\cap S_{j}\right|+\sum _{i<j<k}\left|S_{i}\cap S_{j}\cap S_{k}\right|+\cdots +(-1)^{n+1}\left|S_{1}\cap \dotsm \cap S_{n}\right|\\&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{n+1}{n \choose n}0!\\&=\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(ni)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!},\end{aligned}}}$$$${\displaystyle !n=n!-\left|S_{1}\cup \dotsm \cup S_{n}\right|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}~.}$$

一方、定義により、 n - i個の要素をそれぞれの場所に配置して、他のi個の要素をちょうど! i通りの方法で乱すことができる。^[8]${\displaystyle n!=\sum _{i=0}^{n}{\binom {n}{i}}\ !i}$

と を 代入すると 、 すぐに次の式が得られます 。これは、多数のオブジェクトをランダムに選択した順列が乱雑である確率 の限界です。確率はn が増加するにつれて非常に急速にこの限界に収束します。これが、! nがn !/ eに最も近い整数である理由です。上記の片対数グラフは、乱雑グラフが順列グラフよりほぼ一定の値だけ遅れていることを示しています。 $${\displaystyle !n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$$${\displaystyle e^{x}=\sum _{i=0}^{\infty }{x^{i} \over i!}}$$${\textstyle x=-1}$$${\displaystyle \lim _{n\to \infty }{!n \over n!}=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}=e^{-1}\approx 0.367879\ldots .}$$

この計算と上記の制限に関する詳しい情報は、 ランダム順列の統計に関する記事に記載されています。

ベル数による乱れの数の漸近展開は次のようになる。 ここで は任意の固定された正の整数であり、 は- 番目のベル数を表す。さらに、大きな O項によって暗示される定数はを超えない。^[9]$${\displaystyle !n={\frac {n!}{e}}+\sum _{k=1}^{m}\left(-1\right)^{n+k-1}{\frac {B_{k}}{n^{k}}}+O\left({\frac {1}{n^{m+1}}}\right),}$$${\displaystyle m}$${\displaystyle B_{k}}$${\displaystyle k}$${\displaystyle B_{m+1}}$

出会いの問題は、サイズn の集合の順列のうち、正確に k 個の固定点を持つものがいくつあるかを問うものです。

乱れは、制約された順列のより広い分野の一例です。たとえば、メネジェ問題では、異性のカップルn組がテーブルの周りに男性-女性-男性-女性-... と座っている場合、誰もパートナーの隣に座らないように座る方法は何通りあるでしょうか?

より正式には、集合AとS、および全射A → Sの集合UとVが与えられたとき、 fがUに含まれgがVに含まれ、A内のすべてのaに対してf ( a ) ≠ g ( a )となるような関数 ( f ,  g ) のペアの数を知りたいことがよくあります。言い換えると、各fおよびgに対して、 f ( a ) = φ( g ( a ))となるようなSの乱れ φ が存在するということです。

もう 1 つの一般化は次の問題です。

特定の単語の固定文字を含まないアナグラムはいくつありますか?

たとえば、n文字の A とm文字の B という 2 つの異なる文字のみで構成されている単語の場合、答えはn = mかどうかによって 1 または 0 になります。これは、固定文字を使用せずにアナグラムを作成する唯一の方法は、すべてのA をBと交換することであり、これはn = mの場合にのみ可能だからです。一般的なケースでは、n ₁文字X ₁、n ₂文字X ₂、...、n _r文字X _rの単語の場合、答えは (包含排除公式を適切に使用した後) 特定の多項式シーケンスP _nの形になります 。ここで、P _{n は}次数nです。ただし、 r = 2の場合の上記の答えは直交関係を与え、したがってP _nはラゲール多項式です(簡単に決定できる符号を除いて)。 ^[10]$${\displaystyle \int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)\ e^{-x}dx,}$$

特に、古典的な乱れについては、 となります。 ここで、 は上側の不完全ガンマ関数です。 $${\displaystyle !n={\frac {\Gamma (n+1,-1)}{e}}=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx}$$${\displaystyle \Gamma (s,x)}$

与えられた順列群（それを生成する順列の集合によって記述される）に何らかの乱れが含まれているかどうかを判断することはNP完全である。 ^{[11] [12]}

無料辞書のウィクショナリーで「derangement」を調べてください。

• Baez, John (2003)。「Let's get deranged!」(PDF) – math.ucr.edu 経由。
• Bogart, Kenneth P.; Doyle, Peter G. (1985)。「メネジェ問題の非性差別的解決」 – math.dartmouth.edu 経由。
• ワイスタイン、EW「錯乱」。 MathWorld / Wolfram Research – mathworld.wolfram.com経由。