ciągi binarne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
greniu69
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 13 kwie 2011, o 19:21
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 2 razy

ciągi binarne

Post autor: greniu69 »

Bardzo proszę o pomoc w zadaniu
ile jest ciągów binarnych o długości \(\displaystyle{ n}\), w których jest dokładnie \(\displaystyle{ k}\) par \(\displaystyle{ 01}\)?
Ostatnio zmieniony 5 paź 2012, o 20:53 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

ciągi binarne

Post autor: norwimaj »

Co otrzymasz, gdy podzielisz taki ciąg na maksymalne podsłowa składające się z samych jedynek albo z samych zer? Np. \(\displaystyle{ 00,111,0,1111}\) albo \(\displaystyle{ 1,0,111,0,11,00}\). Pierwszy z tych przykładów przepiszę ze sztucznie dodanymi przecinkami, żeby zaznaczyć, że na początku jest zero jedynek a na końcu zero zer: \(\displaystyle{ ,00,111,0,1111,}\). Liczba wszystkich ciągów to liczba możliwości postawienia tych przecinków.
greniu69
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 13 kwie 2011, o 19:21
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 2 razy

ciągi binarne

Post autor: greniu69 »

Myślałem o rozpatrywaniu tego ze względu na skrajne wartości czyli rozbiciu na 4 przypadki. Widzę że całkowicie w złą stronę szedłem, niestety nie do końca rozumiem to co napisałeś, mógłbyś to zrobić bardziej łopatologicznie? Poparcie tego jakimś przykładem byłoby mile widziane. Dzięki z góry bo naprawdę chciałbym to zrozumieć.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

ciągi binarne

Post autor: norwimaj »

greniu69 pisze:Myślałem o rozpatrywaniu tego ze względu na skrajne wartości czyli rozbiciu na 4 przypadki. Widzę że całkowicie w złą stronę szedłem,
Rozpatrzenie czterech przypadków też powinno działać, tylko wynik nie będzie od razu w najprostszej postaci.
greniu69 pisze:Poparcie tego jakimś przykładem byłoby mile widziane.
\(\displaystyle{ n=5,k=1}\)

Mamy najpierw ciąg (być może pusty) jedynek, potem niepusty ciąg zer i niepusty ciąg jedynek, następnie ciąg zer. Razem \(\displaystyle{ 4}\) ciągi, więc \(\displaystyle{ 3}\) przecinki je oddzielające. Przecinki mogą stać pomiędzy liczbami albo na początku, albo na końcu ciągu. Łącznie \(\displaystyle{ 6}\) miejsc dla przecinków (na jednym miejscu tylko jeden przecinek). Zatem przecinki możemy postawić na \(\displaystyle{ \binom63}\) sposobów. Każdemu ustawieniu przecinków odpowiada dokładnie jeden ciąg, na przykład \(\displaystyle{ ,??,?,??}\) to ciąg \(\displaystyle{ ,00,1,00}\), czyli \(\displaystyle{ 00100}\).
greniu69
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 13 kwie 2011, o 19:21
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 2 razy

ciągi binarne

Post autor: greniu69 »

Dzięki wielkie, bardzo mi pomogłeś.
ODPOWIEDZ