szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Ciąg binarny
PostNapisane: 20 lis 2016, o 12:27 
Użytkownik

Posty: 106
Ile jest wszystkich (n+1,n) ciągów binarnych, w których żadne dwa zera nie stoją obok siebie?

Jak mam rozumieć zapis (n+1,n) ciągów binarnych?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Ciąg binarny
PostNapisane: 20 lis 2016, o 17:49 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Ja spróbuję się odnieść do słownej części zadania bo do tego zapisu w nawiasie nie odniosę się bo nie rozumiem go.

A więc: ile jest ciągów długości n, u których dwa zera nie stoją koło siebie:

dla n=1 mamy:

0,1 , czyli a_{1}=2


dla n=2 mamy:

01,10,11 , czyli a_{2}=3


dla n=3 mamy:

010,110,011,101, 111 , czyli a_{3}=5

ogólnie, łatwo zaobserwować:

a_{1}=2, a_{2}=3


a_{n+2}=a_{n+1}+a_{n}
Góra
Mężczyzna Offline
 Tytuł: Ciąg binarny
PostNapisane: 20 lis 2016, o 19:26 
Użytkownik

Posty: 1076
Lokalizacja: Lublin/Warszawa
Obserwacja w przypadku takiego zadania to trochę słabe podejście.

Niby wychodzi ciąg Fibonacciego, ale dlaczego?

Z powodu interpretacji kombinatorycznej -
Załóżmy, że mamy ciąg długości n + 2. Jeżeli na jego końcu jest 1, to wcześniej może być dowolna liczba, czyli takich ciągów jest tyle co ciągów długości n + 1, czyli _{} a_{n  +1}. W przeciwnym przypadku na końcu jest 0, więc wcześniej musi stać 1, bo dwa zera nie mogą stać obok siebie - ciągów jest tyle co ciągów długości n, czyli a_{n}. Dlatego jest a_{n+2}=a_{n+1}+a_{n}.
Góra
Mężczyzna Offline
 Tytuł: Ciąg binarny
PostNapisane: 20 lis 2016, o 22:19 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
A myślisz, że ja jak to zauważyłem dokładając jedynką do każdego o jeden mniejszego i zero o dwa mniejszego...oraz, i tym sposobem suma dwóch poprzednich daje następny.
Resztę zostawiłem w domyśle dla autora.

Czasem się tak składa, że jeśli coś piszę to wiem co piszę.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ciąg binarny - zadanie 5  prawyakapit  6
 ciąg binarny - zadanie 4  Dawidzi?tko  2
 Ciąg binarny  brasco  1
 ciąg binarny - zadanie 2  robin5hood  0
 ciąg binarny - zadanie 3  robin5hood  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl