Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 602988.02.99
Доступ онлайн
200 ₽
В корзину
Книга представляет собой учебное пособие по комбинаторике и теории вероятностей. Она возникла на основе лекций по комбинаторике, информатике, теории вероятностей, которые ее автор в разные годы читал и продолжает читать на факультете биоинженерии и биоинформатики МГУ им. М.В. Ломоносова, в Школе Анализа Данных Яндекса, в Московском Физико!Техническом Институте и в совместном бакалавриате Российской Экономической Школы и Высшей Школы Экономики. Предметы, которым посвящена книга, изложены в ней достаточно неформально, что позволяет читателю быстро понять их суть. Более детально в книге изложены те разделы, которые редко в подробностях обсуждаются в литературе. И наоборот, те разделы, которые легко изучать по стандартным учебникам, в книге расписаны конспективно - со ссылками на класические источники. Учебное пособие будет полезно студентам, начинающим специалистам и всем, кто интересуется основами комбинаторики и вероятности.
Райгородский, А. М. Комбинаторика и теория вероятностей : учебное пособие / А. М. Райгородский. - Долгопрудный : Издательский Дом «Интеллект», 2026. - 103 с. - ISBN 978-5-91559-147-8. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2241296 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
А.М. РАЙГОРОДСКИЙ
КОМБИНАТОРИКА  
И ТЕОРИЯ ВЕРОЯТНОСТЕЙ
3


А.М. Райгородский
 Комбинаторика и теория вероятностей: Учебное пособие /
А.М. Райгородский – Долгопрудный: Издательский Дом 
«Интеллект», 2026 (эл.версия). – 104 с.
ISBN 978!5!91559!147!8
Книга представляет собой учебное пособие по комбинаторике и теории
вероятностей. Она возникла на основе лекций по комбинаторике, инфор!
матике, теории вероятностей, которые ее автор в разные годы читал и про!
должает читать на факультете биоинженерии и биоинформатики МГУ им.
М.В. Ломоносова, в Школе Анализа Данных Яндекса, в Московском Физи!
ко!Техническом Институте и в совместном бакалавриате Российской Эко!
номической Школы и Высшей Школы Экономики.
Предметы, которым посвящена книга, изложены в ней достаточно нефор!
мально, что позволяет читателю быстро понять их суть. Более детально в
книге изложены те разделы, которые редко в подробностях обсуждаются в
литературе. И наоборот, те разделы, которые легко изучать по стандартным
учебникам, в книге расписаны конспективно ! со ссылками на класические
источники.
Учебное пособие будет полезно студентам, начинающим специалистам и
всем, кто интересуется основами комбинаторики и вероятности.
ISBN 978!5!91559!147!8
© 2013, А.М. Райгородский
© 2013, ООО Издательский Дом
«Интеллект», оригинал!макет,
оформление


ОГЛАВЛЕНИЕ
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 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. Применение формулы Мёбиуса для подсчета числа циклических последовательностей . . . . . . . . . . . . . . . . . . . . .
Задачи по теме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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


Оглавление
Глава 11. Распределения. . . . . . . . . . . . . . . . . . . . . . . . . . . .
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]),
то, как правило, оно не воспроизводится; на него лишь ставится удобная ссылка. Зато если доказательство мало доступно или нигде популярно не изложено, то ему уделяется значительное внимание. Например, так сделано в отношении формулы обращения Мёбиуса, которую
мало где подробно обсуждают, или в отношении задач об оценках
комбинаторных величин, которые крайне важны, но обычно возникают
«сами собой» в чисто профессиональной литературе, и читатель вынужден догадываться, какие идеи за этим стоят.


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


БАЗОВЫЕ ПРИНЦИПЫ
КОМБИНАТОРИКИ
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. Принцип Дирихле
скажем, р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. Базовые принципы комбинаторики
ФОРМУЛА ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ
Пусть имеется 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|.


Доступ онлайн
200 ₽
В корзину