Задача 61511

Темы:    [ Раскладки и разбиения ] [ Правило произведения ]

Сложность: 3 Классы: 8,9,10,11

Условие

Докажите, что каждое натуральное число n может быть  2^n–1 – 1  различными способами представлено в виде суммы меньших натуральных слагаемых, если два представления, отличающихся хотя бы порядком слагаемых, считать различными.

Решение

Расположим в ряд n шаров. Если мы вставим в некоторые промежутки между шарами перегородки, то n разобьётся на некоторое число слагаемых. Поскольку мест для перегородок  n – 1,  возможностей вставить перегородки 2^n–1 (см. зад. 34931). Но этот результат учитывает также случай, когда перегородки вообще не вставляются. Этот случай по условию следует исключить.

Замечания

Ср. с задачей 30717 а.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	3
Название	Производящие функции
Тема	Производящие функции
задача
Номер	11.084