Деление не поровну

[gegmopo4]

Задачка для дошкольников: Разделить семь яблок на три разные кучки.

Comments

[_winnie]

пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
вычтем из упорядоченных слагаемых 1, 2, 3, 4 ... m
получим набор m положительных чисел, сумма которых равна n - (1+2+...+m)
поэтому кол-во разложений на разные слагаемые - равно количеству разложений на любые слагаемые, без ограничения на разноту, числа n - m(m+1)/2

[gegmopo4]

Не понял, какое это имеет отношение.

[_winnie]

Производящие функции или эквивалентность двух формулировок?

[gegmopo4]

Какое отношение имеют эти рассуждения к задаче? 6 можно представить и как 4 + 2, но разбиение (0 + 1) + (0 + 2) + (4 + 3) + (2 + 4) = 1 + 2 + 7 + 6 получается то же, что и при разложении 6 на 3 + 3. Я что-то по-видимому не понимаю?

[_winnie]

А ты представь не как 4+2, а как 2+4. 0+0+2+4. Соответствующее разбиение будет 1+2+5+8 = 16.

пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
.....
Запишем как 4 возрастающих слагаемых с нулями впереди:

[gegmopo4]

Не пойму, как это приближает к решению задачи.

[_winnie]

После нахождения эквивалентности можно набрать в гугле "Number of partitions of n into at most k parts"