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

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

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

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

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|.