Cześć :)
Nie rozumiem dlaczego ilość podzbiorów k-elementowych zbioru n-elementowego z powtórzeniami wynosi:
\(\displaystyle{ 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 \(\displaystyle{ n^k}\) I to oczywiście dzielimy przez k!.
ilość podzbiorów z powtórzeniami
ilość podzbiorów z powtórzeniami
Najpierw pokażę, dlaczego Twoje rozumowanie jest złe. Weźmy zbiór \(\displaystyle{ \lbrace 1 \rbrace}\). Weźmy z niego kombinację \(\displaystyle{ \lbrace 1, 1\rbrace}\). Zgodnie z Twoim rozwiązaniem kombinacji długości \(\displaystyle{ 2}\) z powtórzeniami zbioru \(\displaystyle{ 1}\)-elementowego jest \(\displaystyle{ \frac{1}{2!} = \frac{1}{2}}\). Zgodzisz się, że coś tu jest nie tak.
Teraz moje rozwiązanie: weźmy sobie dowolny zbiór \(\displaystyle{ N = \lbrace 1, 2, \ldots , n\rbrace}\) wybierzmy z niego \(\displaystyle{ k}\) elementów ze zwracaniem. Oznaczmy sobie zbiór tych \(\displaystyle{ k}\) elementów przez \(\displaystyle{ 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 \(\displaystyle{ i < j}\), to \(\displaystyle{ a_i \le a_j}\). Ustawmy sobie te elementy w takim porządku. Otrzymamy:
\(\displaystyle{ a_1 \le a_2 \le a_3 \le \ldots \le a_k \le n \ \ (*)}\)
Przekształćmy \(\displaystyle{ (*)}\) następująco:
\(\displaystyle{ 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 \(\displaystyle{ (**)}\) to już dobrze nam znana kombinacja bez powtórzeń długości \(\displaystyle{ k}\) ze zbioru \(\displaystyle{ n+k-1}\)-elementowego, co kończy nasze zadanie.
Pozdrawiam serdecznie, w razie pytań - wal jak w dym
Teraz moje rozwiązanie: weźmy sobie dowolny zbiór \(\displaystyle{ N = \lbrace 1, 2, \ldots , n\rbrace}\) wybierzmy z niego \(\displaystyle{ k}\) elementów ze zwracaniem. Oznaczmy sobie zbiór tych \(\displaystyle{ k}\) elementów przez \(\displaystyle{ 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 \(\displaystyle{ i < j}\), to \(\displaystyle{ a_i \le a_j}\). Ustawmy sobie te elementy w takim porządku. Otrzymamy:
\(\displaystyle{ a_1 \le a_2 \le a_3 \le \ldots \le a_k \le n \ \ (*)}\)
Przekształćmy \(\displaystyle{ (*)}\) następująco:
\(\displaystyle{ 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 \(\displaystyle{ (**)}\) to już dobrze nam znana kombinacja bez powtórzeń długości \(\displaystyle{ k}\) ze zbioru \(\displaystyle{ n+k-1}\)-elementowego, co kończy nasze zadanie.
Pozdrawiam serdecznie, w razie pytań - wal jak w dym