錯乱

組合せ数学において、乱れとは、集合の要素の順列のうち、どの要素も元の位置には現れない順列のことである。言い換えれば、乱れとは不動点を持たない順列のことである。

$大きさn$ の集合の乱れの数は、 $n$ の素因数分解、 $n$ 次の乱れ数、あるいは $n$ 次のド・モンモール数（ピエール・レモン・ド・モンモールにちなんで $）$ として知られている。素因数分解の一般的な表記法には $、!$ $n$ 、 $Dn$ $、$ $dn$ $、$ n¡などがある $。$ ^[a]^[1]^[2]

$n$ $> 0$ の場合、サブファクタリング $!$ $nは$ $⁠$ に最も近い整数に等しい。 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n !/e⁠$ 、ここで $n!は$ $n$ の階乗を表し、 $e$ $\approx 2.718281828\dots$ はオイラー数です。^[3]

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

例

教授が4人の学生（A、B、C、D）にテストを出し、お互いのテストを採点させたいとします。教授がテストを学生に返却し、どの学生も自分のテストを受け取らないようにするには、何通りの方法がありますか？テストを返却する24通りの組み合わせ（4通り！）のうち、

ABCD、	AB DC、	A CB D、	CDB、	DBC、	D C B、
BA CD、	BADC、	BCA D、	BCDA、	BDAC、	BD C A、
CAB D、	CADB	C B A D	C B DA、	CDAB、	CDBA、
DABC、	DA C B、	D B AC、	D BC A、	DCAB、	DCBA。

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

問題の別のバージョンは、それぞれ異なる人に宛てたn通の手紙を、正しく宛名が書かれた封筒に手紙が 1 通も入らぬよう、あらかじめ宛名が書かれたn個の封筒に入れる方法の数を問うときに発生します。

混乱の数を数える

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

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

P _{i は}h ₁以外の帽子を受け取る。この場合、 n − 1 人の人々とn − 1 個の帽子で問題を解くのと同じである。なぜなら、 P ₁ 以外の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を受け取ることができない。
P _{i は}h ₁を受け取ります。この場合、問題はn − 2 人、n − 2 個の帽子に簡略化されます。なぜなら、P _{1 は}h _iの帽子を受け取り、 P _{i は}h ₁の帽子を受け取ったため、実質的にどちらもそれ以上の考慮の対象から外れるからです。

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

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

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

*n要素集合（* OEISのシーケンスA000166）のnが小さい場合の乱れの数
n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
！n	1	0	1	2	9	44	265	1,854	14,833	133,496	1,334,961	14,684,570	176,214,841	2,290,792,932

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

!n=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor

について

n\geq 1,

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

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

次の再帰も成り立つ：^[6] $!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 個のオブジェクトのいずれも固定しない順列であるため、これは次のことを意味する。 $1\leq k\leq n$ $S_{k}$ $(n-i)!$ ${\textstyle {n \choose i}}$ ${\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}(n-i)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!},\end{aligned}}$ $!n=n!-\left|S_{1}\cup \dotsm \cup S_{n}\right|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}~.$

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

異常数の増加n∞に近づく

とを代入すると、すぐに次の式が得られます。これは、多数のオブジェクトをランダムに選択した順列が乱れとなる確率の極限です。確率は $nが$ 増加するにつれて非常に速くこの極限に収束します。そのため、 $!$ $nは$ $n$ $!/$ $e$ に最も近い整数です $。$ 上記の片対数グラフは、乱れのグラフが順列のグラフよりほぼ一定値だけ遅れていることを示しています。 $!n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$ $e^{x}=\sum _{i=0}^{\infty }{x^{i} \over i!}$ ${\textstyle x=-1}$ $\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] $!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),$ $m$ $B_{k}$ $k$ $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] $\int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)\ e^{-x}dx,$

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

計算複雑性

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

階乗値と乱れ値の表
$n$	順列 $n!$	乱れ $!n$	${\frac {!n}{n!}}$
0	1 =1×10 ⁰	1 =1×10 ⁰	= 1
1	1 =1×10 ⁰	0	= 0
2	2 =2×10 ⁰	1 =1×10 ⁰	= 0.5
3	6 =6×10 ⁰	2 =2×10 ⁰	≈0.33333 33333
4	24 =2.4×10 ¹	9 =9×10 ⁰	= 0.375
5	120 =1.20×10 ²	44 =4.4×10 ¹	≈0.36666 66667
6	720 ＝7.20×10 ²	265 ＝2.65×10 ²	≈0.36805 55556
7	5,040 =5.04×10 ³	1,854 ≈1.85×10 ³	≈0.36785,71429
8	40,320 ≈4.03×10 ⁴	14,833 ≈1.48×10 ⁴	≈0.36788 19444
9	362,880 ≈3.63×10 ⁵	133,496 ≈1.33×10 ⁵	≈0.36787 91887
10	3,628,800 ≈3.63×10 ⁶	1,334,961 ≈1.33×10 ⁶	≈0.36787 94643
11	39,916,800 ≈3.99×10 ⁷	14,684,570 ≈1.47×10 ⁷	≈0.36787 94392
12	4億7,900万1,600 約4.79万×10^億	1億7,621万4,841 約1.76万×10^億	≈0.36787 94413
13	6,227,020,800 ≈6.23×10 ⁹	2,290,792,932 ≈2.29×10 ⁹	≈0.36787 94412
14	87,178,291,200 ≈8.72×10 ¹⁰	32,071,101,049 ≈3.21×10 ¹⁰	≈0.36787 94412
15	1,307,674,368,000 ≈1.31×10 ¹²	481,066,515,734 ≈4.81×10⁻¹	≈0.36787 94412
16	20,922,789,888,000 ≈2.09×10 ¹³	7,697,064,251,745 ≈7.70×10 ¹²	≈0.36787 94412
17	355,687,428,096,000 ≈3.56×10⁻¹⁴	130,850,092,279,664 ≈1.31×10 ¹⁴	≈0.36787 94412
18	6,402,373,705,728,000 ≈6.40×10 ¹⁵	2,355,301,661,033,953 ≈2.36×10 ¹⁵	≈0.36787 94412
19	121,645,100,408,832,000 ≈1.22×10 ¹⁷	44,750,731,559,645,106 ≈4.48×10 ¹⁶	≈0.36787 94412
20	2,432,902,008,176,640,000 ≈2.43×10 ¹⁸	895,014,631,192,902,121 ≈8.95×10 ¹⁷	≈0.36787 94412
21	51,090,942,171,709,440,000 ≈5.11×10 ¹⁹	18,795,307,255,050,944,540 ≈1.88×10 ¹⁹	≈0.36787 94412
22	1,124,000,727,777,607,680,000 ≈1.12×10 ²¹	413,496,759,611,120,779,881 ≈4.13×10 ²⁰	≈0.36787 94412
23	25,852,016,738,884,976,640,000 ≈2.59×10 ²²	9,510,425,471,055,777,937,262 ≈9.51×10 ²¹	≈0.36787 94412
24	620,448,401,733,239,439,360,000 ≈6.20×10 ²³	228,250,211,305,338,670,494,289 ≈2.28×10 ²³	≈0.36787 94412
25	15,511,210,043,330,985,984,000,000 ≈1.55×10 ²⁵	5,706,255,282,633,466,762,357,224 ≈5.71×10 ²⁴	≈0.36787 94412
26	403,291,461,126,605,635,584,000,000 ≈4.03×10 ²⁶	148,362,637,348,470,135,821,287,825 ≈1.48×10 ²⁶	≈0.36787 94412
27	10,888,869,450,418,352,160,768,000,000 ≈1.09×10 ²⁸	4,005,791,208,408,693,667,174,771,274 ≈4.01×10 ²⁷	≈0.36787 94412
28	304,888,344,611,713,860,501,504,000,000 ≈3.05×10 ²⁹	112,162,153,835,443,422,680,893,595,673 ≈1.12×10 ²⁹	≈0.36787 94412
29	8,841,761,993,739,701,954,543,616,000,000 ≈8.84× ^10⁻³	3,252,702,461,227,859,257,745,914,274,516 ≈3.25×10 ³⁰	≈0.36787 94412
30	265,252,859,812,191,058,636,308,480,000,000 ≈2.65×10 ³²	97,581,073,836,835,777,732,377,428,235,481 ≈9.76×10 ³¹	≈0.36787 94412

脚注

^ 「subfactorial」という名称はウィリアム・アレン・ウィットワースに由来する。^[1]

参考文献

^ ab Cajori, Florian (2011). 『数学表記法の歴史：2巻1冊』Cosimo, Inc. p. 77. ISBN 9781616405717– Google経由
^ グラハム、ロナルド・L.、クヌース、ドナルド・E.、パタシュニク、オーレン (1994).具体的な数学. マサチューセッツ州レディング: アディソン・ウェズリー. ISBN 0-201-55802-5。
^ abc Hassani, Mehdi (2003). 「Derangements and applications」. Journal of Integer Sequences . 6 (1). Article 03.1.2. Bibcode :2003JIntS...6...12H – via cs.uwaterloo.ca
^ ド・モンモール、PR (1713) [1708]。Essay d'analyse sur les jeux de huge (フランス語) (Revue & augmentée de plusieurs Lettres、第 2 版)。フランス、パリ: ジャック・キヨー (1708) / ジャック・キヨー (1713)。
^ スコヴィル、リチャード (1966). 「帽子チェック問題」.アメリカ数学月刊. 73 (3): 262– 265. doi :10.2307/2315337. JSTOR 2315337.
^ abc スタンレー、リチャード(2012).列挙的組合せ論第1巻(第2版). ケンブリッジ大学出版局. 例2.2.1. ISBN 978-1-107-60262-5。
^ ワイスタイン、エリック・W.「Subfactorial」。MathWorld
^ Bizley, MTL (1967年5月). 「錯乱に関するノート」. Math. Gaz . 51 (376): 118– 120. doi :10.2307/3614384. JSTOR 3614384.
^ Hassani, Mehdi (2020). 「積分による順列の乱れと交代和」. Journal of Integer Sequences . 23.記事20.7.8.
^ Even, S.; Gillis, J. (1976). 「Derangements and Laguerre polynomials」 . Mathematical Proceedings of the Cambridge Philosophical Society . 79 (1): 135– 143. Bibcode :1976MPCPS..79..135E. doi :10.1017/S0305004100052154. S2CID 122311800. 2011年12月27日閲覧。
^ Lubiw, Anna (1981). 「グラフ同型性に類似したNP完全問題のいくつか」. SIAM Journal on Computing . 10 (1): 11– 21. doi :10.1137/0210002. MR 0605600.
^ Babai, László (1995). 「自己同型群、同型性、再構成」. 組合せ論ハンドブック(PDF) . 第1巻、第2巻. アムステルダム, オランダ: Elsevier. 第27章、pp. 1447–1540. MR 1373683 – cs.uchicago.edu経由.

外部リンク

ジョン・バエズ(2003). 「Let's get deranged!」(PDF) – via math.ucr.edu.
ボガート、ケネス・P.、ドイル、ピーター・G. (1985).「メネジェ問題の非性差別的解」 – math.dartmouth.eduより。
ワイスタイン、EW「錯乱」。 MathWorld / Wolfram Research – mathworld.wolfram.com経由。

[2] 「subfactorial」という名称はウィリアム・アレン・ウィットワースに由来する。^[1]

[Cajori-2011-1] Cajori, Florian (2011). 『数学表記法の歴史：2巻1冊』Cosimo, Inc. p. 77. ISBN 9781616405717– Google経由

[3] グラハム、ロナルド・L.、クヌース、ドナルド・E.、パタシュニク、オーレン (1994).具体的な数学. マサチューセッツ州レディング: アディソン・ウェズリー. ISBN 0-201-55802-5。

[Hassani2003-4] Hassani, Mehdi (2003). 「Derangements and applications」. Journal of Integer Sequences . 6 (1). Article 03.1.2. Bibcode :2003JIntS...6...12H – via cs.uwaterloo.ca

[5] ド・モンモール、PR (1713) [1708]。Essay d'analyse sur les jeux de huge (フランス語) (Revue & augmentée de plusieurs Lettres、第 2 版)。フランス、パリ: ジャック・キヨー (1708) / ジャック・キヨー (1713)。

[6] スコヴィル、リチャード (1966). 「帽子チェック問題」.アメリカ数学月刊. 73 (3): 262– 265. doi :10.2307/2315337. JSTOR 2315337.

[EC1-7] スタンレー、リチャード(2012).列挙的組合せ論第1巻(第2版). ケンブリッジ大学出版局. 例2.2.1. ISBN 978-1-107-60262-5。

[Mathworld-Subfactorial-8] ワイスタイン、エリック・W.「Subfactorial」。MathWorld

[9] Bizley, MTL (1967年5月). 「錯乱に関するノート」. Math. Gaz . 51 (376): 118– 120. doi :10.2307/3614384. JSTOR 3614384.

[10] Hassani, Mehdi (2020). 「積分による順列の乱れと交代和」. Journal of Integer Sequences . 23.記事20.7.8.

[11] Even, S.; Gillis, J. (1976). 「Derangements and Laguerre polynomials」 . Mathematical Proceedings of the Cambridge Philosophical Society . 79 (1): 135– 143. Bibcode :1976MPCPS..79..135E. doi :10.1017/S0305004100052154. S2CID 122311800. 2011年12月27日閲覧。

[12] Lubiw, Anna (1981). 「グラフ同型性に類似したNP完全問題のいくつか」. SIAM Journal on Computing . 10 (1): 11– 21. doi :10.1137/0210002. MR 0605600.

[13] Babai, László (1995). 「自己同型群、同型性、再構成」. 組合せ論ハンドブック(PDF) . 第1巻、第2巻. アムステルダム, オランダ: Elsevier. 第27章、pp. 1447–1540. MR 1373683 – cs.uchicago.edu経由.