จำนวนวิธีส่งจดหมายผิดซอง

[mark123 ^.^]

มีคน n คนมีจดหมายจ่าหน้าซอง n ซอง จงหาจำนวนวิธีที่
ก.ไม่มีใครได้รับจดหมายที่จ่าหน้าซองถึงตัวเอง
ข. มีคนได้รับตรงชื่อตัวเอง 1 คน
ทำไงอะครับ

[ohmohm]

โจทย์จริงๆ คือ มี n คน แต่ละคนส่งจดหมาย 1 ซอง รวมทั้งหมด n ซอง และทุกคนจะได้รับจดหมาย 1 ซอง ไม่มากกว่านี้ ไม่น้อยกว่านี้ (เป็น crossbar switch) หรือเปล่าครับ

[mark123 ^.^]

อ่อ ใช่เลยครับ แต่ละคนได้จดหมายเพียง 1 ซองเท่านั้น

[gon]

ข้อความเดิมเขียนโดยคุณ mark123 ^.^

มีคน n คนมีจดหมายจ่าหน้าซอง n ซอง จงหาจำนวนวิธีที่
ก.ไม่มีใครได้รับจดหมายที่จ่าหน้าซองถึงตัวเอง
ข. มีคนได้รับตรงชื่อตัวเอง 1 คน
ทำไงอะครับ

แก้ได้หลายวิธีครับ วิธีที่ง่ายที่สุดคือใช้ความสัมพันธ์เวียนเกิด ผมเคยเขียนในบอร์ดหลายรอบแล้ว ว่ามันคือเรื่อง Derangement ซึ่งมีสูตรว่า $$D_n = (n-1)(D_{n-1} + D_{n-2}), D_1 = 0, D_2 = 1$$
การพิสูจน์คือให้เหตุผลเชิงคอมบินาทอริก เช่น ส่งจดหมายผิดซองทั้งสามคน ทำได้ $D_3 = (2)(D_2+D_1)$ วิธี

อีกวิธีที่ชาวโลกเขาใช้อธิบายกัน คือ ใช้หลักการนำเข้าและตัดออก (principle of inclusion and exclusion) เหมือนเรื่องเซตตอน ม.4 เช่น ถ้าเป็นสองเซตเรามี $|A' \cap B'| = |U| - |A| - |B| + |A \cap B|$

ถ้าเป็น $n$ เซต คือ $|A'_1 \cap A'_2 \cap A'_3 ... \cap A'_n| = |U| - \Sigma |A_i| + \Sigma |A_i \cap A_j| - ... $ โดยที่ $i \ne j \ne k ...$

$= n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - ... + (-1)^k\binom{n}{k}(n-k)!$

จากนั้นเขาจะถึง $n!$ ออกมาได้เป็น $= n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + (-1)^k\frac{1}{k!}) $

เช่น $D_3 = 3!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!})$

1. ตอบ $D_n = (n-1)(D_{n-1} + D_{n-2}), D_1 = 0, D_2 = 1$

หรือ $D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + (-1)^k\frac{1}{k!})$

2. ตอบ $\binom{n}{1}D_{n-1}$

ลองอ่านในเล่มนี้เพิ่มเติมครับ http://e-book.ram.edu/e-book/inside/...asp?code=CO223 บทหลังๆหน่อย

่