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 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 25 lis 2017, o 09:14 
Użytkownik
Avatar użytkownika

Posty: 6852
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: 13358
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 
 Funkcje tworzące ciągów - zadanie 2  Sugre  1
 Określ liczbę chromatyczną grafu G rzędu n, n>=3 otrzymanego  kylercopeland  0
 Podaj stopień minimalny oraz liczbę krawędzi w grafie  rivit  1
 Wyznaczyć ostatnia cyfrę liczby  czerwonepomidory  3
 Wyznaczyć liczbę róznych rozwiązań równania  rivit  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl