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 ?
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 10:14 
Użytkownik
Avatar użytkownika

Posty: 6501
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

Posty: 12616
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ć permutację znając cykle  juvex  4
 Określ liczbę chromatyczną grafu G rzędu n, n>=3 otrzymanego  kylercopeland  0
 jak sprawdzić punkty wspólne dwóch ciągów - zadanie 3  Rebus27  6
 Pytanie o liczbe podzbiorów zbioru z powtórzeniami  anulak  1
 Wyznaczyć równianie ogólne rekurencji.  2moonface  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl