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

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

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

โดยผมสังเกตได้จากเกม 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 \ge 3$
$q_n$ คือ วิธีการที่สลับได้เมื่อมี $n$ ช่อง
ที่ให้ $n \ge 3$ เพราะไม่อยากนิยาม $q_0$, $q_{-1}$
(จะปรากฎเมื่อหา $q_1$, $q_2$ จากสมการ)
และกำหนดให้ $q_1 = 0$ และ $q_2 = 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_3$
ขั้นตอนที่สอง เอา 2 ไว้ที่อื่น
จะทำได้ 3 วิธี ซึ่งเหมือนกับ $q_4$
ขั้นตอนสุดท้าย เอา 4 คูณ $q_4 + q_3$
จึงได้ว่า $q_5 = 4(q_4 + q_3) = 44$ วิธี

ถึงตรงนี้ก็ตอบโจทย์ได้แล้ว
$q_7 = 6(q_6 + q_5) = 1854$

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

ยังๆๆ
เราต้องไม่พอใจอะไรง่ายๆ สิครับ
เพราะมันเป็นความสัมพันธ์เวียนเกิด
ซึ่งมันใช้ยากหน่อย เช่น จะหา $q_{1000}$
ก็ต้องหา $q_{999}, q_{998}, q_{997}, \dots$
โครตจะยุ่งยากเลยหละครับ

ถึงแม้ผมจะปลุกปล้ำกับมันอยู่พักใหญ่
ผมก็ไม่สามารถลดรูปทำให้มันง่ายขึ้นได้
เลยเอาตัวอย่างเลขไปหาใน 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 \ge 3$
$d_n$ คือ วิธีการที่สลับได้เมื่อมี $n$ ช่อง
และกำหนดให้ $d_1 = 0$ และ $d_2 = 1$
(เปลี่ยนมาใช้ตัว $d$ เพื่อให้เป็นสากล)
(ตอนนั้นคิดยังไงเลือกใช้ตัว $q$ ก็ไม่รู้)

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

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

เมื่อแทนค่าไล่ไปเรื่อยๆ จะได้ผลดังนี้

$$\begin{align*} d_3 &= 3!/2! - 3!/3! \\ d_4 &= 4!/2! - 4!/3! + 4!/4! \\ d_5 &= 5!/2! - 5!/3! + 5!/4! - 5!/5! \\ d_6 &= 6!/2! - 6!/3! + 6!/4! - 6!/5! + 6!/6! \end{align*}$$

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

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

…จบ…

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

อ้างอิง :
math forum