Краткое описание устройства и принципа действия счетчика;doc

Дискретная математика
Листок 5
ВШЭ, факультет математики
первый курс, четвёртый модуль
Листок можно сдавать до 24.04.2014.
1. Многочлен Чебышева Tn определяется формулойPcos(nϕ) = Tn (cosϕ).
n
Найдите выражение для производящей функции
n≥0 Tn (x)t в виде
рациональной функции от x и t.
2. Докажите, что n-й многочлен Чебышева y = Tn (x) удовлетворяет
дифференциальному уравнению второго порядка
(1 − x2 )y 00 − xy 0 + n2 y = 0.
3. Экспоненциальные производящие функции для целочисленных последовательностей называются функциями Гурвица. Докажите, что результат подстановки функции Гурвица в функцию Гурвица является
функцией Гурвица.
4. Вычислите производящую функцию от двух переменных для треугольника Моцкина.
5. Вычислите треугольник Бернулли—Эйлера по модулю 2.
Докажите, что следующие распределения кратностей по рёбрам в треугольниках Дика и Моцкина приводят к указанным последовательностям в их основаниях и найдите производящие функции от двух переменных для каждого из этих треугольников:
6. Если на восходящих ребрах в k-ой строке треугольника Дика стоит
k, а на нисходящих k + 1, то в основании треугольника стоят числа
Бернулли из треугольника Бернулли-Эйлера.
7. Если на восходящих ребрах в k-ой строке треугольника Дика стоит 1, а
на нисходящих k, то в основании треугольника стоят числа факториалы
нечетных чисел, (2n − 1)!! = 1 · 3 · (2n − 1).
8. Если на восходящих и горизонтальных ребрах в k-ой строке треугольника Моцкина стоит 1, а на нисходящих k, то в основании треугольника стоят числа In – число инволюций (перестановок, квадрат которых
есть тождественная перестановка) на множестве из n элементов, I1 = 1,
I2 = 2, I3 = 4, I4 = 10.
9. Если на восходящих и нисходящих ребрах в k-ой строке треугольника
Моцкина стоит k, а на горизонтальных 2k, то в основании треугольника
стоят числа (n + 1)!.
10. Если на восходящих и нисходящих ребрах в k-ой строке треугольника Моцкина стоит k, а на горизонтальных 2k − 1, то в основании треугольника стоят числа n!.
1