Ilość ciągów binarnych

[Valiors]

Ile jest takich ciągów binarnych, że jest w nich X jedynek oraz Y zer i dodatkowo pomiędzy każdą parą jedynek musi znajdować się co najmniej 1 zero?

[sebnorth]

Zadanie nie jest dla mnie do końca jasne bo jeśli \(\displaystyle{ X = 10}\) a \(\displaystyle{ Y = 1}\) to nie ma takich ciągów.

Jeśli mamy ciągi powiedzmy długości n i zachodzi warunek 'pomiędzy każdą parą jedynek musi znajdować się co najmniej 1 zero' czyli warunek że nie ma w ciagu dwóch jedynek pod rząd

to jeśli sobie oznaczymy przez \(\displaystyle{ F_n}\) liczbę takich ciągów to zajdzie równość rekurencyjna:

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

bo jeśli ciąg kończy się 1 to wcześniej musi być 0 a przed zerem dowolny ciąg długości \(\displaystyle{ n-2}\) spełniający warunek zadania

lub ciąg kończy się na 0 a przed zerem dowolny ciąg długości \(\displaystyle{ n-1}\) spełniający warunek zadania

[Valiors]

Zakładam, że X oraz Y są takie, że zawsze da się zbudować taki ciąg binarny, oraz ciąg może się kończyć i zaczynać zerem.

[jarek4700]

Tutaj już to było.
359603.htm