|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
จำนวนวิธีส่งจดหมายผิดซอง
มีคน n คนมีจดหมายจ่าหน้าซอง n ซอง จงหาจำนวนวิธีที่
ก.ไม่มีใครได้รับจดหมายที่จ่าหน้าซองถึงตัวเอง ข. มีคนได้รับตรงชื่อตัวเอง 1 คน ทำไงอะครับ |
#2
|
|||
|
|||
โจทย์จริงๆ คือ มี n คน แต่ละคนส่งจดหมาย 1 ซอง รวมทั้งหมด n ซอง และทุกคนจะได้รับจดหมาย 1 ซอง ไม่มากกว่านี้ ไม่น้อยกว่านี้ (เป็น crossbar switch) หรือเปล่าครับ
|
#3
|
|||
|
|||
อ่อ ใช่เลยครับ แต่ละคนได้จดหมายเพียง 1 ซองเท่านั้น
|
#4
|
||||
|
||||
อ้างอิง:
การพิสูจน์คือให้เหตุผลเชิงคอมบินาทอริก เช่น ส่งจดหมายผิดซองทั้งสามคน ทำได้ $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 บทหลังๆหน่อย ่ |
|
|