4.2 Понятие композиции обыкновенных производящих функций
Основы перечислительной комбиаторики
4.2 Понятие композиции обыкновенных производящих функций
модуль 4.2 шаг 5
Чему равно количество способов получить по нескольким различным предметам оценки 3, 4 и 5 так, чтобы сумма оценок была равна десяти?
Решение
Представим \(\frac{1}{1-(z^3+z^4+z^5)}\) как: \(z^3 + z^4 + z^5 + z^6 + 2z^7 + 3z^8+3z^9+...+4z^{10}+... +6z^{11}+7z^{12}+6z^{13}+3z^{14}+z^{15}\)
Ответ
4
модуль 4.2 шаг 7
Дайте комбинаторное доказательство того факта, что количество способов наклеить на бандероль марки произвольного достоинства в сумме \(n\) рублей действительно равно \(2^{n-1}\).
Решение и ответ
модуль 4.2 шаг 10
Какие из этих функций являются обыкновенными производящими функциями некоторых последовательностей неотрицательных целых чисел?
Решение и ответ
- \(e^z\)
- \(3z^5\)
- \(5/(1-z)\)
- \(3(2-z)\)
- \(1/z\)
модуль 4.2 шаг 13
На плацу стоят в одну линию *n* солдат. Дежурный офицер разбивает эту шеренгу на произвольное число непустых отрядов, а затем назначает в каждом отряде командира. Найдите производящую функцию для количества способов совершить данные комбинаторные действия.
Решение
Введем обыкновенную производящую функцию для отряда с учетом условия, что отряд не может быть пустым \(f(z)=z+2z^2+3z^3+4z^4+...+nz^n\). Здесь коэффициент \(a_n\) показывает сколькими вариантами можно назначить командира в отряде.
Вспоминая, что \(f(z)=1+z+z^2+z^3+z^4+...+z^n=\frac{1}{1-z}\) и \(f^{'}(z)=1+2z+3z^2+4z^3+...+nz^{n-1}\) преобразуем \({\displaylines} { f(z)=z+2z^2+3z^3+4z^4+...+nz^n=z(1+2z+3z^2+4z^3+...+nz^{n-1})= \\ =zf^{'}=z\left ( \frac{1}{1-z}\right)^{'}=\frac{z}{(1-z)^2} }\).
Тогда \(h(z)=\frac{1}{1-f(z)}=\frac{1}{1-\frac{z}{(1-z)^2}}=\frac{(1-z)^2}{(1-z)^2-z}.\)
Ответ
(1-z)^2/(1-3*z+z^2)
модуль 4.2 шаг 14
На вход подаётся единственное натуральное число $$n \leqslant 5000000$$. Найдите число способов совершить комбинаторные действия из предыдущей задачи. Так как оно может быть очень большим, выведите его по модулю 1000000007.
Указание: один из способов найти рекуррентное соотношение, вычисление по которому будет эффективным, состоит в том, чтобы переписать равенство для полученной производящей функции \(f(z)\) в виде \(H(z)∗f(z)=G(z)\), где \(H(z)\) и \(G(z)\) — некоторые известные многочлены, и приравнять коэффициенты при \(z^n\) в левой и правой частях этого равенства.
Sample Input:
1
2880593
Sample Output:
1
188919299
Решение и ответ
1
2
3
4
5
6
7
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', object) ** abs(n))[0, 1]
print(fib(2*int(input())) % 1000000007)