szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Ciągi binarne
PostNapisane: 15 gru 2014, o 16:08 
Użytkownik

Posty: 420
Lokalizacja: Clausthal-Zellerfeld
Ile jest ciągów binarnych n–elwmwntowych, w których 0 nie występuje k razy nierozdzielone jedyną (nie występuje k razy pod rząd).
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
 Tytuł: Ciągi binarne
PostNapisane: 15 gru 2014, o 20:50 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
Po pierwsze sformułowanie zadania jest denne.

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

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

n - długość ciągu

k - liczba oznaczająca ile jedynek nie może wystąpić w szeregu jedna za drugą

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


a(2,2)=3 jedynka nie wystąpi dwa razy

itd...

zauważmy teraz, że z obserwacji wynika:

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

I teraz czym jest nasze C_{n}

Otóż jeżeli ilość jedynek w ciągu przekroczy lub się zrówna z k

a jak wiadomo 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ż k).

czyli np dla k - jedynek mamy:

R- serii złożonych z minimum:

z dwóch serii jedynek i serii zer co daje minimum R=3

zer jest w tym przypadku: n-k maxymalna liczba serii to oczywiście n

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

dla R=2c

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 R=2c+1

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 k

wyniesie:

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

I teraz dopiero nasze - C_{n}

to suma wszystkich S(k) od k do n

czyli:

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

Pewnie można prościej...

ps. ciut zrobiłem zamieszania z R bo nie mylić proszę ilość ciągów z ilością serii
ale można się domyślić z kontekstu...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ciągi binarne - zadanie 4  nxx  1
 Ciągi binarne - zadanie 2  iie  0
 ciągi binarne - zadanie 5  greniu69  4
 ciągi binarne - zadanie 3  olcia446  6
 Ciągi binarne - zadanie 8  karaoke120  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl