[ последовательностей ]

Одним из классических примеров использования производящих функций является задача о счастливых билетах.

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, 024321. Первая цифра номера билета может быть нулём. Известно, что количество счастливых билетов из шести цифр равно 55252. Но как это число было получено? Вообще, как решать более сложную задачу: для любого положительного целого n указать количество 2n -значных счастливых билетов?

Здесь будут рассмотрены некоторые известные методы решения данной задачи. Количество счастливых билетов из 2n цифр будем обозначать символом Ln .

Метод динамического программирования

Введём обозначение: — количество n -значных чисел с суммой цифр, равной k (число может начинаться с цифры 0). Понятно, что любой билет состоит из двух частей: левой ( n цифр) и правой (тоже n цифр), причём в обеих частях сумма цифр одинакова. Количество счастливых билетов с суммой k в одной из частей, очевидно, равно . Значит общее количество 2n -значных счастливых билетов равно

Верхний индекс суммирования равен 9n , так как максимальная сумма цифр в одной части билета равна 9n .

Теперь осталось найти все значения . Количество n -значных чисел с суммой цифр k можно выразить через количество (n-1) -значных чисел, добавляя к ним n -ю цифру, которая может быть равна 0, 1, . 9:

Здесь неявно предполагается, что для n≥0 . Положим по определению .

Вычисление значений по указанной формуле лучше представить с помощью таблицы:

Любое число в этой таблице (кроме ) получается если просуммировать 10 элементов, стоящих слева и сверху от него. Например, в таблице красным цветом выделено число 73, а серым — числа, сумме которых оно равно. Само это число 73 означает, что именно столько существует трёхзначных чисел с суммой цифр 12.

Теперь нужно просуммировать квадраты чисел, стоящих в столбце n=3 : 1 2 +3 2 +6 2 +⋅⋅⋅=55252 . Если нужно было бы подсчитать восьмизначные билеты, то потребовалось бы вычислять столбец n=4 до значения k=36 .

Метод производящих функций

Билет состоит из двух частей. Рассмотрим произвольный счастливый билет, скажем, 271334 и заменим цифры второй его части на величину, которой им не хватает до 9. То есть 271665 . Теперь сумма всех цифр билета равна 27. Легко заметить, что такой фокус проходит с любым счастливым билетом. Таким образом, количество счастливых билетов из 2n цифр равно количеству 2n -значных чисел с суммой цифр, равной 9n . То есть

Теперь можно было бы воспользоваться техникой предыдущего пункта и найти число, стоящее в столбце n=6 и в строке k=27 . Получилось бы в точности 55252 . Но здесь можно воспользоваться техникой производящих функций.

Выпишем производящую функцию G(z) , коэффициент при z k у которой будет равен :

Действительно, однозначное число с суммой цифр k (для k=0. 9 ) можно представить одним способом. Для k>9 — ноль способов.

Заметим, что если возвести функцию G в квадрат, то коэффициент при z k будет равен числу способов получить сумму k с помощью двух цифр от 0 до 9:

В общем случае, G n (z) — это производящая функция для чисел , поскольку коэффициент при z k получается перебором всех возможных комбинаций из n цифр от 0 до 9, равных в сумме k . Перепишем производящую функцию в ином виде:

В итоге, нам требуется отыскать

Для этого посмотрим, что будет получаться, если раскрывать скобки в следующем выражении (нас интересует только коэффициенты при z 27 ):

Решение путём интегрирования

Внимание, данный раздел предназначен для тех, кто знаком с курсом ТФКП.

Воспользуемся производящей функцией G(z) из предыдущего раздела:

Составим ряд Лорана следующим образом:

Значение a0 в данном разложении будет в точности равно [ проверьте ]

Интегральная теорема Коши говорит, что

где интегрирование выполняется по любой простой замкнутой кривой, охватывающей начало координат. Удобно взять , чтобы интегрировать вдоль окружности (такая замена равносильна переходу к полярным координатам):

Теперь подставим сюда H(z) :

Нетрудно видеть, что в общем случае

Отметим, что в реальности решать эту задачу путём интегрирования чрезвычайно затруднительно. На практике лучше работает метод динамического программирования.

Также в одном из упражнений будет предложено вывести формулу:

вычисление по которой представляется на сегодняшний день очень эффективным.

Рассмотрена классическая задача о подсчёте счастливых троллейбусных билетов. Приводится формула.

Задача о счастливых билетах — условное название комбинаторной задачи подсчета количества последовательностей цифр длины 6, начиная с 000000 и до 999999, у которых сумма первых трех цифр равна сумме трех последних. Система счисления при этом предполагается десятичной, то есть цифры берутся от 0 до 9. Название задачи происходит от используемого в некоторых течениях городской культуры в СССР и России термина «счастливый билет» в отношении билетов общественного транспорта с суммой первых трех цифр равной сумме трех последних цифр или аналогичными свойствами. Задача может быть решена перебором, существуют и явные формулы ее решения. Возможное обобщение задачи — решать ее при четном числе цифр 2n и в m-ичной системе счисления (m, n — натуральные числа), то есть вычислять количество последовательностей цифр длины 2n, у которых сумма первых n цифр равняется сумме n последних цифр, а сами цифры берутся от 0 до m. Разбиралась в нескольких публикациях в журнале «Квант» в 1970-х и 1980-х годах, согласно С. К. Ландо предлагалась А. А. Кирилловым на своем семинаре в МГУ в 1970-е годы.

Содержание

[править] Явные формулы решения

Методом производящих функций в книге С. К. Ландо «Производящие функции» выводится следующая формула для числа 6-значных счастливых билетов в десятичной системе счисления.

Обозначим многочлен [math]A_1(s) = 1 + s + s^2 + . + s^9[/math] . Он обладает свойством, что коэффициент при [math]s^n[/math] равен числу однозначных чисел, сумма цифр которых равна [math]n[/math] . Отсюда следует, что коэффициент при [math]s^n[/math] в многочлене [math]A_3(s) = (A_1(s))^3[/math] равен числу представлений числа [math]n[/math] в виде суммы трех цифр (принимающих значения от 0 до 9). Поэтому число счастливых 6-значных билетов в десятичной системе счисления равно сумме квадратов коэффициентов многочлена [math]A_3(s)[/math] , что дает более простой по сравнению с полным перебором способ вычисления числа счастливых билетов.

Этот результат можно привести к явным формулам, использующим интеграл от тригонометрических функций, приписываемых в книге С. Ландо математику В. Дринфельду, который получил их будучи десятиклассником. В публикациях журнала «Квант» говорится, что формулы в виде интегралов прислали в журнал читатели.

Из предыдущего результата следует, что число счастливых билетов равно свободному члену (коэффициенту [math]p_0[/math] при члене [math]s_0[/math] ) многочлена Лорана [math]A_3(s)A_3(frac<1>)[/math] . Отсюда с помощью этого многочлена Лорана и примененной к нему теоремы Коши о вычетах выводится, что число счастливых билетов равно:

[math]p_0 = frac<1> <pi>intlimits_0^ <pi>left ( frac<sin 10 x ><sin >
ight ) ^ <6>dx.[/math]

Аналогично выводится общая формула для нахождения количества [math]2n[/math] -значных счастливых билетов в [math]m[/math] -ичной системе счисления:

Также число счастливых билетов совпадает с числом целых точек, лежащих строго внутри [math]2n[/math] -мерного куба [math][0, m+1]^<2n>[/math] на проходящей через его центр гиперплоскости, перпендикулярной главной диагонали, которое называется числом Петровского (в честь академика И. Г. Петровского).

[править] Решение методом включения-исключения

Рассмотрим конечное множество [math]B[/math] , элементы которого обладают некоторыми из свойств [math]c_1, . c_r[/math] . Обозначим [math]N(c_i)[/math] — число элементов множества [math]B[/math] , обладающих свойством [math]c_i[/math] , через [math]N(c_i,c_j)[/math] — число элементов множества [math]B[/math] , обладающих свойствами [math]c_i[/math] и [math]c_j[/math] ( [math]i
e j[/math] ) и т. д. Пусть [math]|B|[/math] — общее число элементов множества [math]B[/math] .

При этих обозначениях число элементов множества [math]B[/math] , для которых не выполнено ни одно из свойств [math]c_i[/math] ( [math]i = 1, …, r[/math] ) равно (принцип включения-исключения):

[math]|B| — N(c_1) — … — N(c_r) + N(c_1, c_2) + … — N(c_1, c_2, c_2) — …[/math]

Число 10-ичных шестизначных счастливых билетов равно числу билетов с суммой цифр, равной 27 (это следует из того, что каждому счастливому билету с десятичной записью [math]a_1b_1c_1a_2b_2c_2[/math] можно взаимно-однозначно сопоставить билет с десятичной записью [math]a_1b_1c_1(9-a_2)(9-b_2)(9-c_2)[/math] , который имеет сумму цифр 27. Введем множество [math]B[/math] всех расстановок неотрицательных целых чисел с суммой 27 в шести позициях, а также определим 6 свойств [math]c_1, . c_6,[/math] где свойство [math]c_i[/math] обозначает, что число в [math]i[/math] -й позиции не меньше 10. Число способов расставить [math]p[/math] неотрицательных целых чисел с суммой [math]q[/math] выражается через число сочетаний и равно [math]C^_[/math] . Поэтому имеем [math]|B| = C^5_<32>[/math] (число способов распределить 27 в 6 позиций), [math]N(c_i) = C^5_<22>[/math] (ставим в [math]i[/math] -ю позицию число 10, а оставшуюся сумму 17 распределяем произвольно по 6 позициям), [math]N(c_i, c_j) = C^5_<12>[/math] (ставим в i-ю и j-ю позицию число 10, а оставшуюся сумму 7 распределяем произвольно по 6 позициям), [math]N(c_i,c_j,c_k)=0[/math] (общая сумма 27 меньше, чем 30).

Таким образом, по принципу включения-исключения число 6-значных 10-ичных счастливых билетов равно

[math]C_<32>^5 — 6C_<22>^5+15C_<12>^5 = 55252.[/math]

Аналогично выполняется общая формула для нахождения количества [math]2n[/math] -значных счастливых билетов в [math]m[/math] -ичной системе счисления, которое равно числу билетов с суммой цифр [math]n(m–1)[/math] :

Ее также можно вывести с помощью производящих функций.

[править] Рекуррентное соотношение

Обозначим через [math]N_n(k)[/math] количество [math]n[/math] -значных [math]m[/math] -ичных чисел ( [math]n=1, 2, 3, . [/math] ), сумма цифр каждого из которых равна [math]k[/math] . В частности, [math]N_n(k) = 0[/math] при [math]klt0[/math] и [math]kgt(m-1)n.[/math] Очевидно, [math]N_n(0) = 1[/math] .

Поскольку [math]n[/math] -значное число с суммой цифр [math]k[/math] получается из [math](n–1)[/math] -значного числа с суммой цифр [math]l[/math] (где [math]k–(m-1)≤l≤k[/math] ) путем добавления цифры [math]k–l[/math] , то:

Отсюда получается рекуррентное соотношение, с помощью которого можно последовательно вычислять числа [math]N_n(k)[/math] :

[math]N_n(k + 1) – N_n(k) = N_(k + 1) – N_(k – (m-1)).[/math]

Имеем, что число счастливых [math]2n[/math] -значных [math]m[/math] -ичных билетов [math]C_ <2n,m>= N_<2n>((m-1)n),[/math] так как оно равно числу билетов с суммой цифр [math]n(m–1).[/math]

С помощью данного рекуррентного соотношения можно дать элементарное (не использующее теорию функций комплексного переменного) доказательство формулы для числа счастливых билетов в виде интеграла.

Ответ на эту задачу нужно записать в виде пяти шестизначных чисел, каждое число
записано в одной строке, в том же порядке, как они записаны в условии (в первой строке –
ответ для первого числа, во второй строке – для второго и т. д.). Если вы не можете дать ответ
для какого-то числа, напишите вместо него любое шестизначное число.