โจทย์คอมบิช่วยหน่อยครับ

[boat25451]

จงหาจำนวนวิธีการสร้างคำที่มีความยาวnตัวอักษร โดยใช้ตัวอักษรa, b, c, dโดยห้ามa,และbติดกัน

[Napper]

แนวคิดข้อนี้คือใช้ความสัมพันธ์เวียนเกิดครับ

สำหรับ $n \ge 1$ กำหนดให้ $A_n,B_n,C_n,D_n$ คือจำนวนวิธีเรียงสตริง (ชุดตัวอักษร) ความยาว $n$ ตามเงื่อนไข (a,b ห้ามติดกัน) และขึ้นต้นด้วย a,b,c,d ตามลำดับ ดังนั้น คำตอบที่เราต้องการคือ $A_n+B_n+C_n+D_n$

สังเกตว่า a,b มีความสมมาตรกัน เพราะถ้าหากแทน a ด้วย b และแทน b ด้วย a ในสตริงหนึ่งๆที่ขึ้นต้นด้วย a ก็จะได้สตริงที่ขึ้นต้นด้วย b และการกระทำนี้ไม่ส่งผลต่อเงื่อนไขที่ว่า a,b ห้ามติดกัน จึงสรุปได้ว่า $A_n=B_n$ ทุก $n \ge 1$ และในทำนองเดียวกัน เราจะได้ว่า $C_n=D_n$ ทุก $n \ge 1$ เช่นกัน

ค่าเริ่มต้น

\begin{align}
A_1 &= 1 && \textrm{a}\\[5pt]
A_2 &= 3 && \textrm{aa, ac, ad}\\[5pt]
A_3 &= 11 && \textrm{aaa, aac, aad}\\
&&& \textrm{aca, acb, acc, acd}\\
&&& \textrm{ada, adb, adc, add}\\[15pt]

C_1 &= 1 && \textrm{c}\\[5pt]
C_2 &= 4 && \textrm{ca, cb, cc, cd}\\[5pt]
C_3 &= 14 && \textrm{caa, cac, cad}\\
&&& \textrm{cbb, cbc, cbd}\\
&&& \textrm{cca, ccb, ccc, ccd}\\
&&& \textrm{cda, cdb, cdc, cdd}
\end{align}

ความสัมพันธ์เวียนเกิด

ในการสร้างสตริงความยาว $n+1$ ที่ขึ้นต้นด้วย a เราสามารถแปะสตริงความยาว $n$ ข้างหลัง a ได้ทั้งสิ้น $A_n+C_n+D_n$ วิธี เพราะสตริงที่นำมาแปะต่อนั้นต้องขึ้นต้นด้วย a, c หรือ d เท่านั้น ห้ามขึ้นต้นด้วย b จึงได้ว่า

$A_{n+1}=A_n+C_n+D_n \quad$ ทุก $n \ge 1$

แต่ในการสร้างสตริงความยาว $n+1$ ที่ขึ้นต้นด้วย c นั้น เราสามารถแปะสตริงความยาว $n$ หลัง c ด้วยอะไรก็ได้ จึงได้ความสัมพันธ์เป็น

$C_{n+1}=A_n+B_n+C_n+D_n \quad$ ทุก $n \ge 1$

จากข้อมูล $A_n=B_n$ และ $C_n=D_n$ ลดรูปเหลือเป็นระบบสมการเวียนเกิดเชิงเส้น

\begin{align}
A_{n+1}&=A_n+2C_n\\[5pt]
C_{n+1}&=2A_n+2C_n
\end{align}
จัดให้เหลือตัวแปรเดียวโดยคำนวณ $A_{n+2}-2A_{n+1}$ และเขียน $A_{n+2}$ ในรูปของพจน์ที่ต่ำกว่าดังนี้

\begin{align}
A_{n+2}-2A_{n+1} & =(A_{n+1}+2C_{n+1})-2(A_n+2C_n)\\[5pt]
A_{n+2} & =3A_{n+1}-2A_n+2(C_{n+1}-2C_n)\\[5pt]
A_{n+2} & =3A_{n+1}-2A_n+2(2A_n)\\[5pt]
A_{n+2} & =3A_{n+1}+2A_n
\end{align}
สมการเวียงเกิดเชิงเส้นนี้มี characteristic equation คือ $r^2=3r+2$ ซึ่งมีรากเป็น $r=\frac{3 \pm \sqrt{17}}{2}$ ได้รูปแบบทั่วไปเป็น

$$A_n = k_1 \left(\frac{3 + \sqrt{17}}{2}\right)^n + k_2 \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

โดยที่ค่าคงที่ $k_1,k_2$ หาได้จากเงื่อนไขเริ่มต้น $A_1=1$ และ $A_2=3$ จะได้ $k_1=\frac{1}{\sqrt{17}}$ และ $k_2=-\frac{1}{\sqrt{17}}$ นั่นคือ

$$A_n = \frac{1}{\sqrt{17}} \left(\frac{3 + \sqrt{17}}{2}\right)^n - \frac{1}{\sqrt{17}} \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

เราสามารถหารูปทั่วไปของ $C_n$ ได้ในทำนองเดียวกัน หรือคำนวณจากความสัมพันธ์ $C_n=\frac{1}{2}(A_{n+1}-A_n)$ ได้เช่นกัน ได้ว่า

$$C_n = \left(\frac{1+\sqrt{17}}{4\sqrt{17}}\right) \left(\frac{3 + \sqrt{17}}{2}\right)^n + \left(\frac{-1+\sqrt{17}}{4\sqrt{17}}\right) \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

ซึ่งการคำนวณโดยใช้สูตรได้ว่า $A_3=11$ และ $C_3=14$ ตรงกับวิธีนับโดยตรงตอนหาเงื่อนไขเริ่มต้น

คำตอบ

โจทย์นี้ต้องการหาวิธีทั้งหมด จึงรวมทุกกรณีเป็น $A_n+B_n+C_n+D_n=2A_n+2C_n=C_{n+1}$ ซึ่งมีค่าเท่ากับ

$$\left(\frac{5+\sqrt{17}}{2\sqrt{17}}\right) \left(\frac{3 + \sqrt{17}}{2}\right)^n + \left(\frac{-5+\sqrt{17}}{2\sqrt{17}}\right) \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

สำหรับทุก $n \ge 1$