Задача 61509

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

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

Условие

Пусть p(n) – количество разбиений числа n (определение разбиений смотри здесь). Докажите равенства:

p(0) + p(1)x + p(2)x '' + ...  =  (1 + x + x² + ...)...(1 + x^k + x^2k + ...)...  =  (1 – x)^–1(1 – x²)^–1(1 – x³)^–1...

(По определению считается, что  p(0) = 1.)

Решение

Представим n в виде суммы k₁ единиц, k₂ двоек, k₃ троек, … . Поставим в соответствие такому разбиению одночлен  xⁿ = x^k₁x^2k₂x^3k₃...,
где множитель x^k₁ берется из первой скобки, x^2k₂ – из второй, x^3k₃ – из третьей, ... . Ясно, что количество таких одночленов (коэффициент
при xⁿ после раскрытия скобок и приведения подобных) равно p(n), что и доказывает левое равенство.

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

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