Ciągi binarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gblablabla
Użytkownik
Użytkownik
Posty: 420
Rejestracja: 6 lis 2010, o 20:10
Płeć: Mężczyzna
Lokalizacja: Clausthal-Zellerfeld
Podziękował: 65 razy
Pomógł: 25 razy

Ciągi binarne

Post autor: gblablabla »

Ile jest ciągów binarnych \(\displaystyle{ n–}\)elwmwntowych, w których 0 nie występuje \(\displaystyle{ k}\) razy nierozdzielone jedyną (nie występuje \(\displaystyle{ k}\) razy pod rząd).
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Ciągi binarne

Post autor: arek1357 »

Po pierwsze sformułowanie zadania jest denne.

Po drugie po rozszyfrowaniu co autor miał na myśli zakładam:,

niech - \(\displaystyle{ a(n,k)}\) ilość ciągów spełniający to założenie gdzie:

\(\displaystyle{ n}\) - długość ciągu

\(\displaystyle{ k}\) - liczba oznaczająca ile jedynek nie może wystąpić w szeregu jedna za drugą

np: \(\displaystyle{ a(2,1)=1}\) oznacza, że jedynka nie wystąpi ani razu


\(\displaystyle{ a(2,2)=3}\) jedynka nie wystąpi dwa razy

itd...

zauważmy teraz, że z obserwacji wynika:

\(\displaystyle{ a(n,k)= {n \choose 0}+ {n \choose 1}+...+ {n \choose k-1} +C_{n}}\)

I teraz czym jest nasze \(\displaystyle{ C_{n}}\)

Otóż jeżeli ilość jedynek w ciągu przekroczy lub się zrówna z \(\displaystyle{ k}\)

a jak wiadomo \(\displaystyle{ k}\) jedynek nie może stać koło siebie, więc będą się tworzyć serie z mniejszą ilością jedynek poprzedzielane zerami!(Wcześniejsze przypadki nie miały z tym problemu bo i tak jedynek zawsze było mniej niż \(\displaystyle{ k}\)).

czyli np dla \(\displaystyle{ k}\) - jedynek mamy:

\(\displaystyle{ R}\)- serii złożonych z minimum:

z dwóch serii jedynek i serii zer co daje minimum \(\displaystyle{ R=3}\)

zer jest w tym przypadku: \(\displaystyle{ n-k}\) maxymalna liczba serii to oczywiście \(\displaystyle{ n}\)

Niech teraz \(\displaystyle{ R=2c+1}\) lub \(\displaystyle{ R=2c}\) - (Stosuję teraz wzór na serie)

dla \(\displaystyle{ R=2c}\)

\(\displaystyle{ R(k,c)=2 {k-1 \choose c-1} {n-k-1 \choose c-1}}\) - ilość ciągów o zadanej liczbie serii

natomiast dla:


dla \(\displaystyle{ R=2c+1}\)

\(\displaystyle{ R(k,c)= {k-1 \choose c} {n-k-1 \choose c-1}+{k-1 \choose c-1} {n-k-1 \choose c}}\) - podobnie

czyli można zapisać, że suma wszystkich serii dla pewnego \(\displaystyle{ k}\)

wyniesie:

\(\displaystyle{ S(k)= \sum_{c=3}^{k}R(k,c)}\)

I teraz dopiero nasze - \(\displaystyle{ C_{n}}\)

to suma wszystkich \(\displaystyle{ S(k)}\) od \(\displaystyle{ k}\) do \(\displaystyle{ n}\)

czyli:

\(\displaystyle{ C_{n}= \sum_{i=k}^{n}S(i)}\)

Pewnie można prościej...

ps. ciut zrobiłem zamieszania z \(\displaystyle{ R}\) bo nie mylić proszę ilość ciągów z ilością serii
ale można się domyślić z kontekstu...
ODPOWIEDZ