szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 lis 2016, o 22: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"?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2016, o 00: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 01:06 
Użytkownik
Avatar użytkownika

Posty: 12428
Lokalizacja: czasem Warschau, czasem Breslau
Obrazek

Sorry za off-topic.
Góra
Kobieta Offline
PostNapisane: 3 gru 2016, o 21: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 23: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 
 Wzór Bineta - zadanie 2  myszka9  6
 Wzór jawny ciągu rekurencyjnego - zadanie 2  SRV  1
 Podaj wzór na wybranie do zbiorów  MathMaster  2
 Wzór jawny na n-ty wyraz ciągu określonego rekurencją  fryxjer  1
 Wzór An - rekurencja  robix  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl