สมมติว่าคุณมีนิยายอยู่เรื่องหนึ่งที่มีความยาวทั้งสิ้น $n$ เล่มจบ แล้วคุณเกิดอยากลองสลับการวางแต่ละเล่มโดยที่ไม่มีเล่มใดอยู่แหน่งเดิมเลย (เช่น เล่ม 1 ไม่อยู่ตำแหน่งที่ 1, เล่ม 2 ก็ไม่อยู่ในตำแหน่งที่ 2 รวมถึงเล่มอื่นๆทุกเล่ม) ถามว่าคุณสามารถเรียงนิยายของคุณได้กี่วิธี?

นี่คือตัวอย่างหนึ่งของการเรียงสับเปลี่ยนแบบที่เรียกว่า Derangement ซึ่งหมายถึงการเรียงสับเปลี่ยนที่ไม่มีของชิ้นใดวางอยู่ในตำแหน่งเดิมเลย เช่นมีลำดับ $\{1,2,3,4\}$ ถ้าเรียงใหม่ให้เป็น $\{4,3,2,1\}, \{2,1,4,3\}, \{3,1,4,2\}$ จะถือว่าเป็น Derangement เพราะไม่มีตัวใดวางอยู่ในตำแหน่งเดิม แต่ $\{1,3,2,4\}, \{1,4,3,2\}$ ไม่ถือว่าเป็น Derangement เพราะมี 1 ที่ยังอยู่ในตำแหน่งเดิม

เรามักจะใช้สัญลักษณ์ $!n$ หรือ $D_n$ แทนจำนวนวิธี Derangement สำหรับของ $n$ ชิ้น

สำหรับวิธีในการหา Derangement นั้นมีหลายวิธี วิธีหนึ่งคือใช้ Recurence relation ดังนี้

$$D_n = (n-1) \times (D_{n-1} + D_{n-2})$$

โดยที่ $D_0 = 1$ และ $D_1 = 0$ (หมายถึงว่าถ้ามีของแค่ชิ้นเดียวจะไม่มีวิธีวางให้ไม่อยู่ในตำแหน่งเดิมเลย จึงมีวิธีเท่ากับ 0)

ที่มาคือของชิ้นแรกสามารถเปลี่ยนที่ได้ทั้งหมด $n-1$ แบบ หรือก็คือวางตรงไหนก็ได้ที่ไม่ใช่ที่เดิม ดังนั้นในสมการก็ควรจะเป็น $(n-1) \times {อะไรซักอย่าง}$ จากนั้นให้มองว่าของชิ้นแรกถูกนำไปวางที่ตำแหน่ง $k$ ดังนั้นของที่อยู่ตกแหน่ง $k$ เดิมจะต้องเปลี่ยนตำแหน่ง ซึ่งมี 2 กรณี คือ 

1. นำของชิ้นที่ $k$ มาวางไว้ที่ตำแหน่งแรก แทนของชิ้นแรกที่เอาไปไว้ในตำแหน่ง $k$ จะได้ว่าเหลือของอีก $n-2$ ชิ้น ที่ต้องนำมาสลับที
2. นำของชิ้นที่ $k$ ไปวางไว้ที่ใดก็ได้ที่ไม่ใช่ตำแหน่งแรก ให้มองว่า $k$ อยู่ตำแหน่งแรกและต้องวางใหม่ไม่ให้อยู่จุดนั้น พร้อมๆกับของชิ้นอื่นด้วย ดังนั้นในกรณีนี้จะต้องหาวิธีวางของของ $n-1$ ชิ้น

เมื่อมารวมกันทั้งหมดก็จะได้ $D_n = (n-1) \times (D_{n-1} + D_{n-2})$ และเขียนออกมาเป็นโปรแกรมโดยใช้ Recursive function ได้ดังนี้

C++

int de(int n) {
    if (n == 0)  return 1;
    if (n == 1)  return 0;
    return (n-1) * (de(n-1) + de(n-2));
}

Python

def de(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    return (n-1) * (de(n-1) + de(n-2))

วิธีนี้อาจจะทำงานได้ช้าเนื่องจากมีการคำนวนที่ซ้ำซ้อนกันเกิดขึ้นจำนวนมาก (เช่นเดียวกับการหาลำดับ Fibonacci ด้วย Recursive function) ซึ่งสามารถแก้ได้โดยใช้ Dynamic Programming ดังนี้

C++

int de(int n) {
    int d[n+1];
    d[0] = 1, d[1] = 0;
    for (int i = 2; i <= n; ++i)
        d[i] = (i-1) * (d[i-1] + d[i-2]);
    return d[n];
}

Python

def de(n):
    d = [0] * (n-1)
    d[0] = 1
    d[1] = 0
    for i in range(2,n+1):
        d[i] = (i-1) * (d[i-1] + d[i-2])
    return d[n]

ด้วยโปรแกรมหลังนี้จะทำให้สามารถหาจำนวนของการ Derangement ของ n ได้ในเวลา $O(n)$

นอกจากนี้ยังสามารถหาจำนวน Derangement ได้จากหลักการเพิ่มเข้าและตัดออก (Inclusion-Exclusion Principle) ดังนี้ (อ้างอิงจากที่นี่)

เริ่มต้นจากหารูปแบบทั่วไปผ่านกรณีที่ $n = 4$ ซึ่งก็คือการสลับตำแหน่งของ $\{1,2,3,4\}$ ที่ไม่มีตัวใดอยู่ตำแหน่งเดิมเลย

จำนวนวิธีในการจัดเรียงที่เป็นไปได้ทั้งหมดคือ $4!$

กำหนดให้ $X(1)$ แทนวิธีการจัดเรียงที่ 1 อยู่ในตำแหน่งเดิม เช่น $\{1,3,4,2\}, \{1,4,3,2\}, \{1,2,4,3\}$ เป็นต้น ดังนั้นจำนวนวิธีทั้งหมดในการเรียงที่มี 1 ตำแหน่งเดิม หรือ $|X(1)|$ ก็คือ $3!$ เพราะ 1 อยู่ที่เดิม และสลับอีก 3 ตัวที่เหลือ

เช่นเดียวกันกับตำแหน่งอื่นๆ จำนวนวิธีในการวางให้มีตัวใดตัวหนึ่งอยู่ตำแหน่งเดิมจะเท่ากัน ไม่ว่าจะเป็นตัวไหน ดังนั้นจะได้ว่า $|X(1)| = |X(2)| = |X(3)| = |X(4)|$

กำหนดให้ $|X(1) \wedge X(2)|$ แทนจำนวนวิธีจัดเรียงที่ 1 และ 2 อยู่ในตำแหน่งเดิม จะพบว่าจำนวนวิธีคือจัดเรียง 2 ตัวที่เหลือ ดังนั้น $|X(1) \wedge X(2)| = 2!$

สำหรับการวางให้มี 2 ตัวอยู่ในตำแหน่งเดิม นอกจากการ fix ตำแหน่งของ 1,2 แล้ว ก็จะมีคู่จำนวนที่เหลืออีกทั้งหมด $C(4,2)$ (4 เลือก 2) แบบ ดังนั้นจำนวนการจัดเรียงที่มีอย่างน้อย 2 ตัวอยู่ตำแหน่งเดิมจะเท่ากับ $C(4,2) \times 2!$

สำหรับ 3 ตัว เช่น $|X(1) \wedge X(2) \wedge X(3)|$ ก็จะมีวิธีการวางทั้งหมด $C(4,3) \times 1!$ และสำหรับ 4 ตัว (ทั้งหมด) ก็จะเป็น $C(4,4) \times 0!$

ที่นี้เราจะหาจำนวนของ $D_4$ (จำนวนการจัดเรียงที่ทั้ง 4 ตัวไม่อยู่ในตำแหน่งเดิม) ด้วยหลักการเพิ่มเข้าและตัดออก ก็จะได้เป็น

$D_4 = C(4,0)(4!) - C(4,1)(3!) + C(4,2)(2!) - C(4,3)(1!) + C(4,4)(0!)$

$= \frac{4!}{0!4!}(4!) - \frac{4!}{1!3!}(3!) + \frac{4!}{2!2!}(2!) - \frac{4!}{3!1!}(1!) + \frac{4!}{4!0!}(0!)$

$= \frac{4!}{0!} - \frac{4!}{1!} + \frac{4!}{2!} - \frac{4!}{3!} + \frac{4!}{4!}$

$= 4! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!})$

เมื่อเขียนในรูปทั่วไป ก็จะเป็น

$$D_n = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + (-1)^n \frac{1}{n!})$$

หรือ

$$D_n = n! \sum\limits_{i=0}^n \frac{(-1)^i}{i!}$$

References:

http://oeis.org/wiki/Number_of_derangements

http://www.geeksforgeeks.org/count-derangements-permutation-such-that-no...

A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory (Miklos Bona)

http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html