szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 sie 2017, o 21:05 
Użytkownik

Posty: 166
Lokalizacja: Polska
Znajdź \left| \{b \in \{0,1\}^{*} : \#_{0}(b) + 2\#_{1}(b) \le n \}\right|, gdzie \#_{x}(b) oznacza liczbę wystąpień symbolu x w ciągu b.

Wyliczyłem ilość ciągów spełniających zadanie dla kilku pierwszych n i wyszło mi:
f_{n} = F_{n+1}, gdzie F_{n} to n-ta liczba fibonacciego, a f_{n} to szukana liczba.
Następnie postępując jak w https://pl.wikipedia.org/wiki/Ciąg_Fibonacciego, korzystając z funkcji tworzącej dostaję wynik \frac{1}{ \sqrt{5} }\left( \frac{1 +  \sqrt{5} }{2} \right)^{n}


Czy wynik się zgadza? Macie jakieś inne pomysły jak to zrobić?
Góra
Mężczyzna Offline
PostNapisane: 30 sie 2017, o 21:19 
Użytkownik
Avatar użytkownika

Posty: 187
Lokalizacja: brak
Zamień to na ciągi o wyrazach będących zerem lub dwójką, wtedy szukasz takich ciągów, których suma nie przekracza n.
Góra
Mężczyzna Offline
PostNapisane: 31 sie 2017, o 19:09 
Użytkownik

Posty: 166
Lokalizacja: Polska
na pewno zerem lub dwójką, a nie jedynką lub dwójką?

Wydaje mi się, że szukane rozwiązanie to \sum_{i=0}^{\lfloor  \frac{n}{2}  \rfloor}  \sum_{j=0}^{n-2i} \frac{(i + j)!}{i!*j!},
gdzie sumujemy po liczbie jedynek (j) oraz liczbie dwójek (i) w ciągu.

Natomiast nie wiem jak to dalej ruszyć
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Znajdz liczbe ciagow  Plebsinio  3
 Ile jest różnych ciągów...  tajner  3
 Liczba ciągów - zadanie 3  lennyh  1
 Znajdź funkcję tworzącą ciągu zadanego wzorem rekurencyjn  antek_k  2
 Znajdź funkcję tworzącą ciągu rekurencyjnego  Arst  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl