1.1
W ile ciągach binarnych złożonych z \(\displaystyle{ k}\) zer i \(\displaystyle{ n-k}\) jedynek żadne dwa zera nie sąsiadują ze sobą ?
1.2
W ile \(\displaystyle{ (n,m)}\)-ciągach każda seria jedynek jest poprzedzona nie krótszą od niej serią zer (\(\displaystyle{ n\le m}\)) ?
1.3
Ile ciągów złożonych z ośmiu liter \(\displaystyle{ \alpha}\) i osmiu liter \(\displaystyle{ \beta}\) w ktorych każda litera znajduje sie obok przynajmniej jednej takiej samej litery ?
Bardzo proszę o pomoc w rozwiązaniu tych zadań lub naprowadzenie na poprawne rozwiązanie Z góry dziękuje.
Ciągi zer i jedynek
Ciągi zer i jedynek
Ostatnio zmieniony 18 mar 2019, o 04:38 przez Afish, łącznie zmieniany 3 razy.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Poprawa wiadomości: z góry.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Poprawa wiadomości: z góry.
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Ciągi zer i jedynek
1)
Ustawiam jedynki. Z przerw między nimi (jest ich \(\displaystyle{ n-k-1}\)) oraz miejsca przed ciągiem jedynek i za tym ciągiem wybieram k miejsc dla zer, co daje ilość takich ciągów, że żadne dwa zera nie sąsiadują ze sobą.
\(\displaystyle{ il= {n-k-1+1+1 \choose k} \ \ \ \ \text{ jeśli} \ \ \ \ k \le n-k+1}\)
2)
a) \(\displaystyle{ n=m}\)
Serie zer są tak samo długie jak serie następujących po nich jedynek.
Jeśli \(\displaystyle{ i}\) to ilość serii to ilość ciągów zawierających po \(\displaystyle{ i}\) serii zer i jedynek to ilość rozwiązań równania \(\displaystyle{ x_1+...+x_i=n}\) w dodatnich liczbach całkowitych. Stąd ilość szukanych ciągów:
\(\displaystyle{ il= \sum_{i=1}^{n} {n-1 \choose i-1}}\)
b) \(\displaystyle{ n<m}\)
Ciąg który ma \(\displaystyle{ i}\) serii jedynek może zawierać \(\displaystyle{ i}\) lub \(\displaystyle{ i+1}\) serii zer.
Podobnie jak w a) ilość ciągów zawierających po \(\displaystyle{ i}\) serii jedynek to ilość rozwiązań równania \(\displaystyle{ x_1+...+x_i=n}\) w dodatnich liczbach całkowitych. Dokładnie takie same serie zer dokładam przed jedynki. Pozostałe \(\displaystyle{ m-n}\) rozdzielam między \(\displaystyle{ i}\) serii zer (ilość takich podziałów to ilość rozwiązań równania \(\displaystyle{ y_1+...+y_i=m-n}\) w dodatnich liczbach całkowitych) lub między \(\displaystyle{ i+1}\) serii zer ( to ilość rozwiązań równania \(\displaystyle{ y_1+...+y_i+y_{i+1}=m-n}\) w dodatnich liczbach całkowitych)
\(\displaystyle{ il= \sum_{i=1}^{n} {n-1 \choose i-1} {m-n-1 \choose i-1}+ \sum_{i=1}^{n} {n-1 \choose i-1} {m-n \choose i}}\)
3)
Osiem alf może tworzyć 1 serię na 1 sposób, dwie serie na 5 sposobów, trzy serie na 6 sposobów, a cztery serie tylko na 1 sposób. Jeśli ciąg zaczyna się od alfy to ilość serii bett będzie taka sama lub o jeden mniejsza.
\(\displaystyle{ il=2\left( 1 \cdot 1+5 \cdot 1+5 \cdot 5+6 \cdot 5+6 \cdot 6+6 \cdot 1+1 \cdot 1\right)=208}\)
Ustawiam jedynki. Z przerw między nimi (jest ich \(\displaystyle{ n-k-1}\)) oraz miejsca przed ciągiem jedynek i za tym ciągiem wybieram k miejsc dla zer, co daje ilość takich ciągów, że żadne dwa zera nie sąsiadują ze sobą.
\(\displaystyle{ il= {n-k-1+1+1 \choose k} \ \ \ \ \text{ jeśli} \ \ \ \ k \le n-k+1}\)
2)
a) \(\displaystyle{ n=m}\)
Serie zer są tak samo długie jak serie następujących po nich jedynek.
Jeśli \(\displaystyle{ i}\) to ilość serii to ilość ciągów zawierających po \(\displaystyle{ i}\) serii zer i jedynek to ilość rozwiązań równania \(\displaystyle{ x_1+...+x_i=n}\) w dodatnich liczbach całkowitych. Stąd ilość szukanych ciągów:
\(\displaystyle{ il= \sum_{i=1}^{n} {n-1 \choose i-1}}\)
b) \(\displaystyle{ n<m}\)
Ciąg który ma \(\displaystyle{ i}\) serii jedynek może zawierać \(\displaystyle{ i}\) lub \(\displaystyle{ i+1}\) serii zer.
Podobnie jak w a) ilość ciągów zawierających po \(\displaystyle{ i}\) serii jedynek to ilość rozwiązań równania \(\displaystyle{ x_1+...+x_i=n}\) w dodatnich liczbach całkowitych. Dokładnie takie same serie zer dokładam przed jedynki. Pozostałe \(\displaystyle{ m-n}\) rozdzielam między \(\displaystyle{ i}\) serii zer (ilość takich podziałów to ilość rozwiązań równania \(\displaystyle{ y_1+...+y_i=m-n}\) w dodatnich liczbach całkowitych) lub między \(\displaystyle{ i+1}\) serii zer ( to ilość rozwiązań równania \(\displaystyle{ y_1+...+y_i+y_{i+1}=m-n}\) w dodatnich liczbach całkowitych)
\(\displaystyle{ il= \sum_{i=1}^{n} {n-1 \choose i-1} {m-n-1 \choose i-1}+ \sum_{i=1}^{n} {n-1 \choose i-1} {m-n \choose i}}\)
3)
Osiem alf może tworzyć 1 serię na 1 sposób, dwie serie na 5 sposobów, trzy serie na 6 sposobów, a cztery serie tylko na 1 sposób. Jeśli ciąg zaczyna się od alfy to ilość serii bett będzie taka sama lub o jeden mniejsza.
\(\displaystyle{ il=2\left( 1 \cdot 1+5 \cdot 1+5 \cdot 5+6 \cdot 5+6 \cdot 6+6 \cdot 1+1 \cdot 1\right)=208}\)