11. Ипользование рекурентных соотношений

Если a_0, a₁, …, a_n,… -некоторые числа, то можно построить степенной ряд. Иногда удается идти обратным путем – по свойству ряда как функции от z устанавливать свойства членов последовательности.

11.1. Пусть f_n^r– число сочетаний с повторениями из n видов по r (см. задачу 8.4):

1. проверьте, что f_n¹=n, f_n⁰=1;

2. докажите, что f_n^r=f_n^r-1+ f_n-1^r;

3. пусть , докажите, что A_n(z)= A_n-1(z)/(1-z);

4. получите формулу для A_n(z), не содержащую A_i(z) при i<n. (Сравните с задачей 10.7).

11.2. (Числа Фибоначчи). Числами Фибоначчи называются члены последовательности, заданные по правилу:

B₀=B₁=1, B_n=B_n-1+B_n-2при n>=2.

Пусть

1. докажите, что F(z)=1+zF(z)+z²F(z);

2. найдите F(z);

3. воспользуйтесь разложением рациональной дроби на простейшие, разложением функции 1/(z-a) в степенной ряд и найдите B_n.

Ответ:

12. Формула включений и исключений

12.1. В группе 25 студентов. 15 занимается лыжами, 12 – коньками, а 8 – и тем и другим. Сколько студентов не занимается ни тем, ни другим.

12.2. (Обобщение). Проверьте, что если A и B- конечные множества, то . Здесь -число элементов множества A.

12.3. Из 25 человек 15 занимается футболом, 12 – волейболом и 13 – баскетболом; 12 – футболом и баскетболом, 8 занимается всеми тремя видами спорта. Сколько человек занимается хотя бы одним видом спорта?

12.4. (Обобщение). Проверьте, что если A, B, C – конечные множества, то

12.5. (Обобщение). Как будет выглядеть аналог формул из задач 12.2. 12.4. для n множеств?

Ответ:

.

Указание: Один из путей доказательства – проверить, что каждый элемент в правой части дает слагаемое 1. Для этого предположите, что, .

12.6. Сколько существует перестановок чисел 1,…, n, в которых :

1. число k расположено на k месте?

2. числа k₁ , k₂ расположены на своих местах?

3. Числа k₁ , …, k_m расположены на своих местах?

4. хотя бы одно из чисел 1,…, n расположено на своем месте?

5. ни одно из чисел 1 , …, n не расположено на своем месте (беспорядки)?

12.7. Пусть D_n – число беспорядков среди перестановок чисел 1, …, n (см. задачу 12.6 п.5). Найти. Ответ несколько неожиданный: 1/e.

13. Порядок комбинаторных задач

13.1. Докажите, что (n/z)^n/2<n!<nⁿпри n>=2.

Докажите что возрастает при изменении k от 1 до n+1 и убывает – при изменении k от n+1 до 2n+1.

13.3. Докажите, что

Эти результаты показывают, что комбинаторные величины очень быстро растут с ростом n.

Для n! известна весьма точная приближенная формула Стирлинга: , причем отношение этих величин имеет предел 1 приn. Поразительно, что здесь участвует числоp- отношение длины окружности к диаметру.

Список использованных источников

1. Виленкин И.Я. Комбинаторика. –М.:Наука, 1969. –328с.

2. Виленкин И.Я. Популярная комбинаторика. –М.:Наука, 1975.-208с.

3. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. –М.:Наука, 1977. –80с.

4. Кофман А. Введение в прикладную комбинаторику. М.:Наука, 1975. – 480с.

5. Холл М. Комбинаторика. –М.:Мир, 1970. –424с.