Ilość n-cyfrowych liczb binarnych z niesąsiadującymi zerami

[hubertwojtowicz]

Zadaniem jest określenie ile jest n-cyfrowych liczb binarnych takich, że nie posiadają one sąsiadujących ze sobą zer.
np.:
dla n=4 mamy 5 takich liczb:
1010, 1011, 1101, 1110, 1111
dla n=5 mamy 8 takich liczb:
10101, 10110, 10111, 11010, 11011, 11101, 11110, 11111
itd.
Proszę o pomoc.

[alchemik]

Niech \(\displaystyle{ a_{n}}\) oznacza ilość liczb n-cyfrowych spełniające powyższe założenia.

Wtedy \(\displaystyle{ a_{n}=a_{n-1}+a_{n-2}}\)

Zauważ, że wszystkie liczby n-cyfrowe składają się, z takich liczb:
\(\displaystyle{ \overline{10X}}\), gdzie X oznacza liczby n-2 cyfrowe spełniające powyższe założenia
\(\displaystyle{ \overline{1Y}}\), gdzie Y oznacza liczby n-1 cyfrowe spełniające powyższe założenia.

Wyznacz sobie piersze liczby:
\(\displaystyle{ a_{1}=1 \\ a_{2}=2}\)

Wyżej masz podany wzór rekurencyjny (podobieństwo do ciągu Fibonacciego \(\displaystyle{ F_{n}}\), jednak \(\displaystyle{ F_{n+1}=a_{n}}\)), jeżeli chodzi o jawny to wstaw we wzorze jawnym ciągu Fibonacciego zamiast \(\displaystyle{ n}\) to \(\displaystyle{ n+1}\)

[abc666]

Można to zrobić rekurencyjnie poprzez doklejanie cyfry z prawej strony

mamy
n=1
1
n=2
10
11
n=3
101
111
110

Widzimy, że liczby z zerem na końcu, powstaje jedna, a dla liczby z jedynką dwie. Jeśli oznaczymy poprzez \(\displaystyle{ a_n}\) liczbę n-cyfrowych liczb z zerem na końcu a poprzez \(\displaystyle{ b_n}\) liczbę n-cyfrowych liczb z jedynką na końcu to liczba szukanych liczb wynosi.
\(\displaystyle{ c_n=a_n+2b_n}\)

Znajdujemy teraz wzory ciągów \(\displaystyle{ a_n}\) i \(\displaystyle{ b_n}\). Ponieważ jedynkę możemy dokleić zawsze to \(\displaystyle{ b_n=c_{n-1}}\). Zero możemy dokleić tylko tam gdzie jest jedynka więc \(\displaystyle{ a_n=b_{n-1}}\) a z tego \(\displaystyle{ a_n=c_{n-2}}\). Teraz podstawiamy nasze ciągi do pierwszego wzoru i orzymujemy.

\(\displaystyle{ c_n=c_{n-2}+2c_{n-1}}\)
Teraz już tylko prosa rekurencja do rozwiązania np. przy użyciu równań charakterystycznych a nasz ostateczny wzór to
\(\displaystyle{ c_n= \frac{ \sqrt{2}-2 }{4( \sqrt{2}-1 )} \left( (1- \sqrt{2} )^n-(1+ \sqrt{2} )^n\right)}\)

EDIT
Coś źle liczby wychodzą z tego mojego wyniku. Jakby ktoś wskazał gdzie błąd zrobiłem to było by miło.

[alchemik]

Widzimy, że liczby z zerem na końcu, powstaje jedna, a dla liczby z jedynką dwie. Jeśli oznaczymy poprzez \(\displaystyle{ a_n}\) liczbę n-cyfrowych liczb z zerem na końcu a poprzez \(\displaystyle{ b_n}\) liczbę n-cyfrowych liczb z jedynką na końcu to liczba szukanych liczb wynosi.
\(\displaystyle{ c_n=a_n+2b_n}\)

Ta ostatnia równość nie jest prawdą, zauważ, że wśród liczb n-cyfrowych w zapisie binarnym, mogą się znajdować tylko liczby n-cyfrowe z 1 bądź 0 na końcu nic wiecej nic mniej.

Zatem jeżeli przyjmujesz założenia jak wyżej to może być tylko:

\(\displaystyle{ c_n=a_n+b_n}\)

Dalej powinno pójśc dobrze.

[abc666]

Już widzę teraz, ale w moim rozwiązaniu bardziej chodziło o to że
\(\displaystyle{ c_n=a_{n-1}+2b_{n-1}}\)

[hubertwojtowicz]

A jeżeli uogólnilibyśmy problem do liczby o podstawie k, to jaka byłaby postać równania rekurencyjnego?

Chciałem sam to uogólnić, bo pierwotnie tak było w zadaniu, ale rekurencja nie jest moją najmocniejszą stroną... Przy okazji proszę o jakieś linki do stron z dobrymi opisami podobnych zagadnień dotyczących wyprowadzania i rozwiązywania równań rekurencyjnych.

Dziękuję za dotychczasową pomoc

[abc666]

Ciągnąc mój pomysł: mamy dla
\(\displaystyle{ n=1\ k-1}\) możliwości
teraz doklejamy cyfrę z prawej. Podobnie oznaczamy przez \(\displaystyle{ a_n}\) liczbę n-cyfrowych liczb zakończonych zerem a przez \(\displaystyle{ b_n}\) zakończonych nie-zerem wtedy
\(\displaystyle{ c_n=a_{n}+ b_{n}}\)
Ciąg \(\displaystyle{ a_n}\) wyraża się wzorem \(\displaystyle{ a_n=b_{n-1}}\) - będziemy mieć tyle liczb z zerami ile było bez zer ponieważ do takich zero możemy "przykleić".

Ponieważ nie-zero możemy przykleić zawsze to \(\displaystyle{ b_n=k \cdot c_{n-1}}\). Z tego wszystkiego dostajemy że
\(\displaystyle{ c_n=kc_{n-2}+kc_{n-1}=k(c_{n-2}+c_{n-1})}\)
Z warunkami początkowymi
\(\displaystyle{ a_1=k-1 \\
a_2=k^2-k}\)

No i teraz rozwiązujemy rekurencje przy pomocy r. charakterystycznych
Mamy równanie
\(\displaystyle{ x^2-kx-k=0}\)
z tego
\(\displaystyle{ x_1= \frac{k- \sqrt{k^2+4k} }{2} \\
x_2= \frac{k+ \sqrt{k^2+4k} }{2}}\)

\(\displaystyle{ c_n=Ax_1^n+Bx_2^n}\)
teraz
\(\displaystyle{ \begin{cases} k-1= \left(A \cdot x_1+B \cdot x_2 \right) \\
k(k-1)= \left(A \cdot x_1^2 +B \cdot x_2^2 \right)\end{cases}}\)
po podstawieniu, uproszczeniu i pomnożeniu przez dwa dostajemy
\(\displaystyle{ \begin{cases} 2(k-1)=A(k-\sqrt{k^2+4k} )+B(k+\sqrt{k^2+4k}) \\
2(k-1)=A(k-\sqrt{k^2+4k}+2)+B(k+\sqrt{k^2+4k}+2) \end{cases}}\)

po odjęciu od drugiego pierwszego dostajemy że \(\displaystyle{ A=-B}\), teraz już łatwo dostajemy
\(\displaystyle{ A= -\frac{k-1}{\sqrt{k^2+4k}} \\
B= \frac{k-1}{\sqrt{k^2+4k}}}\)

Wracamy do naszego wzoru
\(\displaystyle{ c_n=-\frac{k-1}{\sqrt{k^2+4k}} \left( \left( \frac{k- \sqrt{k^2+4k} }{2}\right) ^n- \left( \frac{k+ \sqrt{k^2+4k} }{2}\right) ^n\right)\\
c_n=-\frac{k-1}{\sqrt{k^2+4k} \cdot 2^n} \left( \left( k- \sqrt{k^2+4k} \right) ^n- \left( k+ \sqrt{k^2+4k} \right) ^n\right)}\)

Chyba jest dobrze, ale niech ktoś sprawdzi

hubertwojtowicz, przejrzyj dział Kompendium, możesz także poczytać ważniaka ... yskretna_1 oraz wikiepdie