Число счастливых билетов, сумма первых трёх цифр которых равна n, есть a_n² (как в начале, так и в конце номера счастливого билета можно поставить любую тройку цифр с суммой n). Таким образом, для подсчёта числа счастливых билетов нам достаточно вычислить числа a_n, а затем найти сумму квадратов этих 28 чисел.

Для вычисления значений a_n посчитаем число одно- и двухзначных чисел с суммой цифр n. Для каждого n = 0, 1, 2, …,9 существует ровно одно однозначное число с суммой цифр n (запись этого числа совпадает с записью числа n). Будем описывать однозначные числа многочленом . Смысл у этого многочлена следующий: коэффициент при sⁿ в многочлене А₁ равен числу однозначных чисел, сумма цифр которых равна n. Другими словами, коэффициент при sⁿ в многочлене А₁ равен 1, если 0? n ?9, и равен 0, если n>9.

Выпишем многочлен А₂(s), описывающий двузначные числа. Коэффициент при sⁿ в многочлене А₂(s) равен числу двузначных чисел с суммой цифр n. (Мы рассматриваем и такие двузначные числа, в которых первая цифра или обе цифры могут равняться нулю). Степень многочлена А₂ равна 18 (это наибольшая возможная сумма цифр двузначного числа): .

Предложение 1. А₂(s) = (А₁(s))².

Доказательство. Произведение мономов s^k и s^m даёт вклад в коэффициент при мономе sⁿ многочлена (А₁(s))² в том и только в том случае, если n= k+m. Поэтому коэффициент при мономе sⁿ в многочлене (А₁(s))² есть в точности число способов представить число n в виде суммы n= k+m, k,m = 0, 1, ..., 9. Таким образом, многочлен в правой части равенства совпадает с многочленом А₂.

Выпишем многочлен .

Предложение 2. А₃(s) = (А₁(s))³.

Доказательство. Коэффициент при мономе sⁿ в многочлене (А₁(s))³ равен числу представлений числа n в виде суммы трёх цифр n= k+m+l, k, m , l= 0, 1, ..., 9.

Итак, задача о числе счастливых билетов свелась к следующему: надо посчитать число р₀ - сумму квадратов коэффициентов многочлена (А₁(s))³. Умножение на многочлен А₁(s) - очень простая операция. Но мы применим аппарат математического анализа.

Подставим вместо s выражение e^iц. Тогда А₃(e^iц) = (А₁(e^iц))³ будет тригонометрическим полиномом 27-й степени:

.

Воспользовавшись тем, что

, получим

Суммируя геометрическую прогрессию и пользуясь тем, что ,

получаем , откуда искомая величина равна

. (15)

Попробуем оценить значение интеграла (15). График функции на отрезке выглядит так:

В нуле функция достигает своего максимума, равного 10. Вне отрезка величина функции f не превосходит . Поэтому вклад дополнения к отрезку в интеграл (1) не превосходит р?3⁶?2100 (на самом деле он значительно меньше). Основная же составляющая интеграла (1) сосредоточена на отрезке . Для оценки вклада этого отрезка воспользуемся методом стационарной фазы. Этот метод позволяет оценить значение интеграла при t > ?. При больших значениях t величина интеграла определяется поведением функции ln f («фазы») в окрестности своей стационарной точки 0 (точки, в которой (ln f)? = 0, или, что то же самое, f ? = 0). В окрестности нуля , а .

При больших t имеем

.

Полагая t = 6 и пользуясь формулой (15), получаем приближённое равенство . Полученный результат с хорошей точностью (отклонение составляет не более 3%) приближает искомое значение.

На основании рассмотренного примера можно сделать некоторые выводы о комбинаторных задачах и методах их решения. Задачи перечислительной комбинаторики состоят в подсчёте числа объектов, принадлежащих некоторому семейству конечных множеств. У каждого множества семейства имеется свой номер (в задаче о счастливых билетах таким номером была сумма цифр трёхзначного числа).

Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема состоит в том, чтобы найти «хорошее» решение, не требующее выписывания всех элементов изучаемых множеств. Определить, что такое «хорошее» решение, довольно трудно.

При решении задач перечислительной комбинаторики очень полезно рассматривать производящие многочлены. В нашем случае пользу принёс производящий многочлен А₃. Операции с комбинаторными объектами очень естественно выражаются в терминах производящих функций. Так, переход от однозначных чисел с заданной суммой цифр к трёхзначным числам состоял просто в возведении производящего многочлена А₁ в куб. Привлечение методов из смежных областей математики (например, из анализа) позволяет по-иному взглянуть на перечислительную задачу и найти новые, зачастую неожиданные, подходы к её решению.

Библиографический список

1. Болтянский, В.Г. Теоремы и задачи комбинаторной геометрии [Текст] / В.Г. Болтянский, И.Ц. Гохберг // - М.: Наука, 1965.

2. Болтянский, В.Г. Разбиение фигур на меньшие части [Текст] / В.Г. Болтянский, И.Ц. Гохберг // - М.: Наука, 1971.

3. Калужнин, Л.А. Преобразования и перестановки [Текст] / Л.А. Калужнин, В.И. Сущанский // - М.: Наука, 1979.

4. Кофман, А. Развитие методов пересчета [Текст] / А. Кофман // Введение в прикладную комбинаторику - М.: Наука, 1975. - с. 60-73.

5. Ландо, С.К. Счастливые билеты [Текст] // Математическое просвещение, сер. 3, вып. 2. - М.: Просвещение, 1998. - с. 127-132.