2015-10-22
1322
1. Множества. Мощность множества. Операции над множествами. Комбинаторные операции. Правила суммы и правило произведения. Обобщенное правило суммы. Обобщенное правило произведения.
2. Выборка. Виды выборок. Примеры. Упорядоченные выборки. Теорема о числе упорядоченных выборок без повторений. Доказательства. Следствия.
3. Выборка. Виды выборок. Примеры. Упорядоченные выборки. Теорема о числе упорядоченных выборок с повторениями. Доказательства. Следствия.
4. Выборка. Виды выборок. Примеры. Неупорядоченные выборки. Теорема о числе неупорядоченных выборок без повторений. Доказательства. Следствия.
5. Выборка. Виды выборок. Примеры. Неупорядоченная выборка с повторениями. Теорема о числе неупорядоченных выборок без повторений. Доказательство с помощью метода отображений. Следствия. Метод Эйлера.
6. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2, 3, …, k классов, без учета их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия.
|
|
|
7. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2, 3, …, k классов, с учетом их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия.
8. Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Примеры. Сформулировать и доказать теорему о числе различных отображений N в K. Условие существования взаимно-однозначных отображений.
9. Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Примеры. Условия существования отображения N на K. Сформулировать и доказать теоремы о числе взаимно-однозначных отображений N на K.
10. Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Доказательство.
11. Принцип включения и исключения. Теорема о сумме весов элементов, не обладающих ни одним из заданных свойств. Доказательство.
12. Принцип включения и исключения. Теорема о числе элементов, обладающих в точности r-свойствами из N–множества свойств. Доказательство.
13. Задача о беспорядках. Теорема о числе беспорядков из элементов n–множества. Доказательство. Следствия.
14. Теорема о числе перестановок элементов n–множества, в которых r остаются на своих местах. Доказательство.
15. Функция Эйлера. Функция Мебиуса. Выразить функцию Эйлера через функцию Мебиуса.
16. Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.
|
|
|
17. Теорема о числе сочетаний с повторениями. Доказать с помощью получения рекуррентной формулы.
18. Теорема о числе способов выбора k-элементов, никакие два из которых не являются соседними, из n элементов, расположенных в круг. Доказать с помощью получения рекуррентной формулы.
19. Биективные отображения. Подстановки. Тип (класс) подстановки. Теорема о числе подстановок заданного типа. Доказательство.
20. Биективные отображения. Подстановки. Способы представления подстановки. Геометрический способ представления подстановки. Число бинарных деревьев с n вершинами.
21. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний без повторений.
22. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями.
23. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями и при условии, что в каждом сочетании должен присутствовать хотя бы один элемент каждого вида..
24. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для перестановок с повторениями (неограниченными).
25. Числа Стирлинга первого и второго рода. Их комбинаторный смысл. Способы вычисления.
26. Числа Моргана. Их комбинаторный смысл и связь с числами Стирлинга второго рода. Способы вычисления.
27. Числа Каталана. Их комбинаторный смысл. Способы вычисления.
28. Биноминальные и полиномиальные коэффициенты. Их комбинаторный смысл. Способы вычисления.
