szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 lis 2014, o 11:54 
Użytkownik

Posty: 1068
Lokalizacja: Warszawa
Cześć :)
Nie rozumiem dlaczego ilość podzbiorów k-elementowych zbioru n-elementowego z powtórzeniami wynosi:
n(n+1)...(n+k-1) / k!
W mojej opinii powinno to być:
Ponieważ mamy zbiór, w którym jest k-miejsc na elementy to każdy element wybieramy na n sposobów. Tzn. mamy n^k I to oczywiście dzielimy przez k!.
Góra
Mężczyzna Offline
PostNapisane: 21 lis 2014, o 14:37 
Użytkownik

Posty: 120
Najpierw pokażę, dlaczego Twoje rozumowanie jest złe. Weźmy zbiór \lbrace 1 \rbrace. Weźmy z niego kombinację \lbrace 1, 1\rbrace. Zgodnie z Twoim rozwiązaniem kombinacji długości 2 z powtórzeniami zbioru 1-elementowego jest \frac{1}{2!} = \frac{1}{2}. Zgodzisz się, że coś tu jest nie tak.

Teraz moje rozwiązanie: weźmy sobie dowolny zbiór N = \lbrace 1, 2, \ldots , n\rbrace wybierzmy z niego k elementów ze zwracaniem. Oznaczmy sobie zbiór tych k elementów przez K = \lbrace a_1, a_2, \ldots , a_k\rbrace. Bez straty ogólności możemy założyć, że ten zbiór jest tak ponumerowany, że jeśli i < j, to a_i \le a_j. Ustawmy sobie te elementy w takim porządku. Otrzymamy:

a_1 \le a_2 \le a_3 \le \ldots \le a_k \le n \ \ (*)

Przekształćmy (*) następująco:

a_1 < a_2 +1 < a_3 +2 < \ldots < a_i + (i-1) < \ldots < a_k + (k-1) \le n +(k-1) \ \ (**)

W ten sposób sprowadziliśmy nasz przypadek, do przypadku prostrzego. Mianowicie (**) to już dobrze nam znana kombinacja bez powtórzeń długości k ze zbioru n+k-1-elementowego, co kończy nasze zadanie.

Pozdrawiam serdecznie, w razie pytań - wal jak w dym :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilosc rozwiazan rownania - zadanie 2  kamil.jack  1
 Ilość ciągów - zależność rekurencyjna  Harry Xin  17
 Ilość liczb siedmiocyfrowych  micsko123  2
 Ilość możliwych liczb  Ziemniak1990  7
 Różnica pomiędzy wariacja i(z powtórzeniami i bez)kombinacja  pentagramsss  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl