Kombinacje z powtórzeniami - uzasadnienie wzoru

[nivwusquorum]

Witam,

Szukam jakiegoś ładnego uzasadnienia wzoru na kombinacje z powtórzeniami. Wiele razy zdarzało mi się korzystać z tego wzoru, czytałem uzasadnienie na wikipedii, ale ciągle nie mogę zrozumieć jak ten szatan działa i dlaczego działa. Podzieliłby się ktoś jakimś miłym uzasadnieniem tego wzoru, takim, że od razu widać czemu to działa?

Pozdrawiam

[Crizz]

Rozumiem, że chodzi o uzasadnienie wzoru na ilość kombinacji z powtórzeniami.

Najprostsze jest chyba takie uzasadnienie:

Dla uproszecznia przyjmijmy, że roważamy kombinacje z powtórzeniami zbioru \(\displaystyle{ \{0,1,2,...,n-1\}}\). Każdej k-elementowej kombinacji z powtórzeniami możemy przypisać bijektywnie ciąg złożony z k jedynek i n-1 zer, przy czym każda jedynka odpowiada obecności w kombinacji liczby zer występujących w ciągu przed tą jedynką. Szukana liczba jest zatem liczbą możliwości rozmieszczenia k jedynek na n+k-1 miejscach, wynosi zatem \(\displaystyle{ {n+k-1 \choose k}}\) (na mocy wzoru na liczbę kombinacji bez powtórzeń).

Najmniej jasne jest chyba wytłuszczone sformułowanie, więc może przykład.
Bierzemy zbiór \(\displaystyle{ \{0,1,2,3,4\}}\). Tutaj \(\displaystyle{ n=5}\). Zapisujemy dowolny ciąg złożony z \(\displaystyle{ k=3}\) jedynek i \(\displaystyle{ n-1=4}\) zer, np. \(\displaystyle{ (1,1,0,0,1,0,0)}\). Ten ciąg jednoznacznie wyznacza pewną kombinację 3-elementową zbioru 5-elementowego \(\displaystyle{ \{0,1,2,3,4\}}\) w następujący sposób:
-przed pierwszą jedynką jedynką jest zero zer, zatem wrzucamy zero do wyznaczanej kombinacji
-przed drugą jedynką jedynką jest zero zer, zatem wrzucamy zero do wyznaczanej kombinacji
-przed trzecią jedynką jedynką są dwa zera, zatem wrzucamy dwójkę do wyznaczanej kombinacji
Ostatecznie kombinacją, którą wyznacza podany ciąg, jest \(\displaystyle{ \{0,0,2\}}\).

[nivwusquorum]

Świetnie Bardzo fajne. Dziękówka, że Ci się chciało tyle pisać. Dużo fajniejsze niż to na wikipedii

[Matiks21]

Super dowód

[patryk007]

Dobre, zilustrowane wytłumaczenie jest na stronie 5 w (kreski z tłumaczenia Crizz należy utożsamić z zerami, a jedynki z kropkami).