Uporządkowany podział liczby.

[Gromo]

Uporzadkowany podzial liczby \(\displaystyle{ n}\) to ciag dodatnich liczb calkowitych \(\displaystyle{ \left\langle s_1,...,s_k \right\rangle}\) takich, ze \(\displaystyle{ \sum_{i=1}^{k} s_{i} = n}\). Na przyklad, wszystkie takie podzialy liczby \(\displaystyle{ 3}\) to \(\displaystyle{ \left\langle 1 ,1,1 \right\rangle, \left\langle 1, 2 \right\rangle, \left\langle 2, 1 \right\rangle, \left\langle 3 \right\rangle}\).

Udowodnij, ze dla \(\displaystyle{ n \ge 4}\) we wszystkich uporzadkowanych podzialach \(\displaystyle{ n}\) liczba \(\displaystyle{ 3}\) wystepuje dokladnie \(\displaystyle{ n 2^{n-5}}\) razy.

Pomoc moze fakt, ze takich podzialow jest \(\displaystyle{ 2^{n-1}}\). Bylo to trescia wczesniejszego podpunktu, ktory byl latwy.
Probuje to robic przez indukcje, ale niestety srednio mam pomysl jak efektywnie pokazac zwiekszanie sie ilosci trójek w uporzadkowanych podzialach.

[adambak]

wszystkich takich krotek \(\displaystyle{ k}\)-elementowych z conajmniej jedną trójką jest \(\displaystyle{ {n-4 \choose k-2}}\), co jest raczej oczywiste

no to zliczmy takie podziały z trójką na pierwszym miejscu, potem na drugim i tak dalej aż do \(\displaystyle{ k}\)-tego miejsca.. zawsze będzie ich tyle samo i dzięki temu, że zliczamy każdy taki podział z wagą równą \(\displaystyle{ 1}\) to zliczymy wszystkie trójki we wszystkich uporządkowanych podziałach dokładnie raz.. stąd szukana liczba to: \(\displaystyle{ \sum_{k=1}^{n-2}k {n-4 \choose k-2}}\) co jak łatwo udowodnić wynosi rzeczywiście \(\displaystyle{ n2^{n-5}}\)

[Gromo]

Dzięki, już rozumiem.

[TMac]

wszystkich takich krotek \(\displaystyle{ k}\)-elementowych z conajmniej jedną trójką jest \(\displaystyle{ {n-4 \choose k-2}}\), co jest raczej oczywiste

Coś mi się nie zgadza.
Dla \(\displaystyle{ k=3}\) i \(\displaystyle{ n=6}\) mamy \(\displaystyle{ {6-4 \choose 3-2} = {2 \choose 1} = 2}\), a przecież jest więcej takich podziałów: \(\displaystyle{ \left\langle 1,2,3 \right\rangle, \left\langle 2,1,3 \right\rangle, \left\langle 1,3,2 \right\rangle, \left\langle 2,3,1 \right\rangle, \left\langle 3,1,2 \right\rangle, \left\langle 3,2,1 \right\rangle}\).

[adambak]

TMac, dziękuję za zwrócenie uwagi!
fatalny dobór słów, na szczęście mam wymówkę, choć słabą, że późna pora
oczywiście chodzi o krotki z trójką na ustalonym miejscu, no bo skoro korzystam ze znanego faktu \(\displaystyle{ {n-1 \choose k-1}}\) (ilość rozwiązań równania \(\displaystyle{ \sum_{i=1}^{k}x_i=n}\)) to to gdzie ta trójka jest ma znaczenie - wydzielam ją na któreś miejsce i patrzę na ilość rozwiązań tego samego równania tylko z \(\displaystyle{ n-3}\) oraz \(\displaystyle{ k-1}\)

a więc reszta jest ok, że to się sumuje do \(\displaystyle{ n2^{n-5}}\) to najszybciej chyba policzyć korzystając z łatwego faktu: \(\displaystyle{ \sum_{k=0}^{n} k{n \choose k}=n2^{n-1}}\)