จดหมายผิดซอง

มีจดหมาย n ฉบับ กับซองจดหมาย n ซอง ที่เขียนจ่าหน้าตามที่อยู่ของจดหมายแต่ละฉบับ จงหาจำนวนวิธีทั้งหมดในการ ใส่จดหมายลงในซองจดหมาย โดยที่ไม่มีจดหมายฉบับใดเลยใส่ถูกต้องตรงตามซองจดหมายของมัน หรือพูดให้ง่ายก็คือ จงหาจำนวนวิธีทั้งหมด ในการใส่จดหมายทุกฉบับผิดซอง 
กำหนดให้ f(n)= จำนวนวิธีใส่จดหมาย n ฉบับ ในซองจดหมาย n ซอง โดยใส่ผิดซองทั้งหมด
จะได้ว่า
f(1) f(2) f(3) = = = 0 1 2  
เราจะมีวิธีหา f(n) ออกมาได้อย่างไร 
สำหรับผู้ที่ไม่ถนัดเรื่องการเรียงสับเปลี่ยน ปัญหาแบบนี้ เรามักจะแก้โดยใช้ความสัมพันธ์เวียนบังเกิด พิจารณาสิ่งที่จะทำโดยอ้างจากความสำเร็จของงานก่อนหน้านี้ เอ๊ะยังไง 
หากเรารู้ค่าของ f(1),f(2),...,f(n−1)  ถามว่าข้อมูลนี้ช่วยเราคำนวณหา f(n) ได้หรือไม่ ลองพิจารณาตามนะครับ
สมมติว่ามีจดหมาย n−1  ฉบับ และซองจดหมาย n−1  ซอง เรารู้แล้วว่าจำนวนวิธีใส่จดหมายผิดซองทั้งหมดคือ f(n−1)  วิธี
จากนั้นเราไปเขียนจดหมายมา 1 ฉบับ และเขียนซองจดหมายที่จ่าหน้าซองตามจดหมายฉบับนี้อีก 1 ซอง
เราจะมีวิธีนำจดหมายและซองใหม่นี้ ไปใส่ผิดซองกับกองจดหมายและซองจดหมายก่อนหน้านี้ได้อย่างไร 
เพื่อให้อธิบายได้เข้าใจยิ่งขึ้น จึงขอกำหนดสัญลักษณ์ดังต่อไปนี้
a1,a2,a3,...,an แทนจดหมายฉบับที่ 1 ถึง n
A1,A2,A3,...,An แทนซองจดหมายซองที่ 1 ถึง n
เราจะพบว่ามีวิธีทำให้ จดหมาย an กับซองจดหมาย An ไม่ถูกใส่ในซองเดียวกันได้ 2 แบบคือ

1. นำจดหมาย ai  มาใส่ในซองจดหมาย An และนำจดหมาย an ใส่ในซองจดหมาย Ai  (i<n)
   จดหมายและซองจดหมายที่เหลืออยู่ n−2  คู่ มีจำนวนวิธีใส่ผิดซองทั้งหมด f(n−2)  วิธี และเนื่องจากมีวิธีเลือก i ทั้งสิ้น n−1  วิธี ดังนั้นจำนวนวิธีทั้งหมดในกรณีนี้จึงเป็น (n−1)f(n−2)  วิธี
2. นำจดหมาย ai  มาใส่ในซองจดหมาย An แต่ไม่นำจดหมาย an ไปใส่ในซองจดหมาย Ai  (i<n)
   เนื่องจากในกรณีนี้เราบังคับไว้แล้วว่า จะไม่ใส่จดหมาย an ลงในซองจดหมาย Ai  จึงมองอีกแบบได้ว่า Ai  เป็นซองจดหมายที่จ่าหน้าตามที่อยู่ของ an นั่นเอง จดหมายและซองจดหมายที่เหลืออยู่ n−1  คู่ จึงมีจำนวนวิธีใส่ผิดซองทั้งหมด f(n−1)  วิธี และเนื่องจากมีวิธีเลือก i ทั้งสิ้น n−1 วิธี ดังนั้นจำนวนวิธีทั้งหมดในกรณีนี้จึงเป็น (n−1)f(n−1)  วิธี

ดังนั้นจะได้ f(n)=(n−1)(f(n−1)+f(n−2))  วิธี
เรามีวิธีหา f(n) ในรูปอื่นที่ไม่ใช่ความสัมพันธ์เวียนบังเกิดได้หรือไม่ เราลองจัดรูปมันใหม่ดังนี้
f(n)−nf(n−1)=−(f(n−1)−(n−1)f(n−2)) 
และแทนค่า n ตั้งแต่ 3 ถึง n จะได้
f(3)−3f(2) f(4)−4f(3) f(5)−5f(4) ············ f(n)−nf(n−1) = = = ··· = −(f(2)−2f(1)) −(f(3)−3f(2)) −(f(4)−4f(3)) ·················· −(f(n−1)−(n−1)f(n−2))  
จับสมการ n−2  สมการ นำมาคูณกันทั้งหมดจะได้
f(n)−nf(n−1)=(−1)n−2(f(2)−2f(1))=(−1)n 
จะเห็นว่าเทอมที่เป็น f(n−2)  หายไปแล้ว เหลือเพียงเทอม f(n−1)  ซึ่งเรากำจัดได้ดังนี้
จัดรูปใหม่โดยหารตลอดด้วย n! จะได้ n!f(n)−(n−1)!f(n−1)=n!(−1)n 
และแทนค่า n ตั้งแต่ 2 ถึง n จะได้
2!f(2)−1!f(1) 3!f(3)−2!f(2) 4!f(4)−3!f(3) ············ n!f(n)−(n−1)!f(n−1) = = = ··· = 12! −13! 14! ······ n!(−1)n  
จับสมการ n−1  สมการ นำมาบวกกันทั้งหมดจะได้
f(n)=n!(12!−13!+14!−15!+···+n!(−1)n)=n!∑nk=2k!(−1)k=n!∑nk=0k!(−1)k 
เป็นอันว่าเราได้สูตรสำเร็จเรียบร้อยแล้ว แต่ถ้าเราลองดัดแปลงสูตรสุดท้ายอีกหน่อยละ
โดยการคูณเทอมใน Σ  ด้วย (n−k)!(n−k)! และกระจาย n! เข้าไปข้างใน จะได้
f(n)=∑nk=0k!(n−k)!(−1)kn!(n−k)!=∑nk=0(−1)k(kn)(n−k)! 
มองเห็นรูปแบบของสามเหลี่ยมปาสคาล ในสูตรนี้ไหมครับ 
สมมติว่าเราต้องการหาค่า f(4) ก็ให้เราเขียนแถว (−1)k(k4)  ต่างๆออกมาจะได้
1 −4 6 −4 1  
จากนั้นคูณแต่ละเทอมด้วย 4!,3!,2!,1!,0! ตามลำดับและนำมารวมกัน ก็จะได้
4!−4(3!)+6(2!)−4(1!)+0!=9=f(4) 
วิธีแก้ปัญหาแบบเรียงสับเปลี่ยน
นอกจากนี้แล้ว หากเราวิเคราะห์ความหมายของ (kn)(n−k)!  จะพบว่ามันคือ
จำนวนวิธีการเลือกของ k สิ่ง จากของทั้งหมด n สิ่ง โดยของที่เหลือ n−k  สิ่ง วางเรียงกันเป็นเส้นตรง
เมื่อแปลให้มีความหมายสอดคล้องกับปัญหาจดหมายผิดซอง ก็จะเป็น
จำนวนวิธีใส่จดหมาย k ฉบับให้ถูกซอง โดยจดหมาย n−k  ฉบับที่เหลือ จะใส่ยังไงก็ได้
หากใครจินตนาการไม่ออก ลองสมมติว่า เราวางซองจดหมาย A1,A2,A3,...,An เรียงตามลำดับเป็นเส้นตรง และเราจะไม่เปลี่ยนตำแหน่งของซองจดหมาย จากนั้นจึงเลือกจดหมาย k ฉบับ มาใส่ให้ถูกซองของมัน ((kn) วิธี) สุดท้ายจดหมายที่เหลืออยู่ จะใส่ซองไหนก็ได้ ((n−k)!  วิธี)
ยังเหลืออีกเทอมในสูตรที่เป็น (−1)k  ซึ่งให้ผลเป็นบวกเข้า หักออก บวกเข้า หักออก ... รูปแบบนี้คุ้นกันไหมครับ มันช่างเหมือนกับ หลักการรวมเข้าและหักออก และเมื่อเราจินตนาการต่อไป ก็จะรู้แล้วละว่าหลักการรวมเข้าและหักออก ช่วยแก้ปัญหาข้อนี้ได้อย่างไร 
กำหนดให้
ci คือ ใส่จดหมาย ai  ถูกซอง
M(k,n)= จำนวนวิธีใส่จดหมาย k ฉบับให้ถูกซอง โดยจดหมาย n−k  ฉบับที่เหลือ จะใส่ยังไงก็ได้
จากหลักการรวมเข้าและหักออก จะได้
N(c1ˉc2ˉ···cnˉ) = = = = = N−∑ni=1N(ci)+∑ni,j=1 i/=j  N(cicj)−∑ni,j,k=1 i/=j/=k  N(cicjck)+···+(−1)nN(c1c2...cn) n!−M(1,n)+M(2,n)−M(3,n)+···+(−1)nM(n,n) n!−(1n)(n−1)!+(2n)(n−2)!−(3n)(n−3)!+···+(−1)n(nn)(n−n)! ∑nk=0(−1)k(kn)(n−k)! n!∑nk=0k!(−1)k  
เย่ !!! ในที่สุดเราก็ได้วิธีแก้ปัญหาข้อนี้อีกวิธีหนึ่ง
หมายเหตุ: ปัญหานี้เทียบเท่ากับ จงหาจำนวนวิธีเรียงลำดับของ n สิ่ง โดยไม่มีของชิ้นใดกลับมาอยู่ตำแหน่งเดิม

 
ที่มา : https://www.sahavicha.com/?name=knowledge&file=readknowledge&id=624