Одним з класичних прикладів використання виробляють функцій є завдання про щасливих квитках.
Тролейбусний (трамвайний) квиток має номер, що складається з шести цифр. Квиток вважається щасливим, якщо сума перших трьох цифр дорівнює сумі останніх трьох, наприклад, 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).
Неважко бачити, що в загальному випадку
Відзначимо, що в реальності вирішувати цю задачу шляхом інтегрування надзвичайно важко. На практиці краще працює метод динамічного програмування.
Також в одному з вправ буде запропоновано вивести формулу:
обчислення по якій представляється на сьогоднішній день дуже ефективним.