Вторая задача.
Здесь требуется найти производящую функцию
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ] для
последовательности an,
где в пункте а)
an — это количество
способов набрать n рублей
[ПИШЕТ НА ДОСКЕ]
монетами в 1,
2 и 5 рублей.
[ПИШЕТ НА ДОСКЕ] Ну давайте подумаем, как её решать.
То есть мы хотим написать вот такую функцию:
[ПИШЕТ НА ДОСКЕ] ∑ k от 0 к бесконечности ak x в степени k, где
ak — это количество способов и представить ее в каком-нибудь удобном виде.
Давайте для начала подумаем, представим, что у нас просто,
мы хотим добрать n рублей монетами, например, в 5 рублей.
Какая вот для этого будет производящая функция?
Ясно, что все кратные, все суммы, кратные 5 рублям, можно брать одним способом.
А именно: просто взять, разбить на 5 рублей,
а другие не можем взять 0 способов.
Поэтому, если бы у нас монеты только 5 рублей,
то производящая функция выглядела так,
выглядела бы так: 1 + x в 5 + x в
10 + x в 15 + x в 20 +...
Если монеты, например, 2 рубля,
то производящая функция выглядела
бы аналогично вот так: 1 + x в квадрате + x в 4 + x в 6 + x в 8 +...
Ну и 1 рубль — это совсем просто, просто каждое количество рублей
можно одним способом представить в виде суммы, в виде набора однорублёвых монет.
Значит, производящая функция выглядела бы вот таким образом.
Ну а теперь, чтобы получить производящую функцию для последовательности ak,
мы просто возьмём и перемножим эти три производящие функции.
Значит, какой в этом смысл?
В этом смысл ровно такой, что, если мы хотим набрать n рублей, монетами в 1, 2,
5 рублей, то мы берём сколько-то единичек, сколько-то двушек, сколько-то пятерок,
и этим наборам будут соответствовать соответствующие мономы в этих рядах.
Сейчас я вот это напишу.
То есть мы хотим доказать, что вот эта производящая функция,
она равна произведению вот этих трёх, которые здесь написаны.
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ] А
именно: давайте возьмём какой-нибудь… начнём считать коэффициент при x в n.
Что это такое?
Значит, коэффициент при x в n — это мы должны взять сколько-то… какой-то элемент
x в какой-то степени отсюда, чтобы получить x в n степени.
x в какой-то степени отсюда и x в какой-то степени отсюда.
То есть он выглядит так: x в степени 2, x в степени...
простите, какой-то k1 — это мы из этой скобочки взяли,
x в степени 2 на k2 из вот этой скобки и x в
степени 5 умножить на k3 – из вот этой скобки.
При этом эти k могут быть, например, 0 или любым положительным числом.
Ну и такой набор соответствует способу набрать
k1 монет стоимостью 1 рубль,
k2 монет стоимостью 2 рубля и k3 5-рублёвых монет.
То есть каждому набору,
значит, каждому способу набрать n рублей из однорублёвых,
двухрублёвых, пятирублёвых монет соответствует свой набор вот
таких вот мономов, вот таких вот степеней x.
Ну и, значит, коэффициент при xn — это будет ровно способы,
все возможные способы набрать вот такие мономы.
И, значит, количество ak — это будет ровно количество способов,
количество способов выбрать такие мономы,
а это ровно количество способов набрать разбиение на эти монеты.
Ну и, соответственно, понятно,
что производящая функция будет равна произведению этих рядов.
Ну и для краткости их можно переписать другим образом.
Мы знаем уже, что, в прошлой лекции мы доказывали, что,
значит, нижний ряд — это ни что иное, как 1 / (1 − x).
Ну и на семинарах мы разбирали похожие задачи, что верхний ряд — это 1 /
(1 − x в 5) по аналогичным соображениям, а средний ряд — 1 / (1 − x в квадрате).
Ну и, значит, вся эта производящая функция, можно записать в упрощённом виде.
А именно, как 1 / (1 − x) * 1/ на (1 − x в
квадрате) * 1 / (1 − x в пятой).
Вот такой ответ.
Так, ну теперь пункт б), перейдём на ту доску.
Значит, пункт б) отличается только тем, что мы хотим,
значит, опять an – это количество способов набрать n монет,
n рублей монетами в
1, 2 и 5 рублей,
но, только, у нас количество пятирублёвых монет ограничено 3.
Только пятирублёвых
монет не больше 3.
Ну как это сделать?
Ну давайте напишем ту производящую функцию, которая у нас была, и подумаем,
как её исправить.
Значит, у нас была вот такая функция.
Значит, у нас были все возможные способы набрать 1 рубль монет.
Рубли монетами в 1 рубль.
Значит, все возможные способы набрать какое-то количество денег монетами
в 2 рубля, и всё это умножить на количество способов
набрать пятирублёвыми монетами.
Смотрите, раз у нас пятирублёвых монет не больше, чем 3,
это значит, что в последней скобке мы не можем брать слагаемое x в 20 степени,
потому что x в 20 степени соответствует четырём пятирублёвым монетам.
Ну и больше слагаемое логически тоже мы не можем брать.
Ну поэтому мы этот ряд просто заменяем на вот
такой: на (1 + x в 5 + x в 10 + x в 15).
И больше пятирублёвых монет мы не берём.
Ну и опять же.
У нас получается, что, если мы зафиксируем в какой-то степени x в n,
то она будет представляться, если её представить как набор
сомножителей из скобок, то это опять будет x в степени k1
* x в степени 2k2 * x в степени 5k3, но при этом k3 у нас уже будет,
в ней происходят 3, потому что у нас старше 15 степени ничего нет.
Вот таким образом, производящая функция...
давайте я перепишу,
как и в прошлом пункте в виде дробей можно в сокращённом виде записать так,
что это будет 1 / (1 − x) – это первая скобка – * 1 / (1 − x в квадрате) – это
вторая скобка – ну а третью скобку можно тоже написать в таком виде,
просто по формуле сокращённо умножения
записать как отношение (1 − x в 20) / (1 − x в 5).
Вот такой ответ.
Значит, сейчас вот мы нашли функцию для такого количества монет.
Задача решена.