Kombinatoryka - łańcuch bitowy

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Heron878
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 7 lut 2018, o 10:50
Płeć: Mężczyzna
Lokalizacja: Łódź

Kombinatoryka - łańcuch bitowy

Post autor: Heron878 »

Witam,
mam problem z tym zadaniem.
Jak wiele łańcuchów bitowych długości n nie zawiera 000?

Może znacie jakieś materiały, które pomogą mi rozwiązać tego typu zadanie.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Kombinatoryka - łańcuch bitowy

Post autor: Premislav »

Popatrz, jak z krótszych takich łańcuchów powstają dłuższe, ułóż równanie rekurencyjne, do tego dopisz warunki początkowe wynikające z rozważenia małych przypadków, rozwiąż np. metodą funkcji tworzących czy jak tam lubisz (sposobów jest co najmniej kilka).
ODPOWIEDZ