อ้างอิง:
ข้อความเดิมเขียนโดยคุณ 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 บทหลังๆหน่อย
่