Вопросы
1. Отношения порядка и эквивалентности.
2. Сочетания и размещения.
3. Упорядоченные размещения.
4. Сочетания с повторениями.
5. Число неубывающих функций между конечными линейно упорядоченными множествами.
6. Число неубывающих сюръекций между конечными линейно упорядоченными множествами.
7. Число возрастающих отображений между конечными линейно упорядоченными множествами.
8. Применение теоремы Эйлера к классификации платоновых тел.
9. Сочетания и бином Ньютона.
10. Обобщенные биноминальные коэффициенты.
11. Решение однородных линейных рекуррентных соотношений.
12. Разбиения множества и числа Стирлинга второго рода.
13. Применение эйлеровой характеристики для доказательства того, что граф K3,3 неплоский.
14. Применение эйлеровой характеристики для доказательства того, что граф K5 неплоский.
15. Число Белла.
16. Эйлерова характеристика плоских графов.
17. Принцип включения и исключения.
18. Задача о счастливых билетах.
19. Задача о встречах.
20. Производящая функция чисел Фибоначчи.
21. Теорема Эйлера о сумме валентностей вершин графа.
22. Производящая функция последовательности чисел разбиений числа.
23. Теорема о раскраске плоского графа в пять цветов.
Задачи
1. Найти все множества 
, удовлетворяющие условию 
, для некоторых 
и 
.
2. Сколько чисел из множества {1, 2, …, 2000} не делятся ни на 6, ни на 15, ни на 7?
3. Сколько подмножеств множества {1, 2, …, 1000} содержат, по крайней мере, одно число, кратное 6, и ни одного, кратного 15?
4. Найти число подмножеств множества {1, 2, …, 100}, каждое из которых либо состоит из чисел, кратных 3, либо состоит из чисел, кратных 4. Например {3, 12} и {4, 12} присутствуют среди этих множеств.
5. Сколько подмножеств множества {1, 2,…, 1000} не содержат ни одного нечетного числа, но имеют, по крайней мере, одно число, кратное 7?
6. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 2 туза, 2 короля и две дамы?
7. Найти производящую функцию последовательности an = ann, n = 0, 1, 2,…, где a > 0 – действительное число.
8. Сколько ребер в полном графе K1000?
9. Найти число сюръекций множества {1,2,3,4,5,6,7} на множество {1,2,3}.
1. Граф состоит из двух треугольников, имеющих общую вершину. Найти хроматический многочлен этого графа.
2. Решить рекуррентное соотношение un+2 – 3un+1 + 2un = 0 при начальных условиях u0 = 1, u1 =4.
3. Найти хроматическую функцию циклического графа C5.
4. Простой граф имеет 27 ребер. Две его вершины имеют степени 4, а остальные степень 3. Сколько вершин имеет данный граф?
5. Сколько разбиений множества {1,2,3,4,5,6,7} имеют в точности 4 блока?
6. Нарисовать дерево, соответствующее коду Прюфера 333221.
7.Найти производящую функцию последовательности an = (n + 1)(n + 2), n = 0,1,2,…
8. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 3 туза, 2 короля и одна дама?
9. Сколько существует чисел, состоящих из невозрастающих последовательностей цифр и содержащих все цифры, например 98777665555443221110.
10. Найти производящую функцию для последовательности чисел an = n2.
11. Сколькими способами можно представить число 320 в виде произведения четырех сомножителей? Произведения, отличающиеся перестановкой сомножителей, считать различными.
12. Нарисовать дерево, код Прюфера которого равен 555512321.
13. Найти производящую функцию последовательности an = n(n + 1).
14. Найти производящую функцию для последовательности an = exp (an), где a – фиксированное действительное число.
15. Сколькими способами можно представить число 1024 в виде произведения пяти сомножителей?
16. Сколько семизначных чисел, не начинающихся с нуля, не имеют одинаковых цифр?
17. Найти производящую функцию последовательности an = 1/(n + 1).
18. Решить линейное рекуррентное уравнение un+2 = 4un+1 –4 un, u 0 = 2, u1= 3.
19. Сколько существует позиций на шахматной доске, состоящих из двух белых и двух черных коней, двух белых и двух черных слонов и белого и черного королей?
20. Решить рекуррентное уравнение un+2 = –un+1 + 12 un, u 0 = 2, u1= 3.
21. Сколько существует сюръекций {1,2,3,4,5,6,7} ® {1,2,3,4,5}?
22. Сколько перестановок множества {1,2,3,4,5,6} оставляют неподвижным, по крайней мере, 1 элемент, равный 1, 2, или 3?
23. Найти число раскрасок вершин графа «буква A» в 7 цветов. Вершины, имеющие общее ребро, раскрашиваются в различные цвета.
24. Чему равна сумма делителей числа 300?
25. Квадрат разбит на четыре клетки. Сколькими способами можно раскрасить эти клетки так, что любые две соседние имели различные цвета?
26. Сколько подмножеств множества {1,2,…, 2000} содержат, по крайней мере, одно число, делящееся на 6, но не содержат чисел, кратных 15?
27. Сколько существует шашечных позиций, состоящих из 5 белых и 6 черных шашек?
28. 12 человек разбились на 6 групп, по 2 человека в каждой. Сколькими способами это можно сделать?
29. Сколько существует подмножеств множества {1, 2, 3,…, 2000} имеющих, по крайней мере, одно число, кратное 6 или 15?
30. Чему равна сумма делителей числа 240?
31. Пусть trace(A) обозначает след матрицы A. Доказать, что если A – матрица смежности простого графа G, то число треугольников в этом графе равно trace(A3)/6.
1. Решить рекуррентное уравнение un+2= 2un+1 – un, u0 = 1, u1 = 2.
2. Пусть A – матрица смежности простого графа (V,E). Найти число путей длины 2 между каждой парой вершин.
3. Нарисовать граф, вершинами которого являются перестановки трех элементов (i1 i2 i3). Является ли этот граф плоским?
4. Сколько существует чисел, состоящих из 5 различных цифр и не начинающихся с 0?
5. Каждый из тридцати студентов сдал, по крайней мере, один зачет. Сдали зачет по математике 26 студентов, по физике – 24, по информатике – 28. Студенты, сдавшие два предмета, сдали и третий. Сколько студентов сдали все зачеты?
6. Сколько подмножеств множества {1,2,…,1000} состоят из чисел, кратных 6, но не имеют ни одного числа, кратного 15?
7. Найти сумму всех делителей числа 288.
8. Сколько различных слов можно составить с помощью перестановок слова «литература»?
9. В урне k шаров красного, зеленого и синего цвета. Какова вероятность того, что среди них 3 шара имеют красный и 2 – синий цвет.
10. Решить рекуррентное уравнение un+2 = 10un+1 – 25un, u0 = 1, u1 = 2.