szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 lut 2010, o 18:55 
Użytkownik

Posty: 93
Lokalizacja: Chojnice
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
Góra
Mężczyzna Offline
PostNapisane: 22 lut 2010, o 20:38 
Gość Specjalny

Posty: 4094
Lokalizacja: Łódź
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 \{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 {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 \{0,1,2,3,4\}. Tutaj n=5. Zapisujemy dowolny ciąg złożony z k=3 jedynek i n-1=4 zer, np. (1,1,0,0,1,0,0). Ten ciąg jednoznacznie wyznacza pewną kombinację 3-elementową zbioru 5-elementowego \{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 \{0,0,2\}.
Góra
Mężczyzna Offline
PostNapisane: 22 lut 2010, o 21:05 
Użytkownik

Posty: 93
Lokalizacja: Chojnice
Świetnie :) Bardzo fajne. Dziękówka, że Ci się chciało tyle pisać. Dużo fajniejsze niż to na wikipedii :)
Góra
Mężczyzna Offline
PostNapisane: 3 mar 2015, o 21:41 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Super dowód :D
Góra
Mężczyzna Offline
PostNapisane: 16 gru 2016, o 12:27 
Użytkownik
Avatar użytkownika

Posty: 428
Dobre, zilustrowane wytłumaczenie jest na stronie 5 w dowodach kombinatorycznych (kreski z tłumaczenia Crizz należy utożsamić z zerami, a jedynki z kropkami).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podać kombinatoryczne uzasadnienie wzoru  lutzi0  1
 Kombinacje ułożenia orłów i reszek  kubaork  1
 kombinacja z powtórzeniami  duch200  2
 Pytanie o liczbe podzbiorów zbioru z powtórzeniami  anulak  1
 Wariacje z powtórzeniami i bez powtórzeń - zadania  Viola  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl