ในคณิตศาสตร์เชิงการจัดเรียง การเรียงสับเปลี่ยนที่ไม่ลงตัว (derangement)คือการเรียงสับเปลี่ยนของสมาชิก ใน เซตที่ไม่มีสมาชิกใดปรากฏในตำแหน่งเดิม กล่าวอีกนัยหนึ่ง การเรียงสับเปลี่ยนที่ไม่ลงตัวคือการเรียงสับเปลี่ยนที่ไม่มีจุดตรึง (fixed points )

จำนวนการเรียงสับเปลี่ยนของเซตขนาดnเรียกว่าจำนวนการเรียงสับเปลี่ยนลำดับ ที่n หรือแฟกทอเรียลย่อยของnหรือจำนวนเดอ มงต์มัวร์ ลำดับ ที่ n (ตั้งชื่อตาม ปิแอร์ เร ^มงด์ เดอ มงต์มัวร์ ) สัญลักษณ์ที่ใช้กันทั่วไปสำหรับแฟกทอเรียลย่อย ได้แก่D _n , d _n , ! nหรือn ¡  [ ^{a ] ​​[ 1 ] [ 2 ]}

สำหรับn > 0ค่าแฟกทอเรียลย่อยD _nจะเท่ากับจำนวนเต็มที่ใกล้เคียงที่สุดกับ⁠n !/อีโดยที่ n !หมายถึงแฟกทอเรียลของ nและ e ≈ 2.718281828...คือเลขออยเลอร์ ^{[ 3 ]}

ปัญหาของการนับการเรียงสับเปลี่ยนถูกพิจารณาครั้งแรกโดยPierre Raymond de MontmortในEssay d'analyse sur les jeux de hazard ^{[ 4 ]}ในปี 1708; เขาแก้ปัญหานี้ได้ในปี 1713 เช่นเดียวกับNicholas Bernoulliในช่วงเวลาเดียวกัน

สมมติว่าอาจารย์ให้ข้อสอบกับนักเรียน 4 คน คือ A, B, C และ D และต้องการให้นักเรียนตรวจข้อสอบของกันและกัน จะมีกี่วิธีที่อาจารย์จะคืนข้อสอบให้นักเรียนตรวจ โดยที่ไม่มีนักเรียนคนใดได้รับข้อสอบของตัวเองคืน? จากทั้งหมด24 วิธีที่เป็นไปได้ (4!) ในการคืนข้อสอบ

ABCD ,	เอบีดีซี,	เอซีบีดี ,	ซีดีบี	เอดีบีซี,	เอดีซีบี
ปริญญา ตรีซีดี	แบดซี	บีซีเอ ดี	บีซีดีเอ	บีดีเอซี ,	บีดีซีเอ,
รถแท็กซี่D ,	CADB ,	ซีบีเอดี ,	ซีบีดีเอ	ซีดีเอบี	ซีดีบีเอ
DABC ,	DA C B,	ดีบีเอซี,	ดีบีซีเอ,	ดีซีเอบี	ดีซีบีเอ

มีการเรียงสลับตำแหน่งเพียง 9 แบบ (แสดงด้วยตัวเอียงสีน้ำเงินด้านบน) ในการเรียงสลับตำแหน่งอื่นๆ ของเซตสมาชิก 4 ตัวนี้ อย่างน้อยหนึ่งคนจะได้รับข้อสอบของตนเองคืน (แสดงด้วยตัวหนาสีแดง)

ปัญหาอีกรูปแบบหนึ่งเกิดขึ้นเมื่อเราถามถึงจำนวนวิธีที่จะนำ จดหมาย nฉบับ ซึ่งแต่ละฉบับส่งถึงบุคคลที่แตกต่างกัน มาใส่ใน ซองจดหมายที่ระบุที่อยู่ไว้ล่วงหน้า nซอง โดยที่ไม่มีจดหมายฉบับใดปรากฏอยู่ในซองจดหมายที่ระบุที่อยู่ถูกต้อง

การนับการเรียงสับเปลี่ยนของเซตเทียบเท่ากับปัญหาการตรวจสอบหมวกซึ่งพิจารณาจำนวนวิธีที่ หมวก nใบ (เรียกว่าh ₁ถึงh _n ) สามารถส่งคืนให้กับ คน nคน ( P ₁ถึงP _n ) โดยที่ไม่มีหมวกใบใดกลับคืนสู่เจ้าของ^{[ 5 ]}

แต่ละคนอาจได้รับหมวกใดก็ได้จากn  − 1 ใบที่ไม่ใช่ของตนเอง เรียกหมวกที่บุคคลP ₁ได้รับว่าh _iและถือว่าh _iเป็นเจ้าของ: P _iได้รับหมวกของP _{1 (} h ₁₎หรือหมวกอื่นๆ ดังนั้น ปัญหาจึงแบ่งออกเป็นสองกรณีที่เป็นไปได้:

1. P _iได้รับหมวกอื่นที่ไม่ใช่h ₁กรณีนี้เทียบเท่ากับการแก้ปัญหาที่มีคน n  − 1 คนและ หมวก n  − 1 ใบ เพราะสำหรับคนn  − 1 คน นอกเหนือจากP ₁แล้ว จะมีหมวกเพียงใบเดียวจากหมวกที่เหลือn  − 1 ใบที่พวกเขาอาจไม่ได้รับ (สำหรับP _j ใดๆ นอกเหนือจากP _iหมวกที่ไม่สามารถรับได้คือh _jในขณะที่สำหรับP _iคือh ₁ ) อีกวิธีหนึ่งที่จะมองเห็นสิ่งนี้คือการเปลี่ยนชื่อh ₁เป็นh _iซึ่งความไม่สอดคล้องกันจะชัดเจนยิ่งขึ้น: สำหรับj ใดๆ ตั้งแต่ 2 ถึงn , P _jไม่สามารถรับh _jได้
2. P _iได้รับh ₁ในกรณีนี้ ปัญหาจะลดลงเหลือn  − 2 คน และn  − 2 หมวก เนื่องจากP ₁ได้รับหมวกของ h i และP i _ได้รับ_หมวกของh ₁ซึ่งทำให้ทั้งสองคนไม่ต้องนำมาพิจารณาต่ออีก

สำหรับหมวกแต่ละใบจากทั้งหมดn  − 1 ใบที่P ₁อาจได้รับ จำนวนวิธีที่P ₂ , ...,  P _nอาจได้รับหมวกทั้งหมดนั้นเท่ากับผลรวมของจำนวนครั้งในสองกรณีนั้น

สิ่งนี้ทำให้เราได้วิธีแก้ปัญหาการตรวจสอบหมวก: กล่าวคือ จำนวนการเรียงสับเปลี่ยนของ เซตที่มีสมาชิก nตัวคือ สำหรับโดยที่และ^{[ 6 ]}${\displaystyle D_{n}}$$${\displaystyle D_{n}=\left(n-1\right){\bigl (}D_{n-1}+D_{n-2}{\bigr )}}$$${\displaystyle n\geq 2}$${\displaystyle D_{0}=1}$${\displaystyle D_{1}=0.}$

จำนวนความผิดปกติที่มีความยาวน้อยแสดงอยู่ในตารางด้านล่าง

จำนวนการเรียงสับเปลี่ยนของ เซตที่มี nองค์ประกอบ (ลำดับA000166ในOEIS ) สำหรับn ขนาดเล็ก

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
${\displaystyle D_{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

นอกจากนี้ ยังมีนิพจน์อื่นๆ อีกหลายแบบสำหรับ ซึ่งเทียบเท่ากับสูตรที่ให้ไว้ข้างต้น ได้แก่ สำหรับ และ ${\displaystyle D_{n}}$$${\displaystyle D_{n}=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$$${\displaystyle n\geq 0}$

${\displaystyle D_{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 D_{n}=\left\lfloor {\frac {n!+1}{e}}\right\rfloor ,\quad \ n\geq 1,}$$$${\displaystyle D_{n}=\left\lfloor \left(e+e^{-1}\right)n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,}$$$${\displaystyle D_{n}=n!-\sum _{i=1}^{n}{n \choose i}\cdot D_{ni},\quad \ n\geq 1.}$$

ความสัมพันธ์เวียนเกิดต่อไปนี้ก็เป็นจริงเช่นกัน: ^{[ 6 ]}$${\displaystyle D_{n}={\begin{cases}1&{\text{ถ้า }}n=0,\\n\cdot D_{n-1}+(-1)^{n}&{\text{ถ้า }}n>0.\end{cases}}}$$

เราสามารถหาได้สูตรที่ไม่ต้องเรียกซ้ำสำหรับจำนวนการเรียงสับเปลี่ยนที่ไม่ตรงกันของ เซต n ตัวได้เช่นกัน เนื่องจากเรากำหนดให้ เป็นเซตของการเรียงสับเปลี่ยนของ วัตถุ nตัวที่ตรึง วัตถุ ตัว ที่ k ไว้ การ ตัดกันของกลุ่มเซตเหล่านี้จำนวน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}(n-i)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!},\end{aligned}}}$$$${\displaystyle D_{n}=n!-\left|S_{1}\cup \dotsm \cup S_{n}\right|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}~.}$$

ในทางกลับกันเนื่องจากเราสามารถเลือกองค์ประกอบให้อยู่ในตำแหน่งของตนเองและสลับองค์ประกอบi อื่นๆ ใน รูปแบบต่างๆ ตามคำจำกัดความ^{[ 8 ]}${\displaystyle n!=\sum _{i=0}^{n}{\binom {n}{i}}D_{i}}$${\displaystyle n-i}$${\displaystyle D_{i}}$

จาก การ แทนค่าจะได้ว่า นี่คือลิมิตของความน่าจะเป็นที่การเรียงสับเปลี่ยนแบบสุ่มของวัตถุจำนวนมากจะเป็นการเรียงสับเปลี่ยนที่ไม่เข้าที่ ความน่าจะเป็นจะลู่เข้าสู่ลิมิตนี้อย่างรวดเร็วมากเมื่อn เพิ่มขึ้น ซึ่งเป็นเหตุผลว่าทำไมจึงเป็นจำนวนเต็มที่ใกล้เคียงที่สุดกับn !/ e กราฟ กึ่งลอการิทึมข้างต้นแสดงให้เห็นว่ากราฟการเรียงสับเปลี่ยนที่ไม่เข้าที่นั้นล้าหลังกราฟการเรียงสับเปลี่ยนด้วยค่าคงที่เกือบเท่าๆ กัน $${\displaystyle D_{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 }{D_{n} \over n!}=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}=e^{-1}\approx 0.367879\ldots .}$$${\displaystyle D_{n}}$

ข้อมูลเพิ่มเติมเกี่ยวกับการคำนวณนี้และขีดจำกัดข้างต้น สามารถดูได้ในบทความเกี่ยวกับ สถิติของการเรียงสับเปลี่ยนแบบสุ่ม

การขยายอนุกรมเชิงอะซิมโทติกสำหรับจำนวนการเรียงสับเปลี่ยนในรูปของจำนวนเบลล์มีดังนี้: โดยที่เป็นจำนวนเต็มบวกคงที่ใดๆ และแทนจำนวนเบลล์ลำดับที่นอกจากนี้ ค่าคงที่ที่บ่งบอกโดย เทอม O ขนาดใหญ่จะไม่เกิน^{[ 9 ]}$${\displaystyle D_{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}}$

ปัญหาการพบปะ (Problème des rencontres)ถามว่ามีลำดับการเรียงสับเปลี่ยนกี่แบบของเซตขนาดn ที่มี จุดตรึงอยู่ k จุด พอดี

การเรียงสับเปลี่ยนที่ไม่เป็นระเบียบเป็นตัวอย่างหนึ่งของสาขาที่กว้างกว่าอย่างการเรียงสับเปลี่ยนแบบมีข้อจำกัด ตัวอย่างเช่นปัญหาเมเนจถามว่า ถ้า มีคู่รักต่างเพศ nคู่ นั่งรอบโต๊ะแบบ ชาย-หญิง-ชาย-หญิง-... จะมีกี่วิธีที่พวกเขาจะนั่งได้โดยที่ไม่มีใครนั่งติดกับคู่ของตนเอง?

กล่าวอย่างเป็นทางการมากขึ้น เมื่อกำหนดเซตAและSและเซตUและVของฟังก์ชันทั่วถึงA → Sเรามักต้องการทราบจำนวนคู่ของฟังก์ชัน ( f ,  g ) โดยที่fอยู่ในUและgอยู่ในVและสำหรับทุกaในA , f ( a ) ≠ g ( a ) กล่าวอีกนัยหนึ่งคือ โดยที่สำหรับแต่ละfและgจะมีการเรียงสับเปลี่ยน φ ของSที่ทำให้f ( a ) = φ( g ( a ))

ข้อสรุปทั่วไปอีกประการหนึ่งคือปัญหาต่อไปนี้:

มีคำที่สลับตัวอักษรได้กี่คำ โดยไม่มีตัวอักษรใด ๆ ที่แน่นอนจากคำที่กำหนดให้?

ตัวอย่างเช่น สำหรับคำที่ประกอบด้วยตัวอักษรที่แตกต่างกันเพียงสองตัว เช่น ตัวอักษร A จำนวน nตัว และ ตัวอักษร B จำนวน mตัว คำตอบก็คือ 1 หรือ 0 ขึ้นอยู่กับว่าn = mหรือไม่ เพราะวิธีเดียวที่จะสร้างแอนาแกรมโดยไม่มีตัวอักษรคงที่คือการสลับA ทั้งหมด กับBซึ่งเป็นไปได้ก็ต่อเมื่อn = m เท่านั้น ในกรณีทั่วไป สำหรับคำที่มีตัวอักษรX _{1 จำนวน}nตัวตัวอักษรX _{2 จำนวน}n _ตัว ..., ตัวอักษรX _r จำนวน nตัว ปรากฏว่า (หลังจากใช้ สูตร การรวม-การแยก อย่างถูกต้อง ) คำตอบจะมีรูปแบบ สำหรับลำดับพหุนามP _n บางลำดับ โดยที่P _nมีดีกรีnแต่คำตอบข้างต้นสำหรับกรณีr = 2 ให้ความสัมพันธ์เชิงตั้งฉาก ซึ่งP _nจะเป็นพหุนาม Laguerre ( โดยขึ้นอยู่กับเครื่องหมายที่สามารถตัดสินใจได้ง่าย) ^{[ 10 ]}$${\displaystyle \int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)\ e^{-x}dx,}$$

โดยเฉพาะอย่างยิ่ง สำหรับการเรียงสับเปลี่ยนแบบคลาสสิก จะได้ว่า โดย ที่คือฟังก์ชันแกมมาไม่สมบูรณ์บน$${\displaystyle D_{n}={\frac {\Gamma (n+1,-1)}{e}}=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx}$$${\displaystyle \Gamma (s,x)}$

การพิจารณาว่ากลุ่มการเรียงสับเปลี่ยน ที่กำหนด (อธิบายโดยชุดการเรียงสับเปลี่ยนที่กำหนดซึ่งสร้างขึ้น) มีการเรียงสับเปลี่ยนที่ผิดปกติหรือไม่นั้นเป็นปัญหา NP-complete ^{[ 11 ] [ 12 ]}

ตารางค่าแฟกทอเรียลและค่าการคลายตัว

${\displaystyle n}$	การเรียงสับเปลี่ยน${\displaystyle n!}$	ความผิดปกติทางจิต${\displaystyle D_{n}}$	${\displaystyle {\frac {D_{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

ลองค้นหาคำว่า "ความวิกลจริต"ในวิกิพีเดีย ซึ่งเป็นพจนานุกรมเสรี

• Baez, John (2003). "Let's get deranged!" (PDF) – via math.ucr.edu.
• Bogart, Kenneth P.; Doyle, Peter G. (1985). "วิธีแก้ปัญหาความสัมพันธ์แบบสามคนโดยไม่แบ่งแยกเพศ" – ผ่านทาง math.dartmouth.edu
• ไวส์สไตน์, EW "ความผิดปกติ" . การวิจัย MathWorld / Wolfram – ผ่าน mathworld.wolfram.com