szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 lut 2015, o 14:52 
Użytkownik

Posty: 5620
Lokalizacja: Kraków
Problem
Niech f(n) będzie ilością tych układów
zero- jedynkowych, mających n składników
i takich że obok każdego zera jest jakieś ,choć jedno inne zero.
Czy istnieje formuła jawna bądź rekurencyjna na f(n) ?

Przykład:
Gdy n=3 to f(n)=3
istnieją tu układy:
0, 0, 0
0, 0, 1
1, 0, 0
ale i innych nie ma np.
1, 0, 1 (środkowe zero otoczone jedynkami)
0, 1, 0 (skrajne zera nie maja obok innych zer) etc.
Góra
Mężczyzna Offline
PostNapisane: 25 lut 2015, o 19:27 
Użytkownik

Posty: 454
Lokalizacja: Warszawa
Pierwsze refleksje. Warunek zadania sprowadza się do tego, że:
  • ciąg nie zaczyna się od 01,
  • w środku ciągu nie występuje 101,
  • ciąg nie kończy się 10.

Tak więc f(1)=1 (ciąg "1"), f(2)=2 (ciągi "00", "11") i teraz rekurencja. Mamy poprawny ciąg n-wyrazowy. Widzę takie możliwości stworzenia z niego ciągu n+1-wyrazowego:
…00|0
…00|1
…1|1
oraz ciągu n+2-wyrazowego:
…00|00
…00|01
…00|11
…1|00
…1|11
Jednakże można się obyć bez niektórych powyższych możliwości, a więc należy je wymazać, bo inaczej będziemy liczyć pewne ciągi podwójnie:
…00|00 = …00|0 × …00|0
…00|01 = …00|0 × …00|1
…00|11 = …00|1 × …00|1
…1|11 = …1|1 × …1|1
(mam nadzieję że zapis jest zrozumiały; napisałem znak mnożenia, bo jakoś tak mi się skojarzyło z mnożeniem permutacji, jak by kto chciał, może to sformalizować w tym kierunku)

Reasumując, mamy następujące możliwości wydłużania ciągu n-elementowego:
…00|0
…00|1
…1|1
…1|00

A co z tego wynika, napiszę później ;)

-- 25 lut 2015, o 20:33 --

Wprowadźmy takie oznaczenia:
…00|0 (reguła A)
…00|1 (reguła B)
…1|1 (reguła C)
…1|00 (reguła D)

Jest oczywiste, że każdy ciąg kończy się albo 1 albo 0. Jeśli kończy się 0, to jednocześnie kończy się 00. Zatem możemy napisać: f(n)=f_{00}(n)+f_1(n) (zapis mam nadzieję oczywisty).

W jaki sposób może powstać ciąg kończący się 00? Według reguły A lub D. Zatem f_{00}(n)=f_{00}(n-1)+f_1(n-2).

W jaki sposób może powstać ciąg kończący się 1? Według reguły B lub C. Zatem f_1(n)=f_{00}(n-1)+f_1(n-1).

Warunki brzegowe: f_{00}(1)=0,\ f_{00}(2)=1,\ f_1(1)=1,\ f_1(2)=1. Teraz wystarczy rozwiązać rekurencję znanymi metodami.

-- 25 lut 2015, o 20:36 --

mol_ksiazkowy napisał(a):
Przykład:
Gdy n=3 to f(n)=3
istnieją tu układy:
0, 0, 0
0, 0, 1
1, 0, 0

A tu nie wliczyłeś 1,1,1.
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2015, o 11:13 
Użytkownik

Posty: 5620
Lokalizacja: Kraków
Cytuj:
A tu nie wliczyłeś 1,1,1.
oczywiscie mozna wliczyc; domyślnie było tu założenie o istnieniu choć jednego zera...
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2015, o 11:26 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Mam taki pomysł:

a_{n+3}=a_{n+2}^0+a_{n+2}+a_{n}+1


a_{n+2}^0 te ciągi, które kończą się zerem

Z obserwacji:

a_{n+2}^0=a_{n+2}-a_{n+1}

reasumując:


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

a_{n+3}=2a_{n+2}-a_{n+1}+a_{n}+1

bo dodaję te które kończą się na 10 oraz same jedynki w ciągu n minus trzy

Nie biorę pod uwagę ciągu z samych jedynek jak zaproponował vpproff.

Do sprawdzenia ten mój pomysł na szybko...

Sprawdzałem na piechotę i wychodzi:

a_{1}=0: \emptyset

a_{2}=1 :00

a_{3}=3 :000,001,100

a_{4}=6 :0000,1000,0001,1100,0011,1001

a_{5}=11 :0000,10000,00100,00001,11000,10001,00011,11100,11001,00111,10011

a_{6}=20:

00000,100000,001000,000100,000001,110000,100100,000011,001001,100001,001100,

111000,110001,000111,100011,111100,111001,110011,100111,001111

a_{7}=36 :...- nie chce mi się już wypisywać

A co zgadza się ze wzorem rekurencyjnym (te wyniki)!

Czyli ostateczny wzór:

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

a_{n+3}=2a_{n+2}-a_{n+1}+a_{n}+1
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2015, o 15:51 
Użytkownik

Posty: 454
Lokalizacja: Warszawa
mol_ksiazkowy napisał(a):
Cytuj:
A tu nie wliczyłeś 1,1,1.
oczywiscie mozna wliczyc; domyślnie było tu założenie o istnieniu choć jednego zera...

OK, nie wiedziałem. W takim razie każde f(n) trzeba będzie pomniejszyć o 1, tzn. o ciąg złożony z samych jedynek.
Góra
Kobieta Offline
PostNapisane: 26 lut 2015, o 16:51 
Użytkownik
Avatar użytkownika

Posty: 2505
OEIS napisał(a):
A077855 a(n) is the number of binary words of length n+2 such that there is at least one run of 0's and every run of 0's is of length \ge 2. a(1)=3 because we have: \{0,0,0\}, \{0,0,1\}, \{1,0,0\}. Expansion of

\frac{1}{(1-x)(1-2x+x^2-x^3)}.

Co ciekawe, nie ma tam podanej zależności rekurencyjnej, ale odpowiedź arek1357 jest poprawna. Co my byśmy zrobili bez OEIS :D
Góra
Mężczyzna Offline
PostNapisane: 26 lut 2015, o 22:57 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Same jedynki można dołożyć lub nie kwestia gustu sam nawet o tym myślałem, wcale by to niczego nie zepsuło ale niech tam...

Proponuję teraz żeby nie rozpoczynać nowego wątku bo zadanie wydało mi się dość ciekawe
wyprowadzić wzór jawny...

Oraz policzyć:

\lim_{ n\to  \infty } \frac{a_{n}}{2^n}

Na mój gust ta granica oscyluje między:

\left\langle  \frac{1}{4}; \frac{1}{3}  \right\rangle

ps. nie znam OEIS może mi ją kiedyś przedstawisz będę wdzięczny!
Góra
Kobieta Offline
PostNapisane: 26 lut 2015, o 23:59 
Użytkownik
Avatar użytkownika

Posty: 2505
Wiemy, że ciąg z zadania to asymptotycznie to samo, co A005314, przez ciąg A000931 doszłam do wniosku, że asymptotycznie

a(n) \approx \frac{r^{2n+8}}{2r+3}.

To oznacza, że podany przez Ciebie iloraz to (w granicy)

\lim_n \left(\frac{r^2}{2}\right)^n \cdot \frac{r^8}{2r+3}

Niestety, ale ciąg jest zbieżny do zera (r to około 1.324 i jest pierwiastkiem x^3 = x+1).
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2015, o 01:34 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Nie rozumiem co to A005314 , i znaczy że:


\lim_{n \to \infty  } \frac{a_{n}}{2^n}=0 ???

W to nie mogę uwierzyć coś


\frac{a_{n}}{2^n}= \frac{0}{2}, \frac{1}{4}, \frac{3}{8}, \frac{6}{16}, \frac{11}{32}, \frac{20}{64}, \frac{36}{128},...

Choć patrząc na te liczby to jednak maleją może serio on biegnie do zera jak tak na to popatrzyłem to
może i masz rację a miałem nadzieję że tak nie będzie szkoda...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ciągi zera i jedynek  kowalski93  1
 dzielniki zera - zadanie 4  schokolade  1
 Współczynnik dwumianowy a k większe od zera  apex39  2
 Rekurencja, delta mniejsza od zera  combinev2  3
 Zera i jedynki w ciągu bez "00"  szymonides  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl