Temat: W ile ciagow binarnych

W ile ciagow binarnych o n jedynkach, m zerach
i k seriach jedynek, kazda seria jedynek jest poprzedzona nie krotsza od niej seria zer. Dla
jakich n,m,k liczba takich ciagow jest wieksza od 0

Temat: W ile ciagow binarnych

Jeżeli chodzi o wartości parametrów, dla których ilość ciągów jest niezerowa, to wystarczy wziąć: k<=n<=m
Ilość ciągów: k^(m-k)
Szkic rozumowania:
Załóżmy, że mamy k tub, do których możemy wrzucać kule.
Mamy n kul czarnych i m kul białych.
Ponieważ mamy mieć k ciągów, więc do każdej tuby wrzucamy po jednej kuli czarnej. Resztę, czyli n-k kul rozmieszczamy dowolnie. Możemy to zrobić na k^(n-k) sposobów.
Teraz dokładamy kule białe. Zgodnie z warunkiem zadania, kule czarne muszą być poprzedzone odpowiednią ilością kul białych. Czyli dodajemy do każdej tuby tyle białych kul, ile jest w niej czarnych. A pozostałą ilość białych rozmieszczamy dowolnie. Do każdego układu czarnych kul mamy k^(m-n) sposobów rozłożenia kul białych.
Sumując łącznie dostajemy, że kule czarne i białe w tubach można rozłożyć na k^(n-k) x k^(m-n) sposobów. Czyli k^(m-k)
Jak widać wynik nie zależy od n, co nie jest dla mnie zrozumiałe. Dlatego podałem szkic rozumowania, celem wykrycia ewentualnych błędów. Mam nadzieję, że będzie pomocny.Grzegorz K. edytował(a) ten post dnia 13.09.10 o godzinie 01:46

Temat: W ile ciagow binarnych

Grzegorz K.:
Jeżeli chodzi o wartości parametrów, dla których ilość ciągów jest niezerowa, to wystarczy wziąć: k<=n<=m

> Ilość ciągów: k^(m-k)
>
Chyba jednak coś jest nie tak w rozumowaniu. Wystarczy podać kontrprzykład (n,m,k)=(2,3,1). Według wzoru wychodzi 1, a przecież można z ręki podać

00011

00110

Wydaje mi się, że poprawnym wzorem jest:

Binom(n-1,k-1)*Binom(m-n+k,m-n)

Dowód:
Zacznijmy od ustawienia ciągu n-zer. Następnie musimy ten ciąg podzielić na k serii, aby to zrobić trzeba z (n-1) możliwych miejsc pomiędzy jedynkami wybrać (k-1) i "wepchnąć tam odstępy", następnie bierzemy n zer i ustawiamy je w ten sposób aby był spełniony warunek na poprzedzanie każdej serii jedynek odpowiednią ilością zer. Do tej pory mamy w sumie

Binom(n-1,k-1)

możliwości. Pozostało upchnięcie pozostałych (m-n) zer. Każde z pozostałych zer możemy albo dorzucić na początek którejś z serii albo dorzucić na koniec ciągu, zatem (m-n) razy wybieramy ze zbioru (k+1) elementowego, ale elementy mogą się powtarzać (możemy np. wszystkie zera wrzucić w jedno miejsce). Zatem dostajemy

Binom(m-n+k,m-n)

możliwości. Ostatecznie stosujemy zasadę mnożenia i dochodzimy do wyniku.

Jeżeli się gdzieś rypnąłem w dowodzie to od razu dzięki za poprawki:)Grzegorz Melniczak edytował(a) ten post dnia 13.09.10 o godzinie 13:59