szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 mar 2015, o 13:35 
Użytkownik

Posty: 724
Lokalizacja: Kielce
Udowodnić, że liczba podziałów uporządkowanych liczby n na k składników jest równa {n-1 \choose k-1} oraz, że liczba wszystkich podziałów uporządkowanych liczby n na dowolną liczbę składników jest równa 2^{n-1}
Góra
Mężczyzna Offline
PostNapisane: 25 mar 2015, o 23:59 
Użytkownik

Posty: 1430
Lokalizacja: Warszawa
Podział uporządkowany można interpretować jako rozwiązanie równania x_1+x_2+\cdots+x_k=n w liczbach naturalnych dodatnich. Z problemem liczby takich rozwiązań można sobie poradzić różnie; moje ulubione podejście jest takie:

Ustawmy ciąg n nierozróżnialnych kul. Między kulami jest n-1 miejsc. Ustawiając w tych miejscach k-1 bramek, uzyskujemy właśnie uporządkowany podział (albo rozwiązanie równania). Każde rozstawienie bramek daje inny podział i każdemu podziałowi odpowiada pewne rozstawienie bramek. Podziałów jest więc tyle, na ile sposobów można ustawić bramki, i mamy, co trzeba.

Co do drugiej części, to wystarczy sobie przypomnieć, że \sum_{k=0}^n{n\choose k}=2^n.
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2015, o 11:01 
Użytkownik

Posty: 724
Lokalizacja: Kielce
Ma ktoś jeszcze jakiś pomysł na dowód 1 ?
Góra
Mężczyzna Offline
PostNapisane: 8 kwi 2015, o 21:08 
Użytkownik

Posty: 1430
Lokalizacja: Warszawa
To nie jest jedyne podejście, ale chyba najprostsze. A coś z nim nie tak?

-- 10 kwietnia 2015, 00:44 --

Niech (x_1,x_2,\ldots,x_k) będzie uporządkowanym podziałem, tj. x_1+x_2+\cdots+x_k=n. Kładziemy

y_1=x_1

y_2=x_1+x_2

\vdots

y_{k-1}=x_1+x_2+\cdots+x_{k-1}.

Wówczas \left\{ y_1,y_2,\ldots,y_{k-1}\right\} jest pewnym podzbiorem \left\{ 1,2,\ldots,n-1\right\}. Powyższe odwzorowanie zadaje bijekcję między zbiorem podziałów uporządkowanych a zbiorem k-1-elementowych podzbiorów zbioru n-elementowego (sprawdzenie pozostawiam zainteresowanym).

-- 10 kwietnia 2015, 00:46 --

Powinno być "…zbioru n-1-elementowego.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczby Stirilinga II-go rodzaju dowód na wzór jawny  bellaa87  2
 Dzileniki liczby  Consolidaa  7
 podziały liczby - zadanie 3  matinf  1
 Zbiór i liczby trzycyfrowe  Vivien  2
 liczby kombinatoryka  damcios  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl