ciagi binarne
-
- Użytkownik
- Posty: 25
- Rejestracja: 26 sty 2020, o 20:28
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 8 razy
ciagi binarne
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}}\)
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}}\)
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: ciagi binarne
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ń
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ń
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: ciagi binarne
Nie łatwiej byłoby zrobić podstawienie do \(\displaystyle{ s_p}\) i \(\displaystyle{ s_z}\)?
-
- Użytkownik
- Posty: 25
- Rejestracja: 26 sty 2020, o 20:28
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 8 razy
Re: ciagi binarne
No właśnie nie mam pojęcia, według mnie odpowiedź powinna brzmieć \(\displaystyle{ 2^{n} }\)
jest inny sposób na rozwiązanie tego zadania niż przez funkcje tworzące? Jeszcze ich nie omawialiśmy i nie rozumiem za bardzokerajs pisze: ↑8 mar 2020, o 05:26 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ń
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
-
- Administrator
- Posty: 34293
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: ciagi binarne
I tak brzmi. Jednak ta druga odpowiedź sugeruje, że pytanie brzmiało inaczej...
JK
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: ciagi binarne
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.
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.
-
- Użytkownik
- Posty: 25
- Rejestracja: 26 sty 2020, o 20:28
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 8 razy
Re: ciagi binarne
skąd jest te n-1? Rozumiem, że te k-1 to jest oddzielenie tych serii zer?FasolkaBernoulliego pisze: ↑8 mar 2020, o 15:29
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ść
Dodano po 6 minutach 15 sekundach:
nie wiem za bardzo jak to zsumowaćFasolkaBernoulliego pisze: ↑8 mar 2020, o 15:29
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.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: ciagi binarne
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} }\)
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}}\)
-
- Użytkownik
- Posty: 25
- Rejestracja: 26 sty 2020, o 20:28
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 8 razy
Re: ciagi binarne
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 pisze: ↑8 mar 2020, o 15:29
(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.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: ciagi binarne
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.