Найдите задачу для урока, кружка или самостоятельной работы.
Назовём лестницей высоты n фигуру, состоящую из всех клеток квадрата n×n, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты n на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?
а) Для каждого трёхзначного числа берём произведение его цифр, а затем эти произведения, вычисленные для всех трёхзначных чисел, складываем. Сколько получится? б) Тот же вопрос для четырёхзначных чисел.
Берутся всевозможные непустые подмножества из множества чисел 1, 2, 3, ..., n. Для каждого подмножества берётся величина, обратная к произведению всех его чисел. Найти сумму всех таких обратных величин.
Из первых k простых чисел 2, 3, 5, ..., pk (k > 5) составлены всевозможные произведения, в которые каждое из чисел входит не более одного раза (например, 3·5, 3·7·... ·pk, 11 и т. д.). Обозначим сумму всех таких чисел через S. Доказать, что S + 1 разлагается в произведение более 2k простых сомножителей.
Определить коэффициенты, которые будут стоять при x17 и x18 после раскрытия скобок и приведения подобных членов в выражении (1 + x5 + x7)20.
День в Анчурии может быть либо ясным, когда весь день солнце, либо дождливым, когда весь день льет дождь. И если сегодня день не такой, как вчера, то анчурийцы говорят, что сегодня погода изменилась. Однажды анчурийские ученые установили, что 1 января день всегда ясный, а каждый следующий день в январе будет ясным, только если ровно год назад в этот день погода изменилась. В 2015 году январь в Анчурии был весьма разнообразным: то солнце, то дожди. В каком году погода в январе впервые будет меняться ровно так же, как в январе 2015 года?
Пусть fk,l(x) – производящая функция последовательности Pk,l(n) из задачи 161525: fk,l(x) = Pk,l(0) + xPk,l(1) + ... + xklPk,l(kl). а) Докажите равенства: fk,l(x) = fk–1,l(x) + xkfk,l–1(x) = fk,l–1(x) + xlfk–1,l(x). б) Докажите, что функции fk,l(x) совпадают с многочленами Гаусса gk,l(x) (определение многочленов Гаусса смотри здесь).
Выведите формулу для чисел Каталана, воспользовавшись результатом задачи 161519 и равенством где – обобщенные биномиальные коэффициенты. Определение чисел Каталана можно найти в справочнике.
Обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) – на нечётные. Докажите равенства: а) d(0) + d(1)x + d(2)x² + ... = (1 + x)(1 + x²)(1 + x³)...; б) l(0) + l(1)x + l(2)x² + ... = (1 – x)–1(1 – x³)–1(1 – x5)–1...; в) d(n) = l(n) (n = 0, 1, 2, ...).(Считается по определению, что d(0) = l(0) = 1.)
Пусть p(n) – количество разбиений числа n (определение разбиений смотри здесь). Докажите равенства: p(0) + p(1)x + p(2)x '' + ... = (1 + x + x² + ...)...(1 + xk + x2k + ...)... = (1 – x)–1(1 – x²)–1(1 – x³)–1... (По определению считается, что p(0) = 1.)
Вычислите, используя производящие функции, следующие суммы: а) б) в) г)
Найдите производящие функции последовательностей многочленов Чебышева первого и второго рода: Определения многочленов Чебышева можно найти всправочнике.
Найдите производящие функции последовательности многочленов Фибоначчи 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 секунд? г)* Какова средняя продолжительность жизни таких лягушек?