szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 09: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 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 10:14 
Użytkownik
Avatar użytkownika

Posty: 6108
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 11:19 
Użytkownik

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

Posty: 11816
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 
 Wyznaczyć liczbę podzbiorów  piotrek20008  1
 ile jest ciagow dlugosc  robertos18  6
 Ile istnieje ciągów liczb...  beacik  1
 Znajdź najmniejszą liczbę - zadanie 2  Tam29  3
 wyznaczyć liczbę podzbiorów - zadanie 3  RudaMa?aWied?ma  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl