Cześć.
Dlaczego ilość sposobów wyboru \(\displaystyle{ n}\) przedmiotów o \(\displaystyle{ k}\) typach jest określona \(\displaystyle{ {n+k-1 \choose k-1}}\), a nie jako ilość multipodzbiorów \(\displaystyle{ {n+k-1 \choose k}}\)? Z czego się bierze to \(\displaystyle{ -1}\) w "mianowniku"?
Wzór na multipodzbiory
Wzór na multipodzbiory
Ostatnio zmieniony 1 gru 2016, o 13:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Powód: Używaj LaTeXa także do pojedynczych symboli.
-
jutrvy
- Użytkownik
- Posty: 1202
- Rejestracja: 24 lis 2014, o 18:04
- Płeć: Mężczyzna
- Podziękował: 10 razy
- Pomógł: 239 razy
Wzór na multipodzbiory
No dobra, będę miły i napiszę dowód.
Wybierzmy sobie dowolne \(\displaystyle{ k}\) elementów ze zbioru \(\displaystyle{ \lbrace 1, 2, \ldots, n\rbrace}\) (elementy mogą się powtarzać. To teraz ponumerujmy je sobie niemalejąco.
\(\displaystyle{ a_1\le a_2\le \ldots\le a_k}\). To teraz sztuczka magiczka:
\(\displaystyle{ a_1 < a_2 + 1 < a_3 + 2 < \ldots < a_k + (k-1)}\). Co zrobiliśmy? Sprowadziliśmy nasz problem do problemu równoważnego - wyboru kombinacji \(\displaystyle{ k}\)-elementowej ze zbioru \(\displaystyle{ n+k-1}\)-elementowego. Zatem wzór wygląda tak:
\(\displaystyle{ {n + k - 1 \choose k}}\). Skąd to \(\displaystyle{ -1}\) w mianowniku? Komuś się najwyraźniej pojebananało... (Uwaga szanowni moderatorzy - to nie jest przekleństwo, usunięcie byłoby czynem z lekka kontrowersyjnym - być może bardziej kontrowersyjne, niż umieszczenie tego nieistniejącego słowa w poście...)
Wybierzmy sobie dowolne \(\displaystyle{ k}\) elementów ze zbioru \(\displaystyle{ \lbrace 1, 2, \ldots, n\rbrace}\) (elementy mogą się powtarzać. To teraz ponumerujmy je sobie niemalejąco.
\(\displaystyle{ a_1\le a_2\le \ldots\le a_k}\). To teraz sztuczka magiczka:
\(\displaystyle{ a_1 < a_2 + 1 < a_3 + 2 < \ldots < a_k + (k-1)}\). Co zrobiliśmy? Sprowadziliśmy nasz problem do problemu równoważnego - wyboru kombinacji \(\displaystyle{ k}\)-elementowej ze zbioru \(\displaystyle{ n+k-1}\)-elementowego. Zatem wzór wygląda tak:
\(\displaystyle{ {n + k - 1 \choose k}}\). Skąd to \(\displaystyle{ -1}\) w mianowniku? Komuś się najwyraźniej pojebananało... (Uwaga szanowni moderatorzy - to nie jest przekleństwo, usunięcie byłoby czynem z lekka kontrowersyjnym - być może bardziej kontrowersyjne, niż umieszczenie tego nieistniejącego słowa w poście...)
-
kinia7
- Użytkownik
- Posty: 704
- Rejestracja: 28 lis 2012, o 11:58
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Podziękował: 89 razy
- Pomógł: 94 razy
Wzór na multipodzbiory
To pomyłka, miało być \(\displaystyle{ {n+k-1 \choose n-1}}\)Kacpro pisze:Dlaczego ilość sposobów wyboru \(\displaystyle{ n}\) przedmiotów o \(\displaystyle{ k}\) typach jest określona \(\displaystyle{ {n+k-1 \choose k-1}}\)