Mamy alfabet który składa sie z ...

Dzezi21 · Post autor: **Dzezi21** » 10 sty 2010, o 21:09

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

Crizz · Post autor: **Crizz** » 10 sty 2010, o 21:23

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}}\).

Dzezi21 · Post autor: **Dzezi21** » 10 sty 2010, o 21:53

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 ?

Crizz · Post autor: **Crizz** » 10 sty 2010, o 23:18

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).

Dzezi21 · Post autor: **Dzezi21** » 10 sty 2010, o 23:23

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...

Crizz · Post autor: **Crizz** » 11 sty 2010, o 09:10

12 ciągów?

0000000000
1111111111
2222222222
0111111111
0222222222
0122222222
0112222222
0111222222
0111122222
0111112222
0111111222
0111111122
0012222222

To już 13...a jest więcej.