Олимпиадные задачи по теме «Производящие функции» - сложность 3 с решениями
Производящие функции
Назад<img align="right" src="/storage/problem-media/115364/problem_115364_img_2.gif"> Назовём лестницей высоты <i>n</i> фигуру, состоящую из всех клеток квадрата <i>n</i>×<i>n</i>, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты <i>n</i> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?
Из первых <i>k</i> простых чисел 2, 3, 5, ..., <i>p<sub>k</sub></i> (<i>k</i> > 5) составлены всевозможные произведения, в которые каждое из чисел входит не более одного раза (например, 3·5, 3·7·... ·<i>p<sub>k</sub></i>, 11 и т. д.). Обозначим сумму всех таких чисел через <i>S</i>. Доказать, что <i>S</i> + 1 разлагается в произведение более 2<i>k</i> простых сомножителей.
День в Анчурии может быть либо ясным, когда весь день солнце, либо дождливым, когда весь день льет дождь. И если сегодня день не такой, как вчера, то анчурийцы говорят, что сегодня погода изменилась. Однажды анчурийские ученые установили, что 1 января день всегда ясный, а каждый следующий день в январе будет ясным, только если ровно год назад в этот день погода изменилась. В 2015 году январь в Анчурии был весьма разнообразным: то солнце, то дожди. В каком году погода в январе впервые будет меняться ровно так же, как в январе 2015 года?
Выведите формулу для чисел Каталана, воспользовавшись результатом задачи <a href="https://mirolimp.ru/tasks/161519">161519</a> и равенством <img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_2.gif"> где
<img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_3.gif"> – обобщенные биномиальные коэффициенты.
Определение чисел Каталана можно найти в <a href="https://problems.ru/thes.php?%20letter=23#chisla_catalana">справочнике</a>.
Вычислите, используя производящие функции, следующие суммы:
а) <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_2.gif"> б) <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_3.gif"> в) <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_4.gif"> г) <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_5.gif">
Найдите производящие функции последовательности многочленов Фибоначчи <i>F</i>(<i>x, z</i>) = <i>F</i><sub>0</sub>(<i>x</i>) + <i>F</i><sub>1</sub>(<i>x</i>)<i>z + F</i><sub>2</sub>(<i>x</i>)<i>z</i>² + ... + <i>F<sub>n</sub></i>(<i>x</i>)<i>z<sup>n</sup></i> + ...
и последовательности многочленов Люка <i>L</i>(<i>x, z</i>) = <i>L</i><sub>0</sub>(<i>x</i>) + <i>L</i><sub>1</sub>(<i>x</i>)<i>z + L</i><sub>2</sub>(<i>x</i>)<i>z</i>² + ... + <...
а) Найдите производящую функцию последовательности чисел Люка (определение чисел Люка смотри в задаче <a href="https://mirolimp.ru/tasks/160585">160585</a>)б) Пользуясь этой функцией, выразите <i>L<sub>n</sub></i> через φ и <img width="15" height="30" align="MIDDLE" border="0" src="/storage/problem-media/61504/problem_61504_img_2.gif"> (см. задачу <a href="https://mirolimp.ru/tasks/161502">161502</a>).
а) Докажите, что производящая функция последовательности чисел Фибоначчи <i>F</i>(<i>x</i>) = <i>F</i><sub>0</sub> + <i>F</i><sub>1</sub><i>x</i> + <i>F</i><sub>2</sub><i>x</i>² + ... + <i>F<sub>n</sub>x<sup>n</sup></i> + ... может быть записана в виде <img align="absmiddle" src="/storage/problem-media/61502/problem_61502_img_2.gif"> где <img width="15" height="28" align="MIDDLE" border="0" src="/storage/problem-media/61502/problem_61502_img_3.gif"> = <img width="41" height="41" align="MIDDLE" border="0" s...
Предположим, что у нас имеется 1000000 автобусных билетов с номерами от 000000 до 999999. Будем называть билет <i>счастливым</i>, если сумма первых трёх цифр его номера равна сумме трёх последних. Пусть <i>N</i> – количество счастливых билетов. Докажите равенства:
а) (1 + <i>x</i> + ... + <i>x</i><sup>9</sup>)<sup>3</sup>(1 + <i>x</i><sup>–1</sup> + ... + <i>x</i><sup>–9</sup>)<sup>3</sup> = <i>x</i><sup>27</sup> + ... + <i>a</i><sub>1</sub><i>x</i> + <i>N</i> + <i>a</i><sub>1</sub><i>x</i> + ... + <i>x</i><sup>–27</sup>;...
Пусть <i>a<sub>n</sub></i> – число решений уравнения <i>x</i><sub>1</sub> + ... + <i>x<sub>k</sub></i> = <i>n</i> в целых неотрицательных числах и <i>F</i>(<i>x</i>) – производящая функция последовательности <i>a<sub>n</sub></i>.
а) Докажите равенства: <i>F</i>(<i>x</i>) = (1 + <i>x</i> + <i>x</i>² + ...)<sup><i>k</i></sup> = (1 – <i>x</i>)<sup>–<i>k</i></sup>.
б) Найдите формулу для <i>a<sub>n</sub></i>, пользуясь задачей <a href="https://mirolimp.ru/tasks/161490">161490</a>.
Лягушка прыгает по вершинам шестиугольника <i>ABCDEF</i>, каждый раз перемещаясь в одну из соседних вершин.
а) Сколькими способами она может попасть из <i>A</i> в <i>C</i> за <i>n</i> прыжков?
б) Тот же вопрос, но при условии, что ей нельзя прыгать в <i>D</i>?
<b>Лягушка-сапер</b>.
в) Пусть путь лягушки начинается в вершине <i>A</i>, а в вершине <i>D</i> находится мина. Каждую секунду она делает очередной прыжок. Какова вероятность того, что она еще будет жива через <i>n</i> секунд?
г)* Какова средняя продолжительность жизни таких лягушек?