Свойства производящих функций

1. Сколько делителей, включая само число и 1, имеет число 720?

2. Доказать, что "n > 0 имеют место соотношения

(1) ;

(2) .

3. Найти производящую функцию последовательности a_n = 10ⁿcos(2n).

4. Найти производящую функцию последовательности a_n = 10ⁿsin(2n).

5. Найти производящую функцию последовательности a_n = 10ⁿn.

6. Найти производящую функцию последовательности a_n = 10ⁿn.

7. Найти производящую функцию последовательности a_n = 10ⁿn(n+1).

8. Найти производящую функцию последовательности a_n = 10ⁿn².

9. Найти производящую функцию последовательности a_n = 10ⁿ/(n+1).

10. Найти производящую функцию последовательности a_n = 10ⁿ/(n+1)(n+2).

11. Доказать рекуррентное соотношение для производящих функций последовательностей n^k

12. Найти производящие функции последовательностей a_n=n^k, при k = 1,2,3,4.

Решение рекуррентных уравнений

13. u_n+2 = u_n+1 + 2u_n, u₀ = 1, u₁ = 1;

14. u_n+2 = -u_n+1 + 2u_n , u₀ = 0, u₁ = 1;

15. u_n+2 = -3u_n+1 – 2u_n , u₀ = 1, u₁ = 1;

16. u_n+2 = u_n+1 + 6u_n , u₀ = a, u₁ = b;

17. u_n+2 – 4u_n+1 – 5u_n = 0, u₀ = 8, u₁ = 10;

Ответ: u_n = 7+3ⁿ

18. u_n+3 – 3u_n+2 +u_n+1– 3u_n = 0, u₀ = 1, u₁ = 3, u₂ = 8;

Ответ: u_2n= (9×3²ⁿ+(-1)ⁿ)/10, u_2n+1= (9×3²ⁿ⁺¹+3×(-1)ⁿ)/10, n≥0.

19. u_n+3 + u_n+2 – u_n+1– u_n = 0, u₀ = 1, u₁ = 2, u₂ = 3;

Ответ: u_n=(-1)ⁿ(n-1)+2

20. u_n+2 – 4u_n+1 + 4u_n = 0, u₀ = a, u₁ = b;

21. u_n+2 = 2u_n+1 – 2u_n , u₀ = 1, u₁ = 2.

Указание: Производящая функция последовательности u_n

u(x) =

Ответ:

22. u_n+3 = 3u_n+2 – 3u_n+1+ u_n , u₀ = 1, u₁ = 3, u₂ = 3;

Указание: Искать решение в виде u_n=A+ Bn + Cn².

23. u_n+3 = – 3u_n+2 – 3u_n+1– u_n , u₀ = 0, u₁ = 1, u₂ = –2;

24. u_n+2 = u_n+1 – u_n , u₀ = 1, u₁ = 9; Ответ:

25. u_n+2 = 2u_n+1 – 4u_n , u₀ = 1, u₁ = 2; Ответ:

ТЕОРИЯ ГРАФОВ

Основатель теории графов – Леонардо Эйлер (1707 – 1783), крупнейший математик 18 века. Эйлер работал в Санкт-Петербурге в 1725-1741 годах и в 1766-1783. История теория графов хорошо описана в [16]. По теории графов рекомендуем книги [3], [5], [9], [14], [20].

Эйлеровы графы

Задача о Кенигсбергских мостах (Эйлер, 1736 год). На рисунке 4.1 слева изображена часть реки Прейгель, находящейся в Кенигсберге (ныне Калининграде). Буква Л обозначает левый берег, П – правый, А и Б – острова.

Требуется найти маршрут пешехода, проходящий через все мосты, через каждый мост пешеход должен пройти ровно один раз. Эйлер доказал, что эта задача не имеет решений.

Сначала напомним определение простого графа, приведенное в пп. 1.5. Для произвольного множества V обозначим через P₂(V) множество, состоящее из подмножеств { v₁,v₂ }Í V, каждое из которых состоит из двух не равных между собой элементов.

Определение 1. Простым (неориентированным) графом G=(V,E) называется пара, состоящая из множества V и произвольного подмножества E Í P₂(V). Элементы из V называются вершинами, а из E – ребрами.

Вершины простого графа изображаются как точки или круги, а ребра – как отрезки.

 

Рис. 4.1. Схема мостов и соответствующий ей граф

 

Обобщим определение простого графа.

Определение 2. Графом называется тройка (V, E, a), состоящая из множеств V, E и функции a: E ®P₂(V), сопоставляющей каждому eÎE неупорядоченную пару {u,v}. Элементы из E называются ребрами, элементы из V – вершинами.

Если a(e)={u,v}, то вершины u и v называются концами ребра e. В этом случае u и v называются смежными вершинами и инцидентными ребру e. Если концы ребра e равны (a(e) состоит из единственного элемента), то ребро e называется петлей.

Степенью вершины v называется число инцидентных ей ребер. Ребро, являющееся петлей, учитывается два раза. В частности, петля дает степень 2. Для графа, соответствующего схеме Кенигсбергских мостов, степени вершин равны 3, 3, 3 и 5. Путем в графе называется последовательность вершин и ребер v₀g₁v₁g₂v₂ ∙∙∙ v_n-1g_nv_n, таких что v_i и v_i+1 инцидентны ребрам g_i+1, для всех i Î{1,2, ∙ ∙ ∙, n }. Граф, допускающий путь, не содержащий кратных ребер и содержащий все ребра, называется эйлеровым. Такой путь тоже называется эйлеровым.

На рис. 4.1 справа изображен граф, ребра которого соответствуют мостам, а вершины – частям суши. Задача о Кенигсбергских мостах имеет решение тогда и только тогда, когда этот граф является эйлеровым.