|
|
#1
10 กุมภาพันธ์ 2008, 01:05
|
||||
|
||||
จดหมายผิดซอง
จดหมายผิดซอง
ปัญหาจดหมายผิดซอง หรือที่รู้จักกันในชื่อว่า Derangement เป็นปัญหาเก่าแก่ที่แก้ได้โดย Niclaus Bernoulli และ Euler (ต่างคนต่างแก้) ปัญหามีอยู่ว่า มีจดหมาย $n$ ฉบับ กับซองจดหมาย $n$ ซอง ที่เขียนจ่าหน้าตามที่อยู่ของจดหมายแต่ละฉบับ จงหาจำนวนวิธีทั้งหมดในการ ใส่จดหมายลงในซองจดหมาย โดยที่ไม่มีจดหมายฉบับใดเลยใส่ถูกต้องตรงตามซองจดหมายของมัน หรือพูดให้ง่ายก็คือ จงหาจำนวนวิธีทั้งหมด ในการใส่จดหมายทุกฉบับผิดซอง  กำหนดให้ $f(n) =$ จำนวนวิธีใส่จดหมาย $n$ ฉบับ ในซองจดหมาย $n$ ซอง โดยใส่ผิดซองทั้งหมด จะได้ว่า $\begin{array}{rcl} f(1) & = & 0 \\ f(2) & = & 1 \\ f(3) & = & 2 \end{array} $ เราจะมีวิธีหา $f(n)$ ออกมาได้อย่างไร  สำหรับผู้ที่ไม่ถนัดเรื่องการเรียงสับเปลี่ยน ปัญหาแบบนี้ เรามักจะแก้โดยใช้ความสัมพันธ์เวียนบังเกิด พิจารณาสิ่งที่จะทำโดยอ้างจากความสำเร็จของงานก่อนหน้านี้ เอ๊ะยังไง  หากเรารู้ค่าของ $f(1) , f(2) , \ldots , f(n-1)$ ถามว่าข้อมูลนี้ช่วยเราคำนวณหา $f(n)$ ได้หรือไม่ ลองพิจารณาตามนะครับ สมมติว่ามีจดหมาย $n-1$ ฉบับ และซองจดหมาย $n-1$ ซอง เรารู้แล้วว่าจำนวนวิธีใส่จดหมายผิดซองทั้งหมดคือ $f(n-1)$ วิธี จากนั้นเราไปเขียนจดหมายมา 1 ฉบับ และเขียนซองจดหมายที่จ่าหน้าซองตามจดหมายฉบับนี้อีก 1 ซอง เราจะมีวิธีนำจดหมายและซองใหม่นี้ ไปใส่ผิดซองกับกองจดหมายและซองจดหมายก่อนหน้านี้ได้อย่างไร เพื่อให้อธิบายได้เข้าใจยิ่งขึ้น จึงขอกำหนดสัญลักษณ์ดังต่อไปนี้ $a_1 , a_2 , a_3 , \ldots , a_n$ แทนจดหมายฉบับที่ 1 ถึง n $A_1 , A_2 , A_3 , \ldots , A_n$ แทนซองจดหมายซองที่ 1 ถึง n เราจะพบว่ามีวิธีทำให้ จดหมาย $a_n$ กับซองจดหมาย $A_n$ ไม่ถูกใส่ในซองเดียวกันได้ 2 แบบคือ
เรามีวิธีหา $f(n)$ ในรูปอื่นที่ไม่ใช่ความสัมพันธ์เวียนบังเกิดได้หรือไม่  เราลองจัดรูปมันใหม่ดังนี้$f(n) - n f(n-1) = - (f(n-1) - (n-1) f(n-2))$ และแทนค่า $n$ ตั้งแต่ $3$ ถึง $n$ จะได้ $\begin{array}{rcl} f(3) - 3 f(2) & = & - (f(2) - 2 f(1)) \\ f(4) - 4 f(3) & = & - (f(3) - 3 f(2)) \\ f(5) - 5 f(4) & = & - (f(4) - 4 f(3)) \\ \cdots \cdots \cdots \cdots & \cdots & \cdots \cdots \cdots \cdots \cdots \cdots \\ f(n) - n f(n-1) & = & - (f(n-1) - (n-1) f(n-2))\end{array}$ จับสมการ $n-2$ สมการ นำมาคูณกันทั้งหมดจะได้ $f(n) - n f(n-1) = (-1)^{n-2} (f(2) - 2 f(1)) = (-1)^n$ จะเห็นว่าเทอมที่เป็น $f(n-2)$ หายไปแล้ว เหลือเพียงเทอม $f(n-1)$ ซึ่งเรากำจัดได้ดังนี้ จัดรูปใหม่โดยหารตลอดด้วย $n!$ จะได้ $\frac{f(n)}{n!} - \frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}$ และแทนค่า $n$ ตั้งแต่ $2$ ถึง $n$ จะได้ $\begin{array}{rcl} \frac{f(2)}{2!} - \frac{f(1)}{1!} & = & \frac{1}{2!} \\ \frac{f(3)}{3!} - \frac{f(2)}{2!} & = & - \frac{1}{3!} \\ \frac{f(4)}{4!} - \frac{f(3)}{3!} & = & \frac{1}{4!} \\ \cdots \cdots \cdots \cdots & \cdots & \cdots \cdots \\ \frac{f(n)}{n!} - \frac{f(n-1)}{(n-1)!} & = & \frac{(-1)^n}{n!}\end{array}$ จับสมการ $n-1$ สมการ นำมาบวกกันทั้งหมดจะได้ $\displaystyle{f(n) = n! \left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \cdots + \frac{(-1)^n}{n!}\right) = n! \sum_{k = 2}^{n} \frac{(-1)^k}{k!} = n! \sum_{k = 0}^{n} \frac{(-1)^k}{k!}}$ เป็นอันว่าเราได้สูตรสำเร็จเรียบร้อยแล้ว  แต่ถ้าเราลองดัดแปลงสูตรสุดท้ายอีกหน่อยละโดยการคูณเทอมใน $\Sigma$ ด้วย $\frac{(n-k)!}{(n-k)!}$ และกระจาย $n!$ เข้าไปข้างใน จะได้ $\displaystyle{f(n) = \sum_{k = 0}^{n} \frac{(-1)^k n! (n-k)!}{k! (n-k)!} = \sum_{k = 0}^{n} (-1)^k \binom{n}{k} (n-k)! }$ มองเห็นรูปแบบของสามเหลี่ยมปาสคาล ในสูตรนี้ไหมครับ  สมมติว่าเราต้องการหาค่า $f(4)$ ก็ให้เราเขียนแถว $(-1)^k \binom{4}{k}$ ต่างๆออกมาจะได้ $\begin{array}{ccccc}1 & -4 & 6 & -4 & 1\end{array}$ จากนั้นคูณแต่ละเทอมด้วย $4! , 3! , 2! , 1! , 0!$ ตามลำดับและนำมารวมกัน ก็จะได้ $4! - 4 (3!) + 6 (2!) - 4 (1!) + 0! = 9 = f(4)$ วิธีแก้ปัญหาแบบเรียงสับเปลี่ยน นอกจากนี้แล้ว หากเราวิเคราะห์ความหมายของ $\binom{n}{k} (n-k)!$ จะพบว่ามันคือ จำนวนวิธีการเลือกของ $k$ สิ่ง จากของทั้งหมด $n$ สิ่ง โดยของที่เหลือ $n-k$ สิ่ง วางเรียงกันเป็นเส้นตรง เมื่อแปลให้มีความหมายสอดคล้องกับปัญหาจดหมายผิดซอง ก็จะเป็น จำนวนวิธีใส่จดหมาย $k$ ฉบับให้ถูกซอง โดยจดหมาย $n-k$ ฉบับที่เหลือ จะใส่ยังไงก็ได้ หากใครจินตนาการไม่ออก ลองสมมติว่า เราวางซองจดหมาย $A_1 , A_2 , A_3 , \dots , A_n$ เรียงตามลำดับเป็นเส้นตรง และเราจะไม่เปลี่ยนตำแหน่งของซองจดหมาย จากนั้นจึงเลือกจดหมาย $k$ ฉบับ มาใส่ให้ถูกซองของมัน ($\binom{n}{k}$ วิธี) สุดท้ายจดหมายที่เหลืออยู่ จะใส่ซองไหนก็ได้ ($(n-k)!$ วิธี) ยังเหลืออีกเทอมในสูตรที่เป็น $(-1)^k$ ซึ่งให้ผลเป็นบวกเข้า หักออก บวกเข้า หักออก ... รูปแบบนี้คุ้นกันไหมครับ มันช่างเหมือนกับ หลักการรวมเข้าและหักออก และเมื่อเราจินตนาการต่อไป ก็จะรู้แล้วละว่าหลักการรวมเข้าและหักออก ช่วยแก้ปัญหาข้อนี้ได้อย่างไร กำหนดให้ $c_i$ คือ ใส่จดหมาย $a_i$ ถูกซอง $M(k,n) = $ จำนวนวิธีใส่จดหมาย $k$ ฉบับให้ถูกซอง โดยจดหมาย $n-k$ ฉบับที่เหลือ จะใส่ยังไงก็ได้ จากหลักการรวมเข้าและหักออก จะได้ $\begin{array}{rcl} N(\bar c_1 \bar c_2 \cdots \bar c_n) & = & \displaystyle{N - \sum_{i = 1}^{n} N(c_i) + \sum_{\substack{i,j= 1 \\ i \not= j}}^{n} N(c_i c_j) - \sum_{\substack{i,j,k= 1 \\ i \not= j \not= k}}^{n} N(c_i c_j c_k) + \cdots + (-1)^n N(c_1 c_2 \dots c_n) }\\ & = & n! - M(1,n) + M(2,n) - M(3,n) + \cdots + (-1)^n M(n,n) \\ & = & \displaystyle{n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^n \binom{n}{n}(n-n)!} \\ & = & \displaystyle{\sum_{k = 0}^{n} (-1)^k \binom{n}{k} (n-k)!} \\ & = & \displaystyle{n! \sum_{k = 0}^{n} \frac{(-1)^k}{k!}} \end{array}$ เย่ !!! ในที่สุดเราก็ได้วิธีแก้ปัญหาข้อนี้อีกวิธีหนึ่งหมายเหตุ: ปัญหานี้เทียบเท่ากับ จงหาจำนวนวิธีเรียงลำดับของ $n$ สิ่ง โดยไม่มีของชิ้นใดกลับมาอยู่ตำแหน่งเดิม
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 
|
  |
|
|
