ciagi binarne

[zekori]

1) Ile jest ciągów binarnych o długości n?
Odpowiedź to \(\displaystyle{ 2^{n-k-1} }\)
Dlaczego nie \(\displaystyle{ 2^{n} }\)?
2)Ile jest ciągów o n zerach i m jedynkach zawierających k serii zer?
Odpowiedź to \(\displaystyle{ {n-1 \choose k-1} {m+1 \choose k}}\)

[a4karo]

A co to jest `k` w 1) ?

[kerajs]

Ad 2)
Zał: \(\displaystyle{ n \ge k \wedge m \ge k-1}\)
a) liczba podziałów n zer na k serii to liczba rozwiązań równania:
\(\displaystyle{ s_1+s_2+...+s_k=n }\) gdzie \(\displaystyle{ s_1,s_2,...,s_k \in \NN_+}\)
czyli \(\displaystyle{ {n-1 \choose k-1} }\)
b) między seriami zer jest k-1 serii jedynek. Ponadto seria jedynek może wystąpić przez pierwszą serią zer oraz za ostatnią serią zer. Liczba takich podziałów m jedynek to liczba rozwiązań równania:
\(\displaystyle{ s_p+s_1+s_2+...+s_{k-1}+s_z=m }\) gdzie \(\displaystyle{ s_1,s_2,...,s_{k-1} \in \NN_+ \wedge s_p,s_z \in \NN}\)
Podstawienie \(\displaystyle{ s_1=z_1+1 \wedge s_2=z_2+1 \wedge .... \wedge s_{k-1}=z_{k-1}+1}\) daje równanie:
\(\displaystyle{ s_p+z_1+z_2+...+z_{k-1}+s_z=m-(k-1) }\) gdzie \(\displaystyle{ s_p,z_1,z_2,...,z_{k-1},s_z \in \NN}\)
które ma \(\displaystyle{ {\left[ m-(k-1)\right] +(k+1)-1 \choose (k+1) -1} }\) rozwiązań

[FasolkaBernoulliego]

Nie łatwiej byłoby zrobić podstawienie do \(\displaystyle{ s_p}\) i \(\displaystyle{ s_z}\)?

[zekori]

A co to jest `k` w 1) ?

No właśnie nie mam pojęcia, według mnie odpowiedź powinna brzmieć \(\displaystyle{ 2^{n} }\)

Ad 2)
Zał: \(\displaystyle{ n \ge k \wedge m \ge k-1}\)
a) liczba podziałów n zer na k serii to liczba rozwiązań równania:
\(\displaystyle{ s_1+s_2+...+s_k=n }\) gdzie \(\displaystyle{ s_1,s_2,...,s_k \in \NN_+}\)
czyli \(\displaystyle{ {n-1 \choose k-1} }\)
b) między seriami zer jest k-1 serii jedynek. Ponadto seria jedynek może wystąpić przez pierwszą serią zer oraz za ostatnią serią zer. Liczba takich podziałów m jedynek to liczba rozwiązań równania:
\(\displaystyle{ s_p+s_1+s_2+...+s_{k-1}+s_z=m }\) gdzie \(\displaystyle{ s_1,s_2,...,s_{k-1} \in \NN_+ \wedge s_p,s_z \in \NN}\)
Podstawienie \(\displaystyle{ s_1=z_1+1 \wedge s_2=z_2+1 \wedge .... \wedge s_{k-1}=z_{k-1}+1}\) daje równanie:
\(\displaystyle{ s_p+z_1+z_2+...+z_{k-1}+s_z=m-(k-1) }\) gdzie \(\displaystyle{ s_p,z_1,z_2,...,z_{k-1},s_z \in \NN}\)
które ma \(\displaystyle{ {\left[ m-(k-1)\right] +(k+1)-1 \choose (k+1) -1} }\) rozwiązań

jest inny sposób na rozwiązanie tego zadania niż przez funkcje tworzące? Jeszcze ich nie omawialiśmy i nie rozumiem za bardzo

[FasolkaBernoulliego]

To są funkcje tworzące?

[Jan Kraszewski]

No właśnie nie mam pojęcia, według mnie odpowiedź powinna brzmieć \(\displaystyle{ 2^{n} }\)

I tak brzmi. Jednak ta druga odpowiedź sugeruje, że pytanie brzmiało inaczej...

JK

[FasolkaBernoulliego]

Wydaje mi się, że warto zrozumieć zaproponowany wyżej sposób rozwiązania, bo to ułatwia bezbolesne łyknięcie wielu zadań kombinatorycznych. Żałuję, że na studiach tego dobrze nie ogarnąłem.

Np. w punkcie (2a) chcemy ustalić jakie będziemy mieli te serie zer. Wszystkich zer mamy n, serii mamy mieć k. Ustaw sobie teraz te wszystkie zera obok siebie, np. dla n=5

0 0 0 0 0

Pogrupowanie ich w k serii to tak naprawdę ustawienie k-1 miejsc podziału (x) w n-1 możliwych miejsc (stąd wzór). Np. dla k = 5 mamy tylko jedną możliwość

0 x 0 x 0 x 0 x 0

a dla k = 4 możemy mieć

0 0 x 0 x 0 x 0
0 x 0 0 x 0 x 0
0 x 0 x 0 0 x 0
0 x 0 x 0 x 0 0

To jest równoważne liczbie całkowitych dodatnich rozwiązań równania
\(\displaystyle{ x_1 + x_2 + x_3 + x_4 = 5}\)
gdzie \(\displaystyle{ x_i}\) to po prostu długość i-tej serii. (W przypadku k,n - patrz rozwiązanie kerajsa).

Teraz w punkcie (2b) w każde wybrane miejsce podziału (x) trzeba wstawić serię jedynek, ale oprócz tego mogą (ale nie muszą) się one jeszcze pojawić na początku i końcu. Jak chcesz trochę inne rozwiązanie, to mamy 4 możliwości:

(2b1) nie ma jedynek z początku i z końca (dzielisz jedynki na k-1 serii)
(2b2) są jedynki z początku, ale nie ma z końca (dzielisz jedynki na k serii)
(2b3) nie ma jedynek z początku, ale są z końca (dzielisz jedynki na k serii)
(2b4) są jedynki i na początku, i na końcu (dzielisz jedynki na k+1 serii)

Rozwiązujesz tak jak wyżej i sumujesz.

[zekori]

Pogrupowanie ich w k serii to tak naprawdę ustawienie k-1 miejsc podziału (x) w n-1 możliwych miejsc (stąd wzór). Np. dla k = 5 mamy tylko jedną możliwość

skąd jest te n-1? Rozumiem, że te k-1 to jest oddzielenie tych serii zer?

Dodano po 6 minutach 15 sekundach:

Teraz w punkcie (2b) w każde wybrane miejsce podziału (x) trzeba wstawić serię jedynek, ale oprócz tego mogą (ale nie muszą) się one jeszcze pojawić na początku i końcu. Jak chcesz trochę inne rozwiązanie, to mamy 4 możliwości:

(2b1) nie ma jedynek z początku i z końca (dzielisz jedynki na k-1 serii)
(2b2) są jedynki z początku, ale nie ma z końca (dzielisz jedynki na k serii)
(2b3) nie ma jedynek z początku, ale są z końca (dzielisz jedynki na k serii)
(2b4) są jedynki i na początku, i na końcu (dzielisz jedynki na k+1 serii)

Rozwiązujesz tak jak wyżej i sumujesz.

nie wiem za bardzo jak to zsumować

[FasolkaBernoulliego]

skąd jest te n-1? Rozumiem, że te k-1 to jest oddzielenie tych serii zer?

Mamy k serii, więc potrzebujemy k-1 miejsc, w których "stawiamy znak podziału". Miejsc, gdzie możemy to zrobić jest n-1, bo możemy wstawić pomiędzy każdymi dwoma kolejnymi zerami. Czyli tak naprawdę wybieramy zbiór k-1 elementów ze zbioru (n-1)-elementowego. Stąd
\(\displaystyle{ {n - 1 \choose k - 1} }\)

nie wiem za bardzo jak to zsumować

Dla konkretnych liczb możesz na kalkulatorze, a żeby dostać wzór z odpowiedzi, to możesz np. zastosować trzy razy własność, przy użyciu której się tworzy trójkąt Pascala
\(\displaystyle{ {a - 1 \choose b - 1} + {a - 1 \choose b} = {a \choose b}}\)

[kerajs]

PS:    

1)

Nie łatwiej byłoby zrobić podstawienie do \(\displaystyle{ s_p}\) i \(\displaystyle{ s_z}\)?

Tak, troszkę łatwiej i ciut szybciej.
Wtedy byłoby:
(...)Liczba takich podziałów m jedynek to liczba rozwiązań równania:
\(\displaystyle{ s_p+s_1+s_2+...+s_{k-1}+s_z=m }\) gdzie \(\displaystyle{ s_1,s_2,...,s_{k-1} \in \NN_+ \wedge s_p,s_z \in \NN}\)
Podstawienie \(\displaystyle{ s_p=z_p-1 \wedge s_z=z_z-1 }\) daje równanie:
\(\displaystyle{ z_p+s_1+s_2+...+s_{k-1}+z_z=m+2}\) gdzie \(\displaystyle{ z_p,s_1,s_2,...,s_{k-1}, z _z \in \NN_+}\)
które ma \(\displaystyle{ {\left( m+2\right) -1 \choose (k+1) -1} }\) rozwiązań.

2)

jest inny sposób na rozwiązanie tego zadania niż przez funkcje tworzące? Jeszcze ich nie omawialiśmy i nie rozumiem za bardzo

Rozwiązanie bazuje na kombinacji z powtórzeniami, a nie funkcji tworzącej. Alternatywne wyjaśnienie wzorku: Jak obliczyć prawdopodobieństwo . Jak poszperasz, to pewnie znajdziesz podobne uzasadnienia na koralikach.

[zekori]

(2b1) nie ma jedynek z początku i z końca (dzielisz jedynki na k-1 serii)
(2b2) są jedynki z początku, ale nie ma z końca (dzielisz jedynki na k serii)
(2b3) nie ma jedynek z początku, ale są z końca (dzielisz jedynki na k serii)
(2b4) są jedynki i na początku, i na końcu (dzielisz jedynki na k+1 serii)

Rozwiązujesz tak jak wyżej i sumujesz.

dalej nie wiem za bardzo jakie to maja byc liczby, w sensie np z (2b1) jest ich \(\displaystyle{ {m-2 \choose k-1} }\)?(bo odpadaja 2 miejsca, z poczatku i konca)

[FasolkaBernoulliego]

No ale jak Ci to wyszło? Mam wrażenie, że losowo wstawiasz dane do wzoru. Skoro dzieląc \(\displaystyle{ n}\) zer na \(\displaystyle{ k}\) serii mamy \(\displaystyle{ {n-1 \choose k-1} }\) możliwości, to mając zupełnie analogiczną rzecz do zrobienia, czyli podzielenie \(\displaystyle{ m}\) jedynek na \(\displaystyle{ k - 1}\) serii, dostaniemy zupełnie w ten sam sposób \(\displaystyle{ {m - 1 \choose k-2} }\) możliwości... Zamiast \(\displaystyle{ n}\) piszesz \(\displaystyle{ m}\), a zamiast \(\displaystyle{ k}\) piszesz \(\displaystyle{ k-1}\) i tyle.