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!.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
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 
 szuflady ołówki długopisy wariacja z powtórzeniami  wielkireturner  1
 Interpretacja kombinacji z powtórzeniami i bez powtórzeń  Browning0  1
 Ilość tablic rejestracyjnych z 4 literami i 3 cyframi  kombajnik  2
 liczba podzbiorów - zadanie 5  JakubCh  1
 Ilość meczy każdy z każdym -> harmonogramy rozgrywek  puyo  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl