szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 lis 2016, o 21:53 
Użytkownik

Posty: 3
Lokalizacja: Polska
Cześć.

Dlaczego ilość sposobów wyboru n przedmiotów o k typach jest określona {n+k-1 \choose k-1}, a nie jako ilość multipodzbiorów {n+k-1 \choose k}? Z czego się bierze to -1 w "mianowniku"?
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 23:55 
Użytkownik
Avatar użytkownika

Posty: 1229
No dobra, będę miły i napiszę dowód.

Wybierzmy sobie dowolne k elementów ze zbioru \lbrace 1, 2, \ldots, n\rbrace (elementy mogą się powtarzać. To teraz ponumerujmy je sobie niemalejąco.

a_1\le a_2\le \ldots\le a_k. To teraz sztuczka magiczka:

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 k-elementowej ze zbioru n+k-1-elementowego. Zatem wzór wygląda tak:

{n + k - 1 \choose k}. Skąd to -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...)
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2016, o 00:06 
Użytkownik
Avatar użytkownika

Posty: 13201
Lokalizacja: Wrocław
Obrazek

Sorry za off-topic.
Góra
Kobieta Offline
PostNapisane: 3 gru 2016, o 20:24 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Kacpro napisał(a):
Dlaczego ilość sposobów wyboru n przedmiotów o k typach jest określona {n+k-1 \choose k-1}

To pomyłka, miało być {n+k-1 \choose n-1}
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2016, o 22:10 
Użytkownik
Avatar użytkownika

Posty: 1229
A jeśli tak, to wzór jest poprawny, chyba mój dowód rozwiewa wszystkie Twoje wątpliwości, nie?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Wyznaczyć jawny wzór na n-ty wyraz ciągu.  Jakubb21  2
 Wzór jawny równania rekurencyjnego  emdp  4
 Znależć wzór rekurencyjny dla ciągu ternarnego  widowisko3  1
 n jednakowych kulek znaleźć wzór rekurencyjny  lightinside  3
 Wzór jawny - zadanie 4  arek1357  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl