Knowledge "ย้ายที่ทั้งหมดได้กี่วิธี" คำถามนี้สั้นแต่มันไม่หมู

วันนี้เป็นหวัด เลยต้องนอนตั้งแต่เที่ยง
ตื่นขึ้นมาเขียนบทความนี้อย่างเฉื่อยชา
กว่าจะได้โพสต์ก็ดึกซะโน่น...
ก็หวังว่าจะอ่านได้มันส์อยู่นะครับ
(สำนวนมันคงไม่เป็นหวัดด้วยหรอกนะ)

โจทย์ข้อนี้อาจมีที่มาแปลกไปซักหน่อย
เพราะมันเกิดจากการสังเกตเกมที่เล่น
(ซึ่งคนส่วนใหญ่ไม่ได้คิดถึงจุดนี้เลย)
(และข้อสอบก็ไม่ค่อยออกแนวนี้ด้วย)

แต่สำหรับผมแล้ว มันธรรมดามาก
เพราะความรู้นั้น มีอยู่ในทุกสิ่งครับ

โดยผมสังเกตได้จากเกม O2Jam
แล้วก็เกิดคำถามว่า เวลาใส่แหวนเนี่ย
มันสลับโน้ตที่ตกลงมาได้กี่แบบ?

อธิบายเกี่ยวกับตัวเกมซักหน่อย
O2Jam เป็นเกมเพลงที่ใช้นิ้วกดโน้ต
(คล้ายเกมเต้น แต่เปลี่ยนมาใช้นิ้วแทน)
โดย O2Jam มีปุ่มให้กดมากถึง 7 ปุ่ม
(น่าจะเป็นเกมเพลงที่มีปุ่มกดมากที่สุด)

แต่สำหรับพวกเทพแล้ว นี่คงน้อยไป
ก็เลยมีระบบแหวนความสามารถขึ้นมา
เมื่อใส่แหวนแล้ว ตัวโน้ตจะเปลี่ยนไป
เช่น มองไม่เห็นโน้ต, เรียงโน้ตใหม่,
โน้ตอยู่ในกระจก เป็นต้น

ในที่นี้ เราจะสนใจการเรียงโน้ตใหม่
ซึ่งเท่าที่ผมสังเกตมา (อาจสังเกตผิด)
พบว่าโน้ตจะมีการเปลี่ยนที่ตกทุกโน้ต
(ไม่อยู่ในตำแหน่งที่ยังไม่ใส่แหวนเลย)

ทวนโจทย์นะครับ
เวลาใส่แหวน โน้ตจะสลับได้กี่แบบ?
(มี 7 ที่ให้ลง และต้องลงไม่ซ้ำที่เดิม)

ตอนแรก เห็นโจทย์สั้นๆ ก็คิดว่าหมู
เลยตั้งสมการความน่าจะเป็น (พื้นฐาน)
แต่พอดูแซมเปิลเสปส ก็พบว่าผิดไกล

เลยลองดัดแปลงสมการนั้นนิดหน่อย
ใช้เวลาคิดนานมาก แต่ก็แก้ปัญหาไม่ได้
เลยหนีไปฟังเพลงพักสมองหน่อยนึง

เมื่อวิธีที่ผ่านมาล้มเหลว ก็ใช้วิธีพื้นฐาน
คือทดลองหาค่า โดยเริ่มตั่งแต่ 1 ช่อง
ได้ค่าดังนี้

ช่องโน้ต	สลับได้	หมายเหตุ
1	0	มีที่เดียว จึงย้ายที่ไม่ได้เลย
2	1	ย้ายที่ได้แค่วิธีเดียว
3	2
4	9
5	44	เหนื่อยมาก กว่าจะกระจายหมด
6	256	ข้อนี้ใช้สมการทำนายครับ

โห... มันขึ้นเร็วกว่าที่คิดแฮะ
แต่ตอนกระจาย ก็พบรูปแบบตายตัว
เลยกำหนดสมการออกมาได้ดังนี้

q_n = (n-1)(q_n-1+q_n-2)

โดย
n เป็นจำนวนเต็ม โดย n≥3
q_n คือ วิธีการที่สลับได้เมื่อมี n ช่อง
ที่ให้ n≥3 เพราะไม่อยากนิยาม q₀, q_-1
(จะปรากฎเมื่อหา q₁, q₂ จากสมการ)
และกำหนดให้ q₁ = 0 และ q₂ = 1

อธิบายที่มาของสมการ
โดยใช้ตัวอย่างกรณี 5 ช่องนะครับ

ต้นแบบคือ
1 | 2 | 3 | 4 | 5
เมื่อย้าย 1 ไปไว้ที่ 2 และ 2 ไปไว้ที่ 1
2 | 1 | 5 | 3 | 4
2 | 1 | 4 | 5 | 3
เมื่อย้าย 1 ไปไว้ที่ 2 และ 2 ไปไว้ที่อื่น
5 | 1 | 2 | 3 | 4
4 | 1 | 2 | 5 | 3
3 | 1 | 2 | 5 | 4
3 | 1 | 5 | 2 | 4
5 | 1 | 4 | 2 | 3
4 | 1 | 5 | 2 | 3
3 | 1 | 4 | 5 | 2
4 | 1 | 5 | 3 | 2
5 | 1 | 4 | 3 | 2
เมื่อย้าย 1 ไปไว้ที่ตำแหน่งอื่นที่เหลือ
ก็ทำในทำนองเดียวกันกับข้างบน

สรุปคือ
ขั้นตอนแรก สลับ 1 กับ 2
จะทำได้ 2 วิธี ซึ่งเหมือนกับ q₃
ขั้นตอนที่สอง เอา 2 ไว้ที่อื่น
จะทำได้ 3 วิธี ซึ่งเหมือนกับ q₄
ขั้นตอนสุดท้าย เอา 4 คูณ q₄+q₃
จึงได้ว่า q₅ = 4(q₄+q₃) = 44 วิธี

ถึงตรงนี้ก็ตอบโจทย์ได้แล้ว
q₇ = 6(q₆+q₅) = 1854

...จบเลยดีมั้ย...

ยังๆๆ
เราต้องไม่พอใจอะไรง่ายๆ สิครับ
เพราะมันเป็นความสัมพันธ์เวียนเกิด
ซึ่งมันใช้ยากหน่อย เช่น จะหา q₁₀₀₀
ก็ต้องหา q₉₉₉, q₉₉₈, q₉₉₇, ...
โครตจะยุ่งยากเลยหละครับ

ถึงแม้ผมจะปลุกปล้ำกับมันอยู่พักใหญ่
ผมก็ไม่สามารถลดรูปทำให้มันง่ายขึ้นได้
เลยเอาตัวอย่างเลขไปหาใน google
(เพราะตัวแปรในสมการนั้นไม่สากล)
(พิมพ์ค้นหาด้วยสมการไปก็ไม่มีชัวร์)

เลขที่ใช้หาใน google คือ 8 พจน์แรก
1 2 9 44 265 1854 14833 133496
และพบว่ามันลดรูปให้เป็นอนุกรมได้
(เค้าใช้การจัดหมู่พิสูจน์ ขี้เกียจอ่าน)
ผมเลยลองทำใหม่อีกรอบนึง
(พิสูจน์สูตรง่ายกว่าหาสูตรตั้งเยอะ)
โดยจัดรูปสมการของผมใหม่เป็น

d_n = nd_n-1-d_n-1+(n-1)d_n-2

โดยคราวนี้
n เป็นจำนวนเต็ม โดย n≥3
d_n คือ วิธีการที่สลับได้เมื่อมี n ช่อง
และกำหนดให้ d₁ = 0 และ d₂ = 1
(เปลี่ยนมาใช้ตัว d เพื่อให้เป็นสากล)
(ตอนนั้นคิดยังไงเลือกใช้ตัว q ก็ไม่รู้)

สมการใหม่นี้ พิสูจน์ตรงๆ เข้าใจยาก
เพราะตอนที่จับกลุ่มนั้น งงมากๆ
จึงขอพิสูจน์โดยใช้วิธีแทนค่านะครับ

แนวทางการพิสูจน์นั้น ทำได้โดยการ
เขียนตัวเลขให้ติดแฟกทอเรียลผลหาร
และปล่อยให้ติดแฟกทอเรียลไปเลย
(ไม่ต้องคำนวนออกมาเป็นเลข)

เมื่อแทนค่าไล่ไปเรื่อยๆ จะได้ผลดังนี้
d₃ = 3!/2! - 3!/3!
d₄ = 4!/2! - 4!/3! + 4!/4!
d₅ = 5!/2! - 5!/3! + 5!/4! - 5!/5!
d₆ = 6!/2! - 6!/3! + 6!/4! - 6!/5! +6!/6!

จึงสรุปได้ว่า
d_n = n!/2! - n!/3! + ... +(-1)ⁿn!/n!
(ใช้ได้ที่ n≥2 นะครับ)

ถ้าพิสูจน์แบบการจัดหมู่ (ตามเว็บ) จะได้
D(n) = n! - n!/1! + n!/2! - n!/3! + ... +(-1)ⁿn!/n!
(มีพจน์ n! - n!/1! โผล่ขึ้นมา)
(และ n เป็นจำนวนเต็มบวกแล้ว)

...จบ...

จบดีกว่าครับ หมดเรื่องที่จะฝอยละ
รักษาสุขภาพกันด้วยนะครับ ^^

อ้างอิง :
http://mathforum.org/library/drmath/view/56185.html