Wzór rekurencyjny

[arek1357]

Wyznacz wzór jawny czegoś takiego:

\(\displaystyle{ a_{n+2,k+1}=a_{n+1,k+1}+a_{n,k}}\) dla: \(\displaystyle{ 0\le k \le n ,n \ge 1}\)

z warunkami brzegowymi:

\(\displaystyle{ a_{n,0}=1 , a_{n,1}=n}\)

\(\displaystyle{ a_{2k,k}=k+1 , a_{2k+1,k+1}=1}\)

\(\displaystyle{ a_{2k,s}=0}\) , dla:\(\displaystyle{ s>k}\)

\(\displaystyle{ a_{2k+1,s}=0}\) , dla:\(\displaystyle{ s>k+1}\)

A żeby nie było , że to wymyśliłem z sufitu, otóż wymyśliłem ale to jest wzór na ilość ciągów
o długości \(\displaystyle{ n}\) złożonych z \(\displaystyle{ k}\) jedynek, takich, że żadne dwie jedynki nie stoją koło siebie!
Zer jest:\(\displaystyle{ n-k}\)

To zadanie jest kwintesencją tego (zadania 11): 394175.htm

[jutrvy]

Żeby nie było :p można to policzyć prościej. Ustawiasz sobie zera w rządku i wtykasz między nie lub na początku lub na końcu rządku najwyżej jedną jedynkę. Ile sposobów?

[arek1357]

To ja te sposoby policzyłem rekurencyjnie rekurencja stosunkowo prosta ale dwóch zmiennych można zrobić coś takiego:

\(\displaystyle{ a_{n+2,k+1}=a_{n+1,k+1}+a_{n,k}}\)

Po podzieleniu obie strony przez \(\displaystyle{ a_{n,k}}\) otrzymamy:

\(\displaystyle{ \frac{a_{n+2,k+1}}{a_{n,k}}= \frac{a_{n+1,k+1}}{a_{n,k}}+1}\)

i podstawimy:

\(\displaystyle{ s_{n+2,k+1}= \frac{a_{n+2,k+1}}{a_{n,k}}}\)

\(\displaystyle{ s_{n+1,k+1}=\frac{a_{n+1,k+1}}{a_{n,k}}}\)

równanie się uprości:

\(\displaystyle{ s_{n+2,k+1}=s_{n+1,k+1}+1}\)