Комбинаторика и теория вероятностей

А.М. РАЙГОРОДСКИЙ

КОМБИНАТОРИКА  

И ТЕОРИЯ ВЕРОЯТНОСТЕЙ

3

А.М. Райгородский
                                                                                                                                                                                                                                                                
 Комбинаторика и теория вероятностей: Учебное пособие /
А.М. Райгородский – Долгопрудный: Издательский Дом
«Интеллект», 2013. – 104 с.

ISBN 9785915591478

Книга представляет собой учебное пособие по комбинаторике и теории
вероятностей. Она возникла на основе лекций по комбинаторике, информатике, теории вероятностей, которые ее автор в разные годы читал и продолжает читать на факультете биоинженерии и биоинформатики МГУ им.
М.В. Ломоносова, в Школе Анализа Данных Яндекса, в Московском ФизикоТехническом Институте и в совместном бакалавриате Российской Экономической Школы и Высшей Школы Экономики.
Предметы, которым посвящена книга, изложены в ней достаточно неформально, что позволяет читателю быстро понять их суть. Более детально в
книге изложены те разделы, которые редко в подробностях обсуждаются в
литературе. И наоборот, те разделы, которые легко изучать по стандартным
учебникам, в книге расписаны конспективно со ссылками на класические
источники.
Учебное пособие будет полезно студентам, начинающим специалистам и
всем, кто интересуется основами комбинаторики и вероятности.

ISBN 9785915591478
© 2013, А.М. Райгородский
© 2013, ООО Издательский Дом
«Интеллект», оригиналмакет,
оформление

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6

Глава 1. Базовые принципы комбинаторики . . . . . . . . . . . .
8

1.1. Основные правила комбинаторики . . . . . . . . . . . . . . . . .
8
1.2. Принцип Дирихле . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3. Формула включений и исключений . . . . . . . . . . . . . . . .
10
1.4. Факториал. Размещения, перестановки и сочетания. Бином
Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13

Глава 2. Числа сочетаний и простейшие тождества . . . . . .
14

2.1. Сочетания с повторениями . . . . . . . . . . . . . . . . . . . . . .
14
2.2. Полиномиальная формула . . . . . . . . . . . . . . . . . . . . . .
14
2.3. Свойства чисел сочетания: доказательство знакопостоянных
тождеств. Треугольник Паскаля. . . . . . . . . . . . . . . . . . .
15
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16

Глава 3. Еще тождества и элементы комбинаторного
анализа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17

3.1. Частный случай формулы включений и исключений. Доказательство знакопеременных тождеств . . . . . . . . . . . . . .
17
3.2. Оценки для факториалов и биномиальных коэффициентов.
Формула Стирлинга . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20

Глава 4. Обращение Мёбиуса . . . . . . . . . . . . . . . . . . . . . . .
21

4.1. Функция Мёбиуса. Формула обращения Мёбиуса . . . . . .
21

Оглавление

4.2. Применение формулы Мёбиуса для подсчета числа циклических последовательностей . . . . . . . . . . . . . . . . . . . . .
26
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30

Глава 5. Разбиения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31

5.1. Основы комбинаторики разбиений: примеры задач . . . . . .
31
5.2. Разбиение чисел на слагаемые . . . . . . . . . . . . . . . . . . .
32
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37

Глава 6. Фибоначчи и выравнивания . . . . . . . . . . . . . . . . .
38

6.1. Несколько общих слов о рекуррентных соотношениях . . .
38
6.2. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
6.3. Выравнивание последовательностей . . . . . . . . . . . . . . . .
39
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45

Глава 7. Рекурсия и степенные ряды . . . . . . . . . . . . . . . . .
46

7.1. Линейные
рекуррентные
соотношения
с
постоянными
коэффициентами . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
7.2. Степенные ряды и производящие функции . . . . . . . . . . .
48
7.3. Ряд Ньютона и числа Каталана . . . . . . . . . . . . . . . . . .
52
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52

Глава 8. Графы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53

8.1. Основы теории графов . . . . . . . . . . . . . . . . . . . . . . . . .
53
8.2. Деревья и унициклические графы . . . . . . . . . . . . . . . . .
60
8.3. Основы теории гиперграфов . . . . . . . . . . . . . . . . . . . . .
62
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64

Глава 9. Простейшие вероятностные модели . . . . . . . . . . .
67

9.1. Классическая вероятность . . . . . . . . . . . . . . . . . . . . . .
67
9.2. Схема Бернулли . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
9.3. Схема серий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70

Глава 10. Общая вероятностная модель и понятие
независимости . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71

10.1. Общее конечное вероятностное пространство . . . . . . . . .
71
10.2. Условные вероятности и независимость событий. . . . . . .
72
10.3. Несколько слов о бесконечных вероятностных пространствах
74
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75

Оглавление
5

Глава 11. Распределения. . . . . . . . . . . . . . . . . . . . . . . . . . . .
76

11.1. Случайные величины и их распределения . . . . . . . . . . .
76
11.2. Моменты распределений . . . . . . . . . . . . . . . . . . . . . . .
79
11.3. Формула обращения и предельные теоремы пуассоновского
типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
11.4. Нормальная аппроксимация. . . . . . . . . . . . . . . . . . . . .
85
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86

Глава 12. Неравенства и законы больших чисел . . . . . . . . .
87

12.1. Неравенства Чебышёва и Маркова . . . . . . . . . . . . . . . .
87
12.2. Уточнение неравенства Чебышёва в случае схемы Бернулли
88
12.3. Законы больших чисел . . . . . . . . . . . . . . . . . . . . . . . .
89
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89

Глава 13. Усиленный закон больших чисел и центральная
предельная теорема . . . . . . . . . . . . . . . . . . . . . . .
90

13.1. Виды сходимости последовательностей случайных величин
90
13.2. Неравенство Колмогорова . . . . . . . . . . . . . . . . . . . . . .
91
13.3. Усиленные законы больших чисел . . . . . . . . . . . . . . . .
91
13.4. Центральная предельная теорема . . . . . . . . . . . . . . . . .
93
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93

Глава 14. Мартингал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94

14.1. Условные вероятности и математические ожидания относительно разбиений . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
14.2. Понятие о мартингале . . . . . . . . . . . . . . . . . . . . . . . .
95
14.3. Неравенство Азумы . . . . . . . . . . . . . . . . . . . . . . . . . .
96
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

ВВЕДЕНИЕ

Настоящая книга возникла как методическое пособие к
курсам лекций, которые автор в разные годы читал и до сих пор читает
на факультете биоинженерии и биоинформатики МГУ, на факультете
инноваций и высоких технологий МФТИ, в совместном бакалавриате
Российской экономической школы и Высшей школы экономики, в Школе анализа данных Яндекса. Все эти курсы объединены наличием в
них базовой составляющей по комбинаторике и теории вероятностей.
Иными словами, в основе каждого из них лежит некоторое количество
простых понятий и фактов, которые возникают в указанных дисциплинах и без которых невозможно понимание более специфических — так
сказать, «продвинутых» — результатов.
Многие из этих фактов и понятий есть в классических учебниках и
монографиях. Однако, во-первых, они разбросаны по разным книгам, а
во-вторых, помимо них, эти книги содержат и массу другой информации. Как следствие, оказывается, что нет удобного источника, где были
бы собраны и надлежащим образом позиционированы эти и только эти
факты и понятия. По сути предлагаемая книга заполняет этот пробел.
В книге сжато, лаконично и достаточно неформально вводятся все
необходимые объекты и даются все необходимые утверждения о них.
Если доказательство теоремы имеется в стандартном учебнике (cм. [1–5]),
то, как правило, оно не воспроизводится; на него лишь ставится удобная ссылка. Зато если доказательство мало доступно или нигде популярно не изложено, то ему уделяется значительное внимание. Например, так сделано в отношении формулы обращения Мёбиуса, которую
мало где подробно обсуждают, или в отношении задач об оценках
комбинаторных величин, которые крайне важны, но обычно возникают
«сами собой» в чисто профессиональной литературе, и читатель вынужден догадываться, какие идеи за этим стоят.

Введение
7

Есть в книге и достаточно нетривиальные вещи, характерные для
курсов автора. Например, в той части, которая посвящена теории вероятностей, обсуждаются формулы обращения, позволяющие выразить
распределения дискретных величин через их моменты (это очень важно
в приложениях: например, для случайных графов), а также мартингалы (в дискретном случае) и некоторые связанные с ними неравенства
концентрации меры. Эти вещи описаны так же неформально и без чрезмерного углубления в детали, как и все остальное. Однако так и проще
не потеряться в дебрях материала.
По аналогичному принципу устроены задачи, которые предлагаются
в конце каждой темы: многие из них (хотя и не все) взяты из книг [1,6,7].
Таким образом, книга позволит четко систематизировать информацию, разбросанную по разным учебникам и задачникам (а зачастую и
просто недоступную), и даст тот ее минимум, который необходим для
адекватного восприятия курсов по комбинаторике, информатике, теории
графов, теории алгоритмов, теории вероятностей и др.

Г Л А В А
1

БАЗОВЫЕ ПРИНЦИПЫ
КОМБИНАТОРИКИ

1.1.
ОСНОВНЫЕ ПРАВИЛА КОМБИНАТОРИКИ

Правило сложения. Пусть у нас есть два типа объектов, причем объектов первого типа n штук, а объектов второго
типа m штук. Если мы хотим произвольным образом выбрать либо
объект первого типа, либо объект второго типа, то сделать мы
это можем n + m различными способами.

Правило сложения очевидно, и доказывать его не имеет смысла.
Некоторые комментарии к нему можно найти также на с. 17 книги [1].

Пример. Пусть «объекты первого типа» суть буквы русского алфавита, а «объекты второго типа» суть цифры от нуля до девяти. Тогда
понятно, что n = 33, m = 10, а число способов выбрать либо букву, либо
цифру есть в точности n + m = 43.

Правило умножения. Пусть, как и прежде, у нас есть два типа
объектов, причем объектов первого типа n штук, а объектов второго типа m штук. Если, выбирая произвольный объект A первого типа, мы вслед за ним можем выбрать произвольный объект B второго
типа, то последовательный выбор этих объектов (т. е. выбор пары (A, B) в указанном порядке) можно осуществить nm способами.

Аккуратное доказательство правила умножения приведено на с. 18
книги [1].

Пример. Пусть опять-таки «объекты первого типа» суть буквы русского алфавита, а «объекты второго типа» суть цифры от нуля до девяти. Тогда понятно, что число способов выбрать пару вида а1 или,

1.2. Принцип Дирихле
9

скажем, р7, где на первой позиции стоит буква, а на второй — цифра,
равно 33 · 10 = 330.
Правило умножения допускает очевидное обобщение на случай, когда
типов объектов не два, а сколь угодно много. В самом деле, пусть у нас
есть k типов объектов, причем объектов i-го типа ni штук, i = 1, . . . , k.
Например, n1 — это количество объектов первого типа, а nk — k-го.
Тогда число способов составить последовательность (A1, A2, . . . , Ak), у
которой на первой позиции стоит произвольный объект первого типа,
на второй — произвольный объект второго типа и т. д. вплоть до
k-й позиции, где стоит произвольный объект k-го типа, — это число
способов есть n1 · n2 · . . . · nk (см. также с. 18 в [1]).
Пример. Сколько можно составить автомобильных номеров, если
они имеют вид х486вв, т. е. на первой позиции стоит произвольная буква русского алфавита, затем следуют три произвольные цифры, а на
последних двух позициях снова стоят любые две (возможно, повторяющиеся) буквы русского алфавита? Для простоты считаем, что буквы могут действительно быть любыми и идти в произвольном порядке. Скажем, вполне возможна комбинация ы999ъй, которую реальная
ГИБДД вряд ли будет когда-либо использовать. Ответ на вопрос получается путем перемножения величин 33, 10, 10, 10, 33 и 33 и равен
333 · 1000 = 35 937 000. Здесь объекты первого, пятого и шестого типов
суть буквы, а объекты второго, третьего и четвертого типов — цифры.
Соответственно k = 6, n1 = n5 = n6 = 33, а n2 = n3 = n4 = 10.

1.2.
ПРИНЦИП ДИРИХЛЕ

Пусть у нас имеется nk + 1 объектов и k «ящиков». Тогда, как бы мы ни раскладывали наши объекты по ящикам, обязательно найдется по крайней мере один ящик, который содержит
не менее n + 1 объектов. Доказательство этого принципа очевидно,
однако он является одним из самых важных в комбинаторике и лежит в
основе многих весьма нетривиальных утверждений. В российской математической традиции иногда выражение «принцип Дирихле» заменяют
выражением «принцип ящиков», а в качестве объектов для примера рассматривают кроликов: понятно ведь, что если мы хотим расселить k + 1
кроликов по k ящикам (клеткам), то в каком-нибудь ящике непременно
окажется по меньшей мере два зверька (здесь n = 1). В западной же
традиции кроликов заменяют на голубей и принцип Дирихле называют
«pigeon-hole principle». Отметим, что, вообще-то, «pigeon-hole» — это
еще и почтовый ящик.

Гл. 1. Базовые принципы комбинаторики

1.3.
ФОРМУЛА ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ

Пусть имеется N объектов, каждый из которых может обладать или же не обладать какими-то из свойств α1, . . . , αn. Обозначим
через α′
1, . . . , α′
n отрицания свойств α1, . . . , αn соответственно. Иными
словами, смысл выражений «объект не обладает свойством αi» и «объект обладает свойством α′
i» один и тот же. Обозначим через

N(αi, αj, . . . , αk)

количество объектов, обладающих свойствами αi, αj, . . . , αk (и, возможно, еще некоторыми другими). Например, N(α1) — число объектов со
свойством α1, а N(α2, α′
3) — число объектов, заведомо имеющих свойство α2 и не имеющих свойство α3 (вопрос об остальных свойствах в
каждом из случаев остается открытым).
Теорема (формула включений и исключений). Имеет место
формула

N(α′
1, α′
2, . . . , α′
n) = N − N(α1) − N(α2) − . . . − N(αn) + N(α1, α2) +
+ N(α1, α3) + . . . + N(α1, αn) + . . . + N(αn−1, αn) − N(α1, α2, α3) − . . .
. . . − N(αn−2, αn−1, αn) + . . . + (−1)nN(α1, α2, . . . , αn).

Стандартное доказательство теоремы получается с помощью метода математической индукции, и его (а также многочисленные пояснения и примеры) можно найти на с. 24–30 книги [1]. Мы приведем
здесь иное очень изящное рассуждение.
Определение. Через N мы будем обозначать множество всех натуральных чисел: N = {1, 2, 3, . . .}. Если дано какое-то множество A,
состоящее из n объектов a1, a2, . . . , an, то его мощностью мы будем
называть количество объектов в нем, т. е. число n ∈ N. Мощность
пустого множества ∅ равна нулю. Стандартное обозначение для
мощности множества A есть |A|, т. е. у нас |A| = n.
Пусть S — это множество всех наших объектов, т. е. |S| = N. Обозначим через A1 ⊆ S, . . . , An ⊆ S — множества, состоящие из тех объектов в S, которые обладают свойствами α1, . . . , αn соответственно. Таким образом, |Ai| = N(αi) для любого i. Положим, наконец, A′
i = S \ Ai,
i = 1, . . . , n, так что |A′
i| = N(α′
i). В новых терминах нам предстоит доказать, что
A′
1 ∩A′
2 ∩. . .∩A′
n
= |S|−|A1|−|A2|−. . .−|An|+|A1 ∩A2|+|A1 ∩A3|+. . .

. . . + |A1 ∩ An| + . . . + |An−1 ∩ An| − |A1 ∩ A2 ∩ A3| − . . .
. . . − |An−2 ∩ An−1 ∩ An| + . . . + (−1)n|A1 ∩ A2 ∩ . . . ∩ An|.

1.4. Факториал. Размещения, перестановки и сочетания. Бином Ньютона
11

Пусть дано произвольное T ⊆ S. Определим функцию ϕT(x) для каждого объекта x ∈ S так: ϕT(x) = 1, если x ∈ T, и ϕT(x) = 0 в противном
случае. Эта функция называется индикаторной для множества T. Доказательство следующей простой леммы мы предоставляем читателю.
Лемма. Имеют место соотношения:
1) ϕ∅(x) = 0 и ϕS(x) = 1 для любого x ∈ S;
2) ϕT1∩T2(x) = ϕT1(x) · ϕT2(x) для любого x ∈ S;
3) ϕT ′(x) = 1 − ϕT(x), коль скоро x ∈ S, а T′ = S \ T;
4) x∈S
ϕT(x) = |T|.

Рассмотрим ϕA′
1∩A′
2∩...∩A′
n(x). По лемме

ϕA′
1∩A′
2∩...∩A′
n(x) = ϕA′
1(x) · ϕA′
2(x) · . . . · ϕA′n(x) =

= (1 − ϕA1(x)) · (1 − ϕA2(x)) · . . . · (1 − ϕAn(x)).

Раскрывая в последнем выражении скобки, применяя затем соотношения 1, 2 из леммы (с целью замены произведений индикаторов индикаторами пересечений) и суммируя, наконец, результат по x ∈ S, мы за
счет соотношения 4 получаем утверждение теоремы.

1.4.
ФАКТОРИАЛ. РАЗМЕЩЕНИЯ, ПЕРЕСТАНОВКИ
И СОЧЕТАНИЯ. БИНОМ НЬЮТОНА

Определение. Пусть n ∈ N. Тогда факториалом числа n
называется величина n!, равная произведению всех натуральных чисел от 1 до n: n! = 1 · 2 · 3 · . . . · n. Дополнительно считается, что
0! = 1.
Определение. Пусть дано множество A, состоящее из n объектов: A = {a1, a2, . . . , an}. Назовем k-сочетанием объектов из A произвольный набор таких объектов вида {ai1, ai2, . . . , aik} ⊂ A. Здесь,
во-первых, мощность k-сочетания есть k, причем все объекты, входящие в k-сочетание, принадлежат A и различны между собой, т. е.
никакие два индекса среди i1, i2, . . . , ik не совпадают, так что заведомо 0 ⩽ k ⩽ n. Во-вторых, порядок объектов в k-сочетании для
нас не важен. Например, если A — это русский алфавит, то слово
«лягушка» есть 7-сочетание {л, я, г, у, ш, к, а} (n = 33, k = 7). При
этом другие слова, получающиеся из него путем перестановки букв
(скажем, нечто вроде «ялгушка» или «гуляшка»), отождествляются с ним (задают то же самое 7-сочетание). В то же время слово
«жаба» 4-сочетанием не является, так как в нем два раза встречается одна и та же буква «а».

.

Гл. 1. Базовые принципы комбинаторики

Определение. Пусть дано множество A, состоящее из n объектов: A = {a1, a2, . . . , an}. Назовем k-размещением объектов из A
произвольный набор таких объектов вида {ai1, ai2, . . . , aik} ⊂ A. Здесь
сохраняются все условия, наложенные нами в предыдущем определении на k-сочетание, только теперь порядок объектов становится
принципиальным. Таким образом, снова 0 ⩽ k ⩽ n, «жаба» не есть
размещение (повторяется буква «а»), но 7-размещения «лягушка» и
«гуляшка» различны. Всякое n-размещение называется перестановкой. Далее, если мы отказываемся от свойства, состоящего в том,
что объекты, входящие в размещение, различны (а остальные свойства сохраняем), то мы приходим к определению k-размещения с
повторениями. Так, «жаба» уже является 4-размещением с повторениями. А 4-размещение с повторениями «абаж» с ним не совпадает.
При этом k может быть и больше n. Скажем, 40 раз повторенная
буква «а» — это 40-размещение с повторениями.

Обозначим через Ck
n число всех k-сочетаний из n объектов, через
Ak
n — число всех k-размещений, через Pn — число всех перестановок,

а через A
k
n — число всех размещений с повторениями. Заметим, что в
западной литературе для Ck
n используют иное обозначение
n
k
.

Теорема. Имеет место формула Pn = n!.

Теорема. Имеет место формула

Ak
n = n · (n − 1) · . . . · (n − k + 1) =
n!

(n − k)!.

Теорема. Имеет место формула

Ck
n =
n!

k!(n − k)! = Ak
n

k! .

Теорема. Имеет место формула A
k
n = nk.

Теоремы выполнены для всех допустимых значений натуральных
n и k. Отметим, что

C0
n = A0
n = P0 = A
0
n = 1.

Это верно и из общих соображений (пустое множество ровно одно, и
его спокойно можно считать хоть сочетанием, хоть размещением, хоть
перестановкой, хоть размещением с повторениями, ведь то, чего нет,
обладает любыми свойствами), и в силу теорем (не зря мы положили
0! = 1).

Задачи по теме
13

Подробнее ознакомиться с определениями и найти доказательства
теорем можно в [1] на с. 10–11, 32–34 и 41–44.
Из школьного курса известно, что

(x + y)2 = x2 + 2xy + y2,

а
(x + y)3 = x3 + 3x2y + 3xy2 + 1.

А как устроены коэффициенты в разложении (x + y)n? Ответ на этот
вопрос дает
Теорема (бином Ньютона). Имеет место разложение

(x+y)n = xn +C1
nxn−1y+C2
nxn−2y2 +. . .+Cn−1
n
xyn−1 +yn =
n
X

k=0
Ck
nxn−kyk.

Эта теорема доказывается на с. 192 книги [1]. В связи с ней числа
сочетания называют также биномиальными коэффициентами.

ЗАДАЧИ ПО ТЕМЕ

1. (Задачи к разд. 1.1.) №№ 1–24 из [1] и №№ 2.1–2.16 из [6].

2. (Задачи к разд. 1.2.) №№ 2.17–2.34 из [6].
В квадрат со стороной 2 случайным образом брошены 5 точек. Докажите, что среди них обязательно найдутся две, расстояние между
которыми не превосходит
√

2.

3. (Задачи к разд. 1.3.) №№ 2.96–2.110 из [6] и №№ 91, 92 из [1].

4. Задачи к разд. 1.4.) №№2.35–2.57, 2.72–2.75, 2.80 из [6] и №№34–39,
51, 55, 77–79 из [1].