Связь комбинаторики с различными разделами математики (стр. 7 из 7)
Выпишем многочлен А2(s), описывающий двузначные числа. Коэффициент приsn в многочленеА2(s) равен числу двузначных чисел с суммой цифр n. (Мы рассматриваем и такие двузначные числа, в которых первая цифра или обе цифры могут равняться нулю). Степень многочлена А2 равна 18 (это наибольшая возможная сумма цифр двузначного числа):
.Предложение 1. А2(s) = (А1(s))2.
Доказательство. Произведение мономов skи smдаёт вклад в коэффициент при мономе sn многочлена (А1(s))2 в том и только в том случае, если n= k+m. Поэтому коэффициент при мономе sn в многочлене (А1(s))2 есть в точности число способов представить число n в виде суммы n= k+m, k,m = 0, 1, ..., 9. Таким образом, многочлен в правой части равенства совпадает с многочленом А2.
Выпишем многочлен
.Предложение 2. А3(s) = (А1(s))3.
Доказательство. Коэффициент при мономе sn в многочлене (А1(s))3 равен числу представлений числа n в виде суммы трёх цифр n= k+m+l, k, m , l= 0, 1, ..., 9.
Итак, задача о числе счастливых билетов свелась к следующему: надо посчитать число р0 – сумму квадратов коэффициентов многочлена (А1(s))3. Умножение на многочлен А1(s) – очень простая операция. Но мы применим аппарат математического анализа.
Подставим вместо s выражение eiφ. Тогда А3(eiφ) = (А1(eiφ))3 будет тригонометрическим полиномом 27-й степени:
.Воспользовавшись тем, что
, получим 
Суммируя геометрическую прогрессию и пользуясь тем, что
,получаем
, откуда искомая величина равна 
. (15)Попробуем оценить значение интеграла (15). График функции
на отрезке 
выглядит так: 
В нуле функция достигает своего максимума, равного 10. Вне отрезка
величина функции f не превосходит 
. Поэтому вклад дополнения к отрезку в интеграл (1) не превосходит π∙36≈2100 (на самом деле он значительно меньше). Основная же составляющая интеграла (1) сосредоточена на отрезке . Для оценки вклада этого отрезка воспользуемся методом стационарной фазы. Этот метод позволяет оценить значение интеграла 
при t → ∞. При больших значениях t величина интеграла определяется поведением функции lnf(«фазы») в окрестности своей стационарной точки 0 (точки, в которой (lnf)′ = 0, или, что то же самое, f ′ = 0). В окрестности нуля 
, а 
.При больших t имеем
.Полагая t = 6 и пользуясь формулой (15), получаем приближённое равенство
. Полученный результат с хорошей точностью (отклонение составляет не более 3%) приближает искомое значение.На основании рассмотренного примера можно сделать некоторые выводы о комбинаторных задачах и методах их решения. Задачи перечислительной комбинаторики состоят в подсчёте числа объектов, принадлежащих некоторому семейству конечных множеств. У каждого множества семейства имеется свой номер (в задаче о счастливых билетах таким номером была сумма цифр трёхзначного числа).
Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема состоит в том, чтобы найти «хорошее» решение, не требующее выписывания всех элементов изучаемых множеств. Определить, что такое «хорошее» решение, довольно трудно.
При решении задач перечислительной комбинаторики очень полезно рассматривать производящие многочлены. В нашем случае пользу принёс производящий многочлен А3. Операции с комбинаторными объектами очень естественно выражаются в терминах производящих функций. Так, переход от однозначных чисел с заданной суммой цифр к трёхзначным числам состоял просто в возведении производящего многочлена А1 в куб. Привлечение методов из смежных областей математики (например, из анализа) позволяет по-иному взглянуть на перечислительную задачу и найти новые, зачастую неожиданные, подходы к её решению.
Библиографический список
1. Болтянский, В.Г. Теоремы и задачи комбинаторной геометрии [Текст] / В.Г. Болтянский, И.Ц. Гохберг // – М.: Наука, 1965.
2. Болтянский, В.Г. Разбиение фигур на меньшие части [Текст] / В.Г. Болтянский, И.Ц. Гохберг // – М.: Наука, 1971.
3. Калужнин, Л.А. Преобразования и перестановки [Текст] / Л.А. Калужнин, В.И. Сущанский // – М.: Наука, 1979.
4. Кофман, А. Развитие методов пересчета [Текст] / А. Кофман // Введение в прикладную комбинаторику – М.: Наука, 1975. – с. 60–73.
5. Ландо, С.К. Счастливые билеты [Текст] // Математическое просвещение, сер. 3, вып. 2. – М.: Просвещение, 1998. – с. 127–132.