Podział liczby

[cis123]

Dla ustalonego podziału \(\displaystyle{ \pi}\) liczby \(\displaystyle{ n}\), niech \(\displaystyle{ A(\pi)}\) oznacza liczbę jedynek w \(\displaystyle{ \pi}\), zaś \(\displaystyle{ B(\pi)}\) - liczbę różnych składników w \(\displaystyle{ \pi}\).
Przykład: dla podziału \(\displaystyle{ \pi: 1 + 1 + 2 + 2 + 2 + 4}\) mamy \(\displaystyle{ A(\pi) = 2}\) oraz \(\displaystyle{ B(\pi) = 3}\).
Udowodnij, że \(\displaystyle{ \sum_{\pi}^{} A(\pi) = \sum_{\pi}^{} B(\pi)}\), gdzie sumowanie odbywa się po wszystkich podziałach ustalonej liczby n.

Wskazówka: Spróbuj wyrazić każdą ze stron tożsamości przez \(\displaystyle{ P(1), P(2), ..., P(n-1)}\), gdzie \(\displaystyle{ P(k)}\) to łączna liczba podziałów liczby k.


Pomoże ktoś?

[Mruczek]

Interpretacja kombinatoryczna:
Pokażemy, że \(\displaystyle{ \sum_{\pi}^{} A(\pi) = \sum_{i = 0}^{n - 1} P(i)}\).
Sortujemy podziały rosnąco (tak żeby kolejne składniki podziału były ustalone w porządku niemalejącym). Taki podział może zaczynać się od pewnej liczby jedynek. Jeżeli na \(\displaystyle{ i}\)-tej pozycji w takim podziale jest \(\displaystyle{ 1}\), to wcześniej też są same \(\displaystyle{ 1}\). Suma składników występujących po tej jedynce to \(\displaystyle{ n - i}\). Zliczamy dla każdej pozycji \(\displaystyle{ i}\) w ilu podziałach na \(\displaystyle{ i}\)-tej pozycji występuje jedynka. Takich podziałów jest tyle co podziałów liczby po tej jedynce, czyli \(\displaystyle{ P(n - i)}\).

Pokażemy, że \(\displaystyle{ \sum_{\pi}^{} B(\pi) = \sum_{i = 0}^{n - 1} P(i)}\).
Zliczamy osobno dla każdej liczby w ilu podziałach występuje. Bierzemy dowolną liczbę \(\displaystyle{ i}\) występującą w podziale. Reszta tego podziału to \(\displaystyle{ n - i}\). Dlatego liczba podziałów, w których występuje ta liczba to \(\displaystyle{ P(n - i)}\). Sumujemy po \(\displaystyle{ i}\) i dostajemy to co chcemy.

[Mruczek]

To jest zadanie nr 5 z USAMO 1986:

Kod: Zaznacz cały

https://artofproblemsolving.com/community/c6h424771p2403884

-- 20 sierpnia 2017, 19:44 --Poza tym to zadanie było na egzaminie poprawkowym z MD dla informatyki MIMUW w 2016 r. jako zadanie nr 2:
[url]http://wakacjezmd.github.io/2016/egzamin/2/[/url]
[url]http://i.imgur.com/wXxtskpg.jpg[/url]