Задача 61498

Темы:    [ Производящие функции ] [ Треугольник Паскаля и бином Ньютона ] [ Классическая комбинаторика (прочее) ]

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

Условие

Предположим, что у нас имеется 1000000 автобусных билетов с номерами от 000000 до 999999. Будем называть билет счастливым, если сумма первых трёх цифр его номера равна сумме трёх последних. Пусть N – количество счастливых билетов. Докажите равенства:
  а)  (1 + x + ... + x⁹)³(1 + x^–1 + ... + x^–9)³ = x²⁷ + ... + a₁x + N + a₁x + ... + x^–27;
  б)  (1 + x + ... + x⁹)⁶ = 1 + ... + Nx²⁷ + ... + x⁵⁴.
  в) Найдите число счастливых билетов.

Решение

  а) Раскрыв скобки в произведении   (1 + ... + x⁹)(1 + ... + x⁹)(1 + ... + x⁹)(1 + ... + x^–9)(1 + ... + x^–9)(1 + ... + x^–9),  мы получим сумму выражений вида x^kx^lx^mx^–nx^–px^–q  (x^k берётся из первой скобки, x^l – из второй, и т. д.).
  Каждое решение уравнения  k + l + m – n – p – q   в "цифрах" дает единичный вклад в свободный член. А число решений этого уравнения и есть количество счастливых билетов.

  б) Достаточно умножить равенство из п. а)  на x^–27.

 в) Из п. б) следует, что N равно коэффициенту при x²⁷ у функции    Разложим функции  (1 – x¹⁰)⁶  и  (1 – x)^–-6  по степеням x:
           
Отсюда
     

Ответ

55252.

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

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