Лекция 4. Рекуррентные соотношения

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

В плане производящих функций - самое главное - это понять взаимосвязь коэффициентов в многочлене и количества решений какой-то задачи. Тут есть два классических примера в духе: "Пользуясь свойствами многочлена (1+x)(1+x^2)...(1+x^(2^n)) доказать, что каждое натуральное число представимо в двоичном виде единственным образом", "Почему коэффициент перед x^20 в многочлене (1+x+x^2+...)(1+x^2+x^4+...)(1+x^5+x^10+...) равен количеству способов разменять 20 рублей используя монетки достоинством в 1, 2 и 5 рублей". Подумай, посиди, в ручную частично пораскрывай. Дойдешь в итоге.

В плане свойств рекуррентных соотношений можешь просто открыть главу в Афутовой про последовательности (там все эти свойства доказываются в виде задач), если хочешь посмотреть на примеры в которых рекурренты применяются для решения комбинаторных задач, то можешь глянуть ролик: https://www.youtube.com/watch?v=nv9cyjkER6s&t=3s.

Ну и накидаю основные книги, которые могут помочь:

0) Статья в кванте (http://kvant.mccme.ru/1984/05/metod_proizvodyashchih_funkcij.htm)

1) Виленкин (да, тебе не помогло, но другим может помочь) (https://math.ru/lib/363)

2) Алфутова (глава про последовательности) (https://mccme.ru/free-books/pdf/alfutova.pdf)

3) Кнут "Конкретная математика" (https://notendur.hi.is/pgg/(ebook-pdf)%20-%20Mathematics%20-%20Concrete%20Mathematics.pdf)

4) Ландо "Производящие функции" (https://mccme.ru/free-books/lando/lando-genfunc.pdf)

5) Лекций на ютубе по этой теме полно, вот например от CS центра СПб (https://www.youtube.com/watch?v=PtJ762ospVU)

Источник: www.youtube.com

Комментарии: