szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 08:48 
Użytkownik

Posty: 85
Lokalizacja: Polska
Ile ciągów ternarnych (tj. złożonych z cyfr 0, 1, 2) spełnia tę własność, że po żadnej jedynce nie występuje ani 2 ani 0?

Z tego co na razie rozpisałem to :

s_1 = {0,1,2}\\
s_2 = {00, 01, 02, 11, 20, 21, 22}

czyli

s_1 = 3\\
s_2 =7

Z tego wynika, że po 0 oraz po 2 mogę mieć cokolwiek
0,........ s_n\\
2,........ s_n

Na tym etapie mogę już napisać, że s_{n+1} = 2s_n + ?


Pytajnik: jak zapisać problem z jedynkami? Będzie w takiej postaci?
1,1,1,1,1,1,....... ?
1^n ?
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 09:14 
Użytkownik
Avatar użytkownika

Posty: 6637
Pojawienie się jedynki sprawia że dalej mogą być wyłącznie jedynki.

Ciągów o długości n jest:
1+2+2^2+2^3+...+2^n=2^{n-1}-1
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 10:19 
Użytkownik

Posty: 85
Lokalizacja: Polska
Nie bardzo rozumiem.. Mógłbyś jakoś bardziej to rozpisać?
Dziękuję!
Góra
Mężczyzna Online
PostNapisane: 25 lis 2017, o 13:01 
Użytkownik
Avatar użytkownika

Posty: 13133
Lokalizacja: Wrocław
kerajs napisał(a):
Pojawienie się jedynki sprawia że dalej mogą być wyłącznie jedynki.

A to nie tłumaczy wszystkiego?
Skoro po żadnej jedynce nie może być zera ani dwójki, zatem gdy wystąpi jedynka, to następny wyraz ciągu nie może być ani dwójką, ani zerem, więc (o ile ciąg już się nie urywa) następny wyraz to znów jedynka. No ale po tej kolejnej jedynce znów nie możemy postawić zera ani dwójki, więc może być tylko jedynka. Zatem jeśli pierwsza jedynka pojawi się w k-tym miejscu, k \in 1\ldots n , to na 2^{k-1} sposobów (k=1\ldots n} rozmieszczamy zera/dwójki na pierwszych k miejscach, a dalej (o ile jest coś „dalej") mają być same jedynki.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczbę A zapisac w postaci (n do k)  saerimne  2
 funkcja tworzaca splotu ciagow  marcyk00  12
 Ile istnieje ciągów liczb...  beacik  1
 Rekurencja - wyznaczyć wzór ogólny.  Hyuuga Neji  2
 Ile jest takich ciągów?  marcin_p321  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl