15 Basamaklı Sayı {Çözüldü}

[senior]

Sadece 1, 2 ve 3 rakamlarını kullanarak 15 basamaklı sayılar oluşturacağız, bu sayıların hiçbirinde ardışık 2 veya ardışık 3 görmek istemiyoruz. Kaç farklı sayı oluşturabiliriz?

[çılgın]

Sorudaki şartı sağlayan $x$ basamaklı sonundaki rakam $y$ olan sayıların sayısı $f(x,y)$, sorudaki şartı sağlayan $x$ basamaklı sayıların sayısı ise $g(x)$ olsun. Yani $g(x)=f(x,1)+f(x,2)+f(x,3)$ olur. Kolayca gözlemleyebileceğimiz şekilde $f(x+1,1)=f(x,1)+f(x,2)+f(x,3)$ olur, çünkü $1$ rakamı ile ilgili herhangi bir kısıtlama yoktur. $f(x+1,2)=f(x,1)+f(x,3)$ olur, çünkü $f(x,2)$ deki sayıların sonuna $2$ ekleyemeyiz. Benzer şekilde $f(x+1,3)=f(x,1)+f(x,2)$ olur, bu da demektir ki $g(x+1)=3f(x,1)+2f(x,2)+2f(x,3)=2g(x)+f(x,1)=2g(x)+f(x-1,1)+f(x-1,2)+f(x-1,3)=2g(x)+g(x-1)$ olur. Soruda $15$ için istendiğinden $1$ den itibaren tüm $g$ leri hesaplayarak bulabiliriz. $g(1)=3$ ve $g(2)=7$ olduğu açıktır. Bu diziyi devam ettirerek $g(15)=665857$ buluruz.

Soruyu $n$ için genellemek istersek dizinin karakteristik denklemini çözerek bir genel form bulmamız gerekecektir.