Bir topun etrafında pas atmanın yolları

Question

Beş kişi kendi aralarında topu geçiyor. Top Alonzo ile başlıyor. Topa sahip olan her kişi topu başka birine verir. Sekizinci geçişten sonra top Alonzo'ya geri döner. Olası geçiş sıralarının sayısını bulun.

Biliyorum ki 8 geçiş olduğu için $4^8$ Kısıtlama olmadığında ve sonrasında topu pas geçme yolları $7$ orada geçer $4^6$topu Alonzo'ya geri göndermenin yolları. Nasıl devam ederim?

Answer 1

Şununla başlayan yollarla sınırlı olarak yinelemeli çalışalım $A$ (koyduk $A$ içinde $0^{th}$ dizenin yuvası).

İzin Vermek $a_n$ uzunluk yollarının sayısı $n$ bunun sonu $A$. Gösterimi düzeltmek için baş harfin$A$uzunlukta sayılmaz. Böylece sahibiz$a_1=0$ örneğin, koyamadığımız için $A$ yuvada $1$.

İzin Vermek $b_n$ uzunluk yollarının sayısı $n$ bitmeyen $A$. Sonra,$b_1=4$ Örneğin.

Sizin de belirttiğiniz gibi, bizde $$a_n+b_n=4^n$$

Yinelemeli olarak, biz var $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

Bu zaten sorununuzu çözmek için yeterli ve $$\boxed{a_8=13108}$$ Biraz fazladan çalışma gösteriyor ki $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

İpucu:

İzin Vermek $a_n$ olası dizilerin sayısı $n$ Alonzo'nun topla başladığı yerden geçer ve Alonzo topu $n$inci geçiş. Sonra$a_1 = 0$ ve $a_2 = 4$.

Diyelim ki bir dizi $n$Alonzo'nun topla başladığı paslar ve topa sahip olan her kişi topu bir başkasına atar, ancak son pasın Alonzo'ya olması gerekmez. Her geçiş için 4 seçenek vardır, yani$4^n$olası diziler. İçinde$a_n$ Alonzo, topa sahip olan son kişidir, yani $4^n - a_n$ Alonzo'nun son kişi olmadığı diziler.

Şimdi özyinelemeyi kullanın. Alonzo'nun topu alamayacağını unutmayın.$n-1$inci geçiş.