Найдите задачу для урока, кружка или самостоятельной работы.
Назовём лестницей высоты n фигуру, состоящую из всех клеток квадрата n×n, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты n на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?
Из первых k простых чисел 2, 3, 5, ..., pk (k > 5) составлены всевозможные произведения, в которые каждое из чисел входит не более одного раза (например, 3·5, 3·7·... ·pk, 11 и т. д.). Обозначим сумму всех таких чисел через S. Доказать, что S + 1 разлагается в произведение более 2k простых сомножителей.
День в Анчурии может быть либо ясным, когда весь день солнце, либо дождливым, когда весь день льет дождь. И если сегодня день не такой, как вчера, то анчурийцы говорят, что сегодня погода изменилась. Однажды анчурийские ученые установили, что 1 января день всегда ясный, а каждый следующий день в январе будет ясным, только если ровно год назад в этот день погода изменилась. В 2015 году январь в Анчурии был весьма разнообразным: то солнце, то дожди. В каком году погода в январе впервые будет меняться ровно так же, как в январе 2015 года?
Выведите формулу для чисел Каталана, воспользовавшись результатом задачи 161519 и равенством где – обобщенные биномиальные коэффициенты. Определение чисел Каталана можно найти в справочнике.
Пусть – производящая функция последовательности чисел Каталана. Докажите, что она удовлетворяет равенству C(x) = xC²(x) + 1, и получите явный вид функцииC(x). Определение чисел Каталана можно найти всправочнике.
Вычислите, используя производящие функции, следующие суммы: а) б) в) г)
Найдите производящие функции последовательности многочленов Фибоначчи F(x, z) = F0(x) + F1(x)z + F2(x)z² + ... + Fn(x)zn + ... и последовательности многочленов Люка L(x, z) = L0(x) + L1(x)z + L2(x)z² + ... + Ln(x)zn + ... Определения многочленов Фибоначчи и Люка можно найти в справочнике.
а) Найдите производящую функцию последовательности чисел Люка (определение чисел Люка смотри в задаче 160585)б) Пользуясь этой функцией, выразите Ln через φ и (см. задачу 161502).
а) Докажите, что производящая функция последовательности чисел Фибоначчи F(x) = F0 + F1x + F2x² + ... + Fnxn + ... может быть записана в виде где = , = . б) Пользуясь результатом задачи 161490, получите формулу Бине (см. задачу 160578.
Предположим, что у нас имеется 1000000 автобусных билетов с номерами от 000000 до 999999. Будем называть билет счастливым, если сумма первых трёх цифр его номера равна сумме трёх последних. Пусть N – количество счастливых билетов. Докажите равенства: а) (1 + x + ... + x9)3(1 + x–1 + ... + x–9)3 = x27 + ... + a1x + N + a1x + ... + x–27; б) (1 + x + ... + x9)6 = 1 + ... + Nx27 + ... + x54. в) Найдите число счастливых билетов.
Пусть an – число решений уравнения x1 + ... + xk = n в целых неотрицательных числах и F(x) – производящая функция последовательности an. а) Докажите равенства: F(x) = (1 + x + x² + ...)k = (1 – x)–k. б) Найдите формулу для an, пользуясь задачей 161490.
Лягушка прыгает по вершинам шестиугольника ABCDEF, каждый раз перемещаясь в одну из соседних вершин. а) Сколькими способами она может попасть из A в C за n прыжков? б) Тот же вопрос, но при условии, что ей нельзя прыгать в D? Лягушка-сапер. в) Пусть путь лягушки начинается в вершине A, а в вершине D находится мина. Каждую секунду она делает очередной прыжок. Какова вероятность того, что она еще будет жива через n секунд? г)* Какова средняя продолжительность жизни таких лягушек?