Znajdź \(\displaystyle{ \left| \{b \in \{0,1\}^{*} : \#_{0}(b) + 2\#_{1}(b) \le n \}\right|}\), gdzie \(\displaystyle{ \#_{x}(b)}\) oznacza liczbę wystąpień symbolu \(\displaystyle{ x}\) w ciągu \(\displaystyle{ b}\).
Wyliczyłem ilość ciągów spełniających zadanie dla kilku pierwszych n i wyszło mi: \(\displaystyle{ f_{n} = F_{n+1}}\), gdzie \(\displaystyle{ F_{n}}\) to n-ta liczba fibonacciego, a \(\displaystyle{ f_{n}}\) to szukana liczba.
Następnie postępując jak w
na pewno zerem lub dwójką, a nie jedynką lub dwójką?
Wydaje mi się, że szukane rozwiązanie to \(\displaystyle{ \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} \sum_{j=0}^{n-2i} \frac{(i + j)!}{i!*j!}}\),
gdzie sumujemy po liczbie jedynek (\(\displaystyle{ j}\)) oraz liczbie dwójek (\(\displaystyle{ i}\)) w ciągu.
