Комбинаторика 2024. Часть 1 (1)

1.

Комбинаторика
Виленкин Н.Я. Комбинаторика.
Виленкин Н.Я. Популярная комбинаторика.
Нефедов В.Н., Осипова В.А. Курс дискретной математики.
Липский В. Комбинаторика для программистов.
Андерсон Джеймс А. Дискретная математика и
комбинаторика.
1

2.

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

3.

Если X n , то объект x может быть выбран из X n способами.
Правило суммы. Если объект x может быть выбран m способами,
а объект y – другими n способами, то выбор «либо x , либо y » можно
сделать m n способами.
Правило произведения. Если объект x может быть выбран m
способами и после каждого из таких выборов объект y в свою очередь
может быть выбран n способами, то выбор упорядоченной пары x, y ,
можно сделать mn способами.
3

4.

Правило произведения. Если объект x может быть выбран n
способами и после каждого из таких выборов объект y в свою очередь
может быть выбран m способами, то выбор упорядоченной пары x, y ,
можно сделать nm способами.
Пусть объект x выбирается из множества X a1, a2 ,..., an .
Обозначим через X i – множество пар
x, y , в которых x ai .
Множества X i попарно не пересекаются и X i m i 1, n . Следовательно
n
i 1
n
n
i 1
i 1
X i X i m nm .
4

5.

Правило суммы. Если объект x может быть выбран m способами,
а объект y – другими n способами, то выбор «либо x , либо y » можно
сделать m n способами.
Следствие. Пусть X 1 , X 2 , …, X k – попарно непересекающиеся
множества, тогда
k
i 1
k
Xi Xi .
i 1
Правило произведения. Если объект x может быть выбран m
способами и после каждого из таких выборов объект y в свою очередь
может быть выбран n способами, то выбор упорядоченной пары x, y ,
можно сделать mn способами.
Следствие. Если объект x1 может быть выбран n1 способами, после
чего объект x2 в свою очередь может быть выбран n2 способами и
i 2, m 1 , после выбора объектов x1 , x2 ,..., xi объект xi 1 может быть
выбран ni 1 способами, то выбор упорядоченной последовательности из
m объектов x1 , x2 ,..., xm можно сделать n1n2 ...nm способами.
5

6.

Формула включений и исключений.
Пусть X i – конечные множества, i 1,2,..., n , n 2 . Тогда X1
X2
...
Xn
X 1 X 2 ... X n X 1 X 2 X 1 X 3 ... X 1 X n ... X n 1 X n
n 1
X 1 X 2 X 3 X 1 X 2 X 4 ... X n 2 X n 1 X n ... 1 X 1 X 2 ...
Xn
.
Докажем методом математической индукции.
1. n 2 . Если X 1
X 2 , то X1
X 2 X1 X 2 . Если X 1
X 1 X 2 каждый элемент множества X 1
X1
X 2 , то в сумме
X 2 посчитан 2 раза, а значит,
X 2 X1 X 2 X1
X2 .
6

7.

Пусть формула справедлива для n множеств. Тогда
X1
X2
X1
...
X2
Xn
X n 1 X 1
X2
X n X n 1 X 1
...
X1 X 2 ... X n X1
X1
... 1
n 1
X n 1 X 1
X1 X 2 ... X n X1
X1
X2
X 3 X1
X2
X n 1
X 3 ... X1
X 3 X1
X2
X1
X2
...
X n 1
X2
X 2 X1
... 1 X1 X 2 ... X n
X n 1 X1 X n 1 X 2 X n 1 ... X n
Xn
X n ... X n 1
X 4 ... X n 2
X n 1
Xn
Xn
X n 1 ...
X 3 ... X1
X 4 ... X n 2
X2
X n 1
Xn
...
X 2 X1
X2
Xn
...
X n 1
Xn
X n 1
X n ... X n 1
Xn
Xn
n 1
X1
X2
... 1
1
n 2
n 1
X1
X n 1 X1
X
X3
X n 1
X n 1 ... X n 1
2
X3
...
X n 1 X 1
X2
...
Xn
X n 1
X3
...
Xn
X n 1
X n 1 X 1
X 2 ...
X n 1
X n 1
7

8.

Пример
В НИИ работает несколько человек, причем все они знают
хотя бы по одному языку:
англ. – 6,
англ. и нем. – 4,
франц. – 7,
англ. и франц. – 2,
нем. – 6,
нем. и франц. – 3,
1) Сколько человек в НИИ?
все три языка – 1.
(6 + 7 + 6) – (4 + 2 + 3) + 1 = 11
2) Сколько человек знают только английский?
6 – (4 + 2) + 1 = 1
3) Сколько человек знают только французский? 7 – (2 + 3) + 1 = 3
8

9.

1. Из города A в город B ведут пять дорог, а из города B в город С – три. Сколько
путей, проходящих через B, ведут из города A в город С?
5 3
2. На вершину горы ведут 5 дорог.
1) Сколькими способами турист может подняться на гору и потом спуститься? 5 5
2) Сколькими способами турист может подняться на гору и потом спуститься,
если подъем и спуск происходят по разным дорогам? 5 4
3. В одном классе 25 учеников, а в другом 24. Сколькими способами можно выбрать:
1) одного ученика на конференцию,
2) двух учеников на олимпиаду,
25 24 49
49 48
2
3) по одному человеку из каждого класса?
25 24
4. Сколькими способами можно указать на шахматной доске 2 квадрата:
1) белый и черный,
32 32
2) произвольного цвета?
64 63
2
9

10.

Набор элементов
выборкой объема
xi1 , xi2 ,..., xim
m из n
из множества
X x1 , x2 ,..., xn
называется
элементов. Выборка называется упорядоченной
(неупорядоченной), если порядок следования элементов в ней задан (не является
существенным). В выборках могут допускаться или не допускаться повторения
элементов.
Упорядоченная выборка
Неупорядоченная выборка
Размещения без повтора
Без повторения
элементов
n!
,m n
m
An n m !
0,
m n
Перестановка Pn An n !
n
С повторением
элементов
Размещения с повтором
m
n
A n
m
Сочетания без повтора
n!
,m n
Cnm m! n m !
,
0,
m n
Сочетания с повтором
m
n
C Cnm m 1 Cnn m1 1
0
0
Замечание: В случае нулевой выборки принято, что An Cn An C n 1.
0
0
10

11.

2
5
A 5 5
1. На вершину горы ведут 5 дорог.
1) Сколькими способами турист может подняться на гору и потом спуститься?
2) Сколькими способами турист может подняться на гору и потом спуститься,
5!
2
если подъем и спуск происходят по разным дорогам?
A
5 4
5
(5 2)!
2. В одном классе 25 учеников, а в другом 24. Сколькими способами можно
выбрать:
1) двух учеников на олимпиаду,
49! 49 48
C
2!47!
2
2
49
2) 6 человек для участия в математическом бою (один из них – капитан),
3) по три человека из каждого класса для дежурства в столовой?
5
49 C48
3
3
C25
C24
3. Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут
разделить яблоки между собой, если
40
42!
40
1) все яблоки одинаковые,
C 3 C42
21 41
2!40!
2) все яблоки разные?
40
3
A 340
11

12.

Из колоды, состоящей из 52 карт, выбрали 10 карт.
Определить в скольких случаях среди них окажутся:
1) пиковая дама,
2) все четыре дамы,
3) все карты одного цвета,
4) все карты одной масти,
5) ни одного туза,
6) ровно один туз,
7) ровно два туза,
8) хотя бы один туз,
9) не менее двух тузов?
12