Коэффициенты многочлена (1 + x⁴ + x⁹)²⁵: при x¹⁷ — 6900, при x¹⁸ — 300, при x¹⁹ — 0

Условие

В выражении (1 + x⁴ + x⁹)²⁵ раскрыли скобки и привели подобные слагаемые. Найдите коэффициенты при x¹⁷, x¹⁸ и x¹⁹.

Решение

Произведение 25 одинаковых скобок раскрывается так: из каждой скобки берём одно из слагаемых 1, x⁴ или x⁹ и перемножаем. Если x⁴ взято из a скобок, x⁹ — из b скобок, а 1 — из остальных 25 − a − b, получается x^4a+9b. Выбрать, из каких именно скобок что брать, можно 25!/(a!·b!·(25 − a − b)!) способами. Поэтому коэффициент при x^k равен сумме таких полиномиальных коэффициентов по всем парам (a, b) с 4a + 9b = k.

k = 17. При b = 0 нужно 4a = 17 — невозможно. При b = 1 получаем 4a = 8, a = 2. При b ≥ 2 уже 9b > 17. Единственная пара (2, 1) даёт 25!/(2!·1!·22!) = 25·24·23/2 = 6900.

k = 18. При b = 0 и b = 1 остаются 18 и 9, которые не делятся на 4. При b = 2 получаем a = 0. Коэффициент равен 25!/(0!·2!·23!) = C(25, 2) = 300.

k = 19. Остатки 19, 10 и 1 при b = 0, 1, 2 не делятся на 4, поэтому представлений нет, и коэффициент равен 0.

Ответ

При x¹⁷ — 6900, при x¹⁸ — 300, при x¹⁹ — 0.

Проверка

Программа перемножила многочлен 25 раз. Коэффициенты при x¹⁶, …, x²⁰ равны 12 650, 6900, 300, 0, 53 130. Нулевые коэффициенты среди показателей меньше 36 стоят ровно при 1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 19, 23. Это числа, которые нельзя представить в виде 4a + 9b; наибольшее из них, 23 = 4·9 − 4 − 9, совпадает с формулой Сильвестра для взаимно простых 4 и 9.

Типичные ошибки

• Брать C(25, 3) = 2300 вместо 6900: выбрав три скобки, нужно ещё решить, какая из них даст x⁹, — это множитель 3.
• Считать, что коэффициент при x¹⁹ положителен, раз 19 меньше степени многочлена 225. Значение имеет только представимость 19 в виде 4a + 9b.
• Забывать пару с a = 0, как в случае x¹⁸ = (x⁹)².

Задача по мотивам problems.ru, № 76536. Формулировка и решение — редакция damirock.com.