Podział liczby n na k składników.

[laser15]

Udowodnić, że liczba podziałów uporządkowanych liczby n na k składników jest równa \(\displaystyle{ {n-1 \choose k-1}}\) oraz, że liczba wszystkich podziałów uporządkowanych liczby n na dowolną liczbę składników jest równa \(\displaystyle{ 2^{n-1}}\)

[Majeskas]

Podział uporządkowany można interpretować jako rozwiązanie równania \(\displaystyle{ 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 \(\displaystyle{ n}\) nierozróżnialnych kul. Między kulami jest \(\displaystyle{ n-1}\) miejsc. Ustawiając w tych miejscach \(\displaystyle{ 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 \(\displaystyle{ \sum_{k=0}^n{n\choose k}=2^n}\).

[laser15]

Ma ktoś jeszcze jakiś pomysł na dowód 1 ?

[Majeskas]

To nie jest jedyne podejście, ale chyba najprostsze. A coś z nim nie tak?

-- 10 kwietnia 2015, 00:44 --

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

\(\displaystyle{ y_1=x_1}\)

\(\displaystyle{ y_2=x_1+x_2}\)

\(\displaystyle{ \vdots}\)

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

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