Глава 3. Элементы комбинаторики

39. Комбинаторика. Основные правила комбинаторики - правила суммы и произведения. Комбинаторные конфигурации – выборки. Размещения с повторениями – все выборки. Формула, пример.

40. Размещения без повторений – инъективные выборки. Формула, пример. Перестановки и их групповые свойства. Сочетания – монотонные выборки (в т.ч. инъективные сочетания без повторений). Формулы, пример.

41. Три основных свойства сочетаний. Бином Ньютона. Суммы биномиальных коэффициентов. Треугольник Паскаля. Его связь с биномиальными коэффициентами.

42. Разбиения. Числа Стирлинга 2 рода. Теорема о рекуррентной формуле. Теорема о разложении по биномиальным коэффициентам.

43. Количество всех сюрьективных выборок. Числа Стирлинга 1 рода. Связь чисел Стирлинга. Числа Белла – количество всех разбиений. Теорема о числах Белла.

44. Принцип включений и исключений. Теорема обращения. Формулы обращения для биномиальных коэффициентов. Замкнутые формулы для чисел Стирлинга (все – без доказательства, только схемы доказательств). Пример.

45. Определение рекуррентного соотношения (рекуррентной формулы). Линейные и однородные соотношения, возвратная последовательность. Характеристический многочлен. Решение рекуррентного соотношения (определение и простой пример).

46. Примеры рекуррентных соотношений: арифметическая и геометрическая прогрессии, числа Фибоначчи (задача о кроликах и о последовательностях нулей и единиц). Процесс последовательных разбиений.

47. Теорема о решении однородного линейного рекуррентного соотношения (с доказательством). Пример.

48. Решение неоднородного рекуррентного соотношения. Нахождение частного решения. Пример.

49. Определение производящей функции. Известные примеры: сумма геометрической прогрессии, бином Ньютона. Простейшие формальные операции над рядами.

50. Использование рядов для доказательства тождеств. Деление многочленов и производящие функции. Таблица производящих функций.

51. Решение рекуррентных соотношений с помощью производящих функций. Общий принцип и примеры. Производящая функция чисел Фибоначчи. Неоднородный случай.