Derangement

Number of possible permutations and derangements of n elements. n ! ( n factorial ) is the number of n -permutations; ! n ( n subfactorial) is the number of derangements – n -permutations where all of the n elements change their initial places.

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

大きさnの集合の乱れの数は、nの階乗、n 次の乱れ数、またはn 次のド・モンモール数（ピエール・レモン・ド・モンモールにちなんで）として知られています。一般的に用いられる階乗の表記法には、! n、Dn _、 dn _、またはn¡ などがあります。[ ^{a] [1] [2]}

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

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

例

9つの錯誤（24通りの順列から）が強調表示されています。

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

ABCD、	AB DC、	A CB D、	A CDB、	A DBC、	A D C B、
BA CD、	BADC、	BCA D、	BCDA、	BDAC、	BD CA、
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通の手紙を、宛先が書かれた n個の封筒に入れ、正しく宛名が書かれた封筒に手紙が1通も入らないようにする方法の数を求めるときに生じます。

乱れの数を数える

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

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

1. P _i receives a hat other than h ₁ . This case is equivalent to solving the problem with n  − 1 people and n  − 1 hats because for each of the n  − 1 people besides P ₁ there is exactly one hat from among the remaining n  − 1 hats that they may not receive (for any P _j besides P _i , the unreceivable hat is h _j , while for P _i it is h ₁ ). Another way to see this is to rename h ₁ to h _i , where the derangement is more explicit: for any j from 2 to n , P _j cannot receive h _j .
2. P _i receives h ₁ . In this case the problem reduces to n  − 2 people and n  − 2 hats, because P ₁ received h _i ' s hat and P _i received h ₁ 's hat, effectively putting both out of further consideration.

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に対するn要素集合（ OEISのシーケンスA000166 ）の乱れの数

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の様々な表現があります。これらには、 およびが 含まれます。$${\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 {!(n-i)},\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 (n-i)!}$ ${\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}(n-i)!\\&=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!}}~.}$$

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

乱れの数の増加n∞に近づくにつれて

とを代入することで、 すぐ に次の式が得られます。 これは、多数のオブジェクトのランダムに選択された順列が乱れである確率 の極限です。確率は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に含まれる関数 ( f ,  g )のペアの数を知りたいことがよくあります。そして、 Aのすべてのaに対して、f ( a ) ≠ g ( a ) となります。言い換えれば、各fとgに対して、 f ( a ) = φ( g ( a ) )となるようなSの乱れ φ が存在します。

別の一般化は次の問題です

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

For instance, for a word made of only two different letters, say n letters A and m letters B, the answer is, of course, 1 or 0 according to whether n = m or not, for the only way to form an anagram without fixed letters is to exchange all the A with B, which is possible if and only if n = m. In the general case, for a word with n₁ letters X₁, n₂ letters X₂, ..., n_r letters X_r, it turns out (after a proper use of the inclusion-exclusion formula) that the answer has the form $${\displaystyle \int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)\ e^{-x}dx,}$$ for a certain sequence of polynomials P_n, where P_n has degree n. But the above answer for the case r = 2 gives an orthogonality relation, whence the P_n's are the Laguerre polynomials (up to a sign that is easily decided).^[10]

${\displaystyle \ \int _{0}^{\infty }(t-1)^{z}e^{-t}dt\ }$ in the complex plane

In particular, for the classical derangements, one has that $${\displaystyle !n={\frac {\Gamma (n+1,-1)}{e}}=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx}$$ where ${\displaystyle \Gamma (s,x)}$ is the upper incomplete gamma function.

Computational complexity

It is NP-complete to determine whether a given permutation group (described by a given set of permutations that generate it) contains any derangements.^[11][12]

Table of factorial and derangement values

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

Footnotes

1. The name "subfactorial" originates with William Allen Whitworth.^[1]

References

1. Cajori, Florian (2011). A History of Mathematical Notations: Two volumes in one. Cosimo, Inc. p. 77. ISBN 9781616405717 – via Google.
2. Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics. Reading, MA: Addison–Wesley. ISBN 0-201-55802-5.
3. Hassani, Mehdi (2003). "Derangements and applications". Journal of Integer Sequences. 6 (1). Article 03.1.2. Bibcode:2003JIntS...6...12H – via cs.uwaterloo.ca.
4. de Montmort, PR (1713) [1708]. Essay d'analyse sur les jeux de hazard (フランス語) (Revue & augmentée de plusieurs Lettres, seconde ed.). Paris, FR: Jacque Quillau (1708) / Jacque Quillau (1713).
5. Scoville, Richard (1966). "The Hat-Check Problem". American Mathematical Monthly . 73 (3): 262– 265. doi :10.2307/2315337. JSTOR  2315337.
6. Stanley, Richard (2012). Enumerative Combinatorics, volume 1 (2 ed.). Cambridge University Press. Example 2.2.1. ISBN 978-1-107-60262-5.
7. Weisstein, Eric W.「Subfactorial」. MathWorld .
8. Bizley, MTL (1967年5月). 「A note on derangements」. Math. Gaz . 51 (376): 118–120 . doi :10.2307/3614384. JSTOR  3614384.
9. Hassani, Mehdi (2020). 「Derangements and Alternating Sum of Permutations by Integration」. Journal of Integer Sequences . 23. Article 20.7.8
10. 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日閲覧.
11. Lubiw, Anna (1981). 「グラフ同型性に類似したNP完全問題のいくつか」. SIAM Journal on Computing . 10 (1): 11– 21. doi :10.1137/0210002. MR  0605600
12. Babai, László (1995). 「自己同型群、同型、再構成」. 組合せ論ハンドブック(PDF) . 第1巻、第2巻. アムステルダム、オランダ: Elsevier. 第27章、1447～1540ページ. MR  1373683 – cs.uchicago.edu経由.

外部リンク

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