Witam zwracam się do Was o pomoc mam zadanie nad którym męczę się już kilka godzin. Mianowicie treść jego jest następująca:
Mamy alfabet, który składa się z 0,1,2. Ile można utworzyć ciągów 10 elementowych niemalejących
np. 0,0,0,0,0,0,1,1,2,2
Wiem, że to będzie na pewno wariacja z powtórzeniami
Dziękuje za pomoc
Mamy alfabet który składa sie z ...
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Mamy alfabet który składa sie z ...
Ja bym to rozwiązał kombinacją z powtórzeniami.
Moje rozumowanie jest takie: zapisujesz sobie ciąg dziesięciu jedynek, na początku i na końcu stawiasz barierki:
|1111111111|
Musisz teraz wstawić dwie dodatkowe barierki, między dwie jedynki albo między jedynkę a barierkę, np.
|11|11111|111| albo ||11111|11111|
Sumujesz liczby między kolejnymi barierkami (tu będzie 2,5,3), a otrzymane liczby jednoznacznie wyznaczają ilość kolejno zer, jedynek i dwójek w danym ciągu (tu dwa zera, pięć dwójek i trzy trójki).
Barierki możesz wstawić na 11 miejscach, przy czym możesz postawić dwie barierki w tym samym miejscu (np.zapis |1111111||111| odpowiada ciągowi: siedem zer, zero jedynek, trzy trójki).
Ponieważ masz wybrać z 11 pozycji dwie, na których postawisz barierkę, a dopuszczalne jest wybranie dwóch tych samych miejsc, to na podstawie kombinacji z powtórzeniami stwierdzasz, że szukana liczba ciągów wynosi \(\displaystyle{ {11+2-1 \choose 2}= {12 \choose 2}}\).
Moje rozumowanie jest takie: zapisujesz sobie ciąg dziesięciu jedynek, na początku i na końcu stawiasz barierki:
|1111111111|
Musisz teraz wstawić dwie dodatkowe barierki, między dwie jedynki albo między jedynkę a barierkę, np.
|11|11111|111| albo ||11111|11111|
Sumujesz liczby między kolejnymi barierkami (tu będzie 2,5,3), a otrzymane liczby jednoznacznie wyznaczają ilość kolejno zer, jedynek i dwójek w danym ciągu (tu dwa zera, pięć dwójek i trzy trójki).
Barierki możesz wstawić na 11 miejscach, przy czym możesz postawić dwie barierki w tym samym miejscu (np.zapis |1111111||111| odpowiada ciągowi: siedem zer, zero jedynek, trzy trójki).
Ponieważ masz wybrać z 11 pozycji dwie, na których postawisz barierkę, a dopuszczalne jest wybranie dwóch tych samych miejsc, to na podstawie kombinacji z powtórzeniami stwierdzasz, że szukana liczba ciągów wynosi \(\displaystyle{ {11+2-1 \choose 2}= {12 \choose 2}}\).
-
- Użytkownik
- Posty: 3
- Rejestracja: 10 sty 2010, o 21:03
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 1 raz
Mamy alfabet który składa sie z ...
Hmm no kozacki pomysł Tylko mam jeszcze jedno pytanie z czego bierze się ten -1 no bo rozumiem ze 11 to tyle na tyle sposobów możemy ustawić kreskę 2 bo mamy ciąg z 3 znaków a czemu ten -1 ?
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Mamy alfabet który składa sie z ...
Hmmm... ogólnie wzór na kombinacje z powtórzeniami wygląda tak:
Istnieje \(\displaystyle{ {n+k-1 \choose k}}\) kombinacji k-elementowych z powtórzeniami zbioru n-elementowego.
Jak bardzo chcesz, mogę napisać dowód (ale jest odrobinę skomplikowany).
Istnieje \(\displaystyle{ {n+k-1 \choose k}}\) kombinacji k-elementowych z powtórzeniami zbioru n-elementowego.
Jak bardzo chcesz, mogę napisać dowód (ale jest odrobinę skomplikowany).
-
- Użytkownik
- Posty: 3
- Rejestracja: 10 sty 2010, o 21:03
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 1 raz
Mamy alfabet który składa sie z ...
Sorry troszkę się zakręciłem i już zgłupiałem spróbuje to rozwiązać-- 10 sty 2010, o 23:37 --Wyszło mi 12...
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Mamy alfabet który składa sie z ...
12 ciągów?
0000000000
1111111111
2222222222
0111111111
0222222222
0122222222
0112222222
0111222222
0111122222
0111112222
0111111222
0111111122
0012222222
To już 13...a jest więcej.
0000000000
1111111111
2222222222
0111111111
0222222222
0122222222
0112222222
0111222222
0111122222
0111112222
0111111222
0111111122
0012222222
To już 13...a jest więcej.