Ciągi binarne
-
- 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
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).
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Ciągi binarne
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...
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...