2553 : Combinatorics
อ้างอิง:
6. หาจำนวนลำดับเทอร์นารีที่มีความยาว 6 และผลบวกทุกพจน์เป็นจำนวนคู่
|
ตอบ 365
ให้ $a_n$ แทน จำนวนของสตริงฐานสาม n หลัก ที่ผลบวกของเลขโดดทุกตัวเป็นจำนวนคู่
ให้ $b_n$ แทน จำนวนของสตริงฐานสาม n หลัก ที่ผลบวกของเลขโดดทุกตัวเป็นจำนวนคี่
จะได้ $a_n + b_n = 3^n ...(*)$
หา $a_n$
$a_n = a_{n, 0} + a_{n,1} + a_{n, 2} = a_{n-1} + b_{n-1} + a_{n-1} = 2a_{n-1} + b_{n-1}$ ...(**)
แต่จากสมการ (*) จะได้ $b_{n-1} = 3^{n-1} - a_{n-1}$ แทนใน (**) จะได้ $$a_n = a_{n-1} + 3^{n-1} , a_1 = 2, a_2 = 5$$
ดังนั้น $a_6 = 365$