Счастливые билеты: 55 252 номера из миллиона и производящая функция (1 + x + … + x⁹)⁶

Условие

Номер автобусного билета состоит из шести цифр, от 000000 до 999999. Билет называют счастливым, если сумма первых трёх цифр номера равна сумме трёх последних. Сколько всего счастливых билетов? Решите задачу двумя способами: подсчётом числа способов набрать каждую сумму тремя цифрами и с помощью производящей функции.

Решение

Первый способ. Пусть N(s) — число троек цифр (a, b, c) с суммой s, где s от 0 до 27. Билет счастливый, если обе его половины имеют одну и ту же сумму s; половины выбираются независимо, поэтому счастливых билетов N(0)² + N(1)² + … + N(27)².

Число неотрицательных решений a + b + c = s без ограничений равно C(s + 2, 2). Из него нужно вычесть решения, где какая-то цифра больше 9, и по формуле включений-исключений N(s) = C(s + 2, 2) − 3·C(s − 8, 2) + 3·C(s − 18, 2) (слагаемые с отрицательным верхним числом считаются нулём). Получаем N(0), …, N(13): 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75. Замена каждой цифры d на 9 − d показывает, что N(s) = N(27 − s), так что остальные значения повторяются в обратном порядке.

Сумма квадратов для s от 0 до 13 равна 1 + 9 + 36 + 100 + 225 + 441 + 784 + 1296 + 2025 + 3025 + 3969 + 4761 + 5329 + 5625 = 27 626, а всего счастливых билетов 2·27 626 = 55 252.

Второй способ. Заменим каждую из трёх последних цифр b на 9 − b. Условие a₁ + a₂ + a₃ = b₁ + b₂ + b₃ превращается в a₁ + a₂ + a₃ + (9 − b₁) + (9 − b₂) + (9 − b₃) = 27. Значит, счастливых билетов столько же, сколько шестизначных строк цифр с суммой 27, то есть коэффициент при x²⁷ в многочлене (1 + x + … + x⁹)⁶.

Запишем (1 + x + … + x⁹)⁶ = (1 − x¹⁰)⁶·(1 − x)⁻⁶. Коэффициент при x^m во втором множителе равен C(m + 5, 5), а первый множитель раскрывается по биному: 1 − 6x¹⁰ + 15x²⁰ − … Поэтому коэффициент при x²⁷ равен C(32, 5) − 6·C(22, 5) + 15·C(12, 5) = 201 376 − 158 004 + 11 880 = 55 252.

Ответ

55 252 счастливых билета, то есть около 5,5% всех номеров.

Проверка

Прямой перебор всех миллиона номеров дал 55 252 счастливых билета. Тот же перебор дал 55 252 номера с суммой цифр 27, а перемножение многочленов — коэффициент 55 252 при x²⁷. Наибольшее значение N(s) = 75 достигается при s = 13 и s = 14.

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

Считать N(s) как C(s + 2, 2) без ограничения «цифра не больше 9». Для s ≥ 10 это завышает ответ.
Перемножать суммы вместо сложения квадратов: нужна сумма N(s)², а не (N(0) + … + N(27))² = 10⁶.
Забывать билет 000000: сумма 0 тоже даёт счастливый билет.

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