4 Производящие функции

1. Найти производящую функцию A(x) для последовательности {a_n}, если:

1.1 a_n=(– 1)ⁿ,n≥ 0.

1.2 a_n=1 при ,a_n=0 при n > N.

1.3 a_n=n+1 при ,a_n=0 при n > N.

1.4 a_n=(n+1)(n+2) при ,a_n=0 при n ≥ N.

1.5 a_n=n при n ≥ 0.

1.6 a_n=n² при n ≥ 0.

1.7 a_n= nⁿ при n ≥ 0.

1.8 a_n= ⁿ/n! при n ≥ 1.

1.9 a_n= ⁿ/n!приn– нечетном,a_n=0 приn– четном.

1.10 a_n= ⁿ/n!приn–четном,a_n=0 приn– нечетном.

2. Найти экспоненциальную производящую функцию A(x) для последовательности {a_n}, если:

2.1 a_n=1. 2.2 a_n= ⁿ.

2.3 a_n= n. 2.4 a_n= n(n – 1).

2.5 a_n=n².

3. Найти общий член a_nпоследовательности, для которой функцияA(x) является производящей:

3.1 . 3.2.

3.3 . 3.4.

3.5 . 3.6.

3.7 . 3.8.

4. Пусть последовательности {a_n}, {b_n} – последовательности,b_-1=0,A(x), B(x)– соответствующие производящие функции. Показать, что:

4.1 Если a_n= b_n – b_{n – 1}, то A(x) = B(x)(1 – x).

4.2 Если a_n= b_n+1 – b_n, то A(x) = .

4.3 Если a_n= b_n+1 + b_n+2 + …, a₀ = B(1), то .

4.4 Если a_n= nb_n, то.

5. Пусть A(x), B(x) – производящие функции последовательностей {a_n}, {b_n} соответственно, и пустьA(x) B(x) = 1. Найти {b_n} иB(x) по заданной последовательности{a_n}.

Важное замечание: b_n – это коэффициенты при соответствующих степенях переменной в производящей функции B(x).

5.1 . 5.2.

5.3 a_n= n+1.5.4

5.5

6. Пусть - производящая функция для последовательности. Найдите производящие функции для последовательностей:

6.1 a₀+a₁,a₁+a₂,a₂+a₃,…6.2 a₀, a₀+a₁, a₀+a₁+a₂,…

6.3 a₀, a₁b, a₂b², a₃b³,…6.4a₀, a₂, a₄, a₆, a₈,…

7. Найти число помеченных графов с 4 вершинами и 4 ребрами.

8. Найти число бинарных деревьев порядка 5.

9. Найти число помеченных графов порядка 3.

5 Решение рекуррентных соотношений

1. Найти общее решение рекуррентных соотношений:

1.1 . 1.2.

1.3 . 1.4.

1.5 . 1.6.

1.7 . 1.8.

1.9 Найти все последовательности, удовлетворяющие условию .

2. Найти a_n, зная рекуррентное соотношение и начальные члены:

2.1 .

2.2 .

2.3 .

2.4 .

2.5 .

2.6 .

2.7 .

2.8 Найти последовательность, задаваемую соотношениями .

3. Найти такую последовательность, что и.

4. Доказать, что последовательность с общим членом удовлетворяет соотношению.

5. Найти последовательность такую, что .

6. Решите рекуррентное соотношение

Темы докладов

1. История комбинаторики в персонах и задачах (1 занятие по практике)

2. Генуэзская лотерея (1 занятие по практике)

3. Решение задачи Иосифа Флавия (1 занятие по практике)

4. Задача о счастливых билетах (3 занятие по практике)

5. Числа Каталана (3 занятие по практике)

6. Числа Фибоначчи (4 занятие по практике)

7. Специальные числа в комбинаторике: числа Эйлера, гармонические числа, числа Бернулли (5 занятие по практике)

8. Латинские прямоугольники (5 занятие по практике)

9. Магические квадраты в комбинаторике (5 занятие по практике)

Составитель: доцент каф. ВМК, к.т.н. Завьялова Е.А.