Вероятность в теоремах и задачах (с доказательствами и решениями). Книга 1

А. Н. Ширяев, И. Г. Эрлих
П. А. Яськов

Вероятность в теоремах
и задачах
(с доказательствами
и решениями)
Книга 1

МЦНМО

А. Н. Ширяев, И. Г. Эрлих, П. А. Яськов

Вероятность в теоремах и задачах

(с доказательствами и решениями)

Книга 1

Электронное издание

Москва
Издательство МЦНМО
2014

УДК 519.21(075.8)
ББК 22.171
Ш64

Ширяев А. Н., Эрлих И. Г., Яськов П. А.
Вероятность в теоремах и задачах (с доказательствами и решениями). Книга 1
Электронное издание
М.: МЦНМО, 2014
648 с.
ISBN 978-5-4439-2082-5

Настоящая книга является «решебником» задач из первых двух
глав учебника А. Н. Ширяева «Вероятность-1» и задачника «Задачи по
теории вероятностей». Добавлено также много новых задач. Приводимые
доказательства и решения будут полезны как студентам и аспирантам,
так и преподавателям, демонстрируя как следует решать вероятностные
задачи, доказывать вероятностные теоремы и как их излагать.

Подготовлено на основе книги: Ширяев А. Н., Эрлих И. Г., Яськов П. А. Вероятность в теоремах и задачах (с доказательствами и решениями). Книга 1. ––
М.: МЦНМО, 2013. –– 648 с.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)241–74–83.
http://www.mccme.ru

ISBN 978-5-4439-2082-5
© А. Н. Ширяев, И. Г. Эрлих, П. А. Яськов, 2013.
© МЦНМО, 2014.

Предисловие

В качестве дополнения к нашему учебнику «Вероятность» (1980,
1989, 2004, 2006, 2011) в 2006 и 2011 гг. было издано учебное пособие
«Задачи по теории вероятностей» (издательство МЦНМО). В это пособие вошли как «старые» задачи из учебника, так и большое количество
«новых» задач, которые мною собирались в течение многих лет. Многие
задачи возникали на наших специальных семинарах для студентов
и аспирантов в МГУ. В предисловии к пособию «Задачи» мы отмечали,
что приводимые, скажем, в § 5 второй главы задачи непосредственно
примыкают к теоретическому материалу в § 5 второй главы учебника
«Вероятность». При этом, например, запись B1.II.11.1 означает ссылку
на книгу А. Н. Ширяева «Вероятность-1», гл. II, § 11, пункт 1, а запись
II.11.1 –– ссылку на задачу 1, гл. II, § 11 данного пособия.
Тем самым читатель в дополнение к теоретическому материалу
получает возможность самоконтроля, решая соответствующие задачи
из пособия. Задачи, приводимые в этом пособии, носят разный характер. Некоторые из них можно назвать задачами-упражнениями на
проверку усвоения понятий, фактов, теоретических результатов из учебника «Вероятность». Другие задачи (средней и повышенной трудности)
требуют уже больше усилий в их решении. Наконец, многие задачи,
в сущности, являются теоретическими и призваны дать дополнительный теоретический материал.
Нам неоднократно задавали вопросы по поводу решения многих
задач. Именно это и побудило нас подготовить данное издание, содержащее решение задач из пособия. Настоящая «Книга 1» охватывает
материал первых двух глав. Следует подчеркнуть, что у нас были
многие решения, подготовленные как мною, так и нашими студентами
и аспирантами в течение многих лет. Вместе с этими решениями или
указаниями, а также решениями из многих других источников у нас
образовался первый вариант «решебника». На заключительном этапе
основную работу по подготовке текстов решений выполнили И. Эрлих
(глава I) и П. Яськов (глава II). Следует особо отметить, что П. Яськов
добавил во вторую главу множество новых задач и дал ко многим из
задач, и «старым», и «новым», оригинальные решения.
Мы надеемся, что настоящее пособие с решениями задач и доказательствами многих теорем будет полезно как студентам и аспирантам,

Предисловие

так и научным работникам, демонстрируя, как следует решать вероятностные задачи, доказывать теоремы и как надо, по нашему мнению,
их излагать. Авторы пособия будут признательны читателям как за
замечания к нашим решениям, так и за предложения по поводу решения
приводимых задач.
А. Ширяев
Кафедра теории вероятностей
Московского государственного университета
им. М. В. Ломоносова,
Математический институт им. В. А. Стеклова
Российской академии наук

Глава I

Элементарная теория вероятностей

§ 1. Вероятностная модель эксперимента с конечным
числом исходов

1. Установить справедливость следующих свойств операций ∩ (пересечения) и ∪ (объединения):
A ∪ B = B ∪ A, A ∩ B = B ∩ A (коммутативность),
A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C (ассоциативность),
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
(дистрибутивность),
A ∪ A = A, A ∩ A = A (идемпотентность).
Показать также, что A ∪ B = ¯ ¯A ∩ ¯ ¯B, A ∩ B = ¯ ¯A ∪ ¯ ¯B.
Решение. Для доказательства равенства множеств необходимо
и достаточно показать, что каждый элемент одного множества является
элементом другого и наоборот. Например, равенство A ∪ B = B ∪ A
проверяется так: если x ∈ A ∪ B, то либо x ∈ A, либо x ∈ B. В обоих
случаях x ∈ B ∪ A. Значит, A ∪ B ⊆ B ∪ A. Точно так же проверяется,
что B ∪ A ⊆ A ∪ B. Остальные свойства проверяются аналогично.

2. (Разные интерпретации неполного факториала (N)n ≡
≡ N(N − 1)...(N − n + 1) –– числа размещений из N по n.) Показать,
что
(a) число упорядоченных выборок (...) размера n (без повторений
элементов –– «выбор без возвращения»), составленных из элементов
множества A с числом элементов |A| = N, равно (N)n, 1 ⩽ n ⩽ N;
(b) число слов длины n, составленных из различных букв, выбранных из алфавита, содержащего N букв, равно (N)n, 1 ⩽ n ⩽ N;
(c) число различных функций y = f(x), определенных на множестве
X с |X| = n, принимающих значения в множестве Y с |Y| = N, n ⩽ N,
и таких, что если x1 ̸= x2, то f(x1) ̸= f(x2) (т. е. f : X → Y является
инъекцией), равно (N)n.
Решение. (a) Поскольку выборки упорядоченные, у каждого элемента выборки есть номер. Есть N способов выбрать первый элемент. Когда первый элемент фиксирован, следующий можно выбрать
N − 1 способами, и т. д. Наконец, когда фиксированы n − 1 пер

Гл. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ

вых элементов, последний можно выбрать N − n + 1 способами. Отсюда следует, что общее число требуемых последовательностей есть
N(N − 1)...(N − n + 1) (≡ (N)n).
(b) Каждое интересующее нас слово есть упорядоченная выборка
длины n. Выборка производится без возвращения элементов (буквы
в слове различны) из множества (алфавита), состоящего из N элементов. Таким образом, задача сведена к предыдущей.
(c) Функция определена тогда, когда при каждом значении аргумента определено значение функции. Занумеруем значения аргумента числами от 1 до n, и тогда каждой функции взаимно однозначно ставится
в соответствие упорядоченная выборка элементов из Y длины n (i-й
элемент выборки есть значение функции при i-м значении аргумента).
Задача сведена к п. (a) данной задачи.

3. (Разные интерпретации биномиальных коэффициентов

Cn
N ≡
N!

n! (N − n)! .)

Показать, что
(a) число неупорядоченных выборок [...] размера n (без повторений элементов –– «выбор без возвращения»), составленных из элементов множества A с |A| = N, равно Cn
N, 1 ⩽ n ⩽ N;
(b) число упорядоченных последовательностей (...) длины N, состоящих из n «единиц» и (N − n) «нулей», равно Cn
N, 1 ⩽ n ⩽ N;
(c) число способов, которыми n неразличимых дробинок можно
разместить по N различным ячейкам, причем так, чтобы в каждой
ячейке было не больше одной дробинки («размещение с запретом»),
равно Cn
N, 1 ⩽ n ⩽ N;
(d) число неубывающих путей на двумерной целочисленной решетке Z2
+ = {(i, j) : i, j = 0, 1, 2, ...}, начинающихся в точке (0, 0) и приходящих в точку (n, N − n), равно Cn
N (неубывающий путь –– это такой путь,
у которого на каждом шаге сдвиг происходит либо вверх на единицу,
либо вправо на единицу), 0 ⩽ n ⩽ N, C0
N = 1;
(e) число различных подмножеств D множества A с |A| = N,
состоящих из n элементов (|D| = n, n ⩽ N), равно Cn
N.
Решение. (a) Согласно задаче I.1.2(a) число упорядоченных выборок длины n из N элементов без повторений есть (N)n. При этом
каждая неупорядоченная выборка подсчитана n! раз. (Действительно, неупорядоченная выборка есть множество из n элементов. Число
упорядоченных выборок из него есть (n)n = n!.) Таким образом, число

требуемых в задаче выборок есть (N)n

n!
= Cn
N.

§ 1. ВЕРОЯТНОСТНАЯ МОДЕЛЬ
7

(b) Для задания упорядоченной последовательности из n единиц
и N − n нулей необходимо и достаточно задать номера позиций, на
которых будут стоять единицы. Таким образом, число требуемых последовательностей есть число способов выбрать неупорядоченно n
натуральных чисел (номеров позиций) из чисел от 1 до N. Это число
подсчитано в п. (a) данной задачи.
(c) Каждому способу размещения дробинок можно однозначно поставить в соответствие упорядоченную последовательность из нулей
и единиц: на i-й позиции последовательности стоит 1, если в i-й ячейке
есть дробинка, и 0 иначе. Задача сведена к п. (b) данной задачи.
(d) Интересующий нас путь состоит из n отрезков, расположенных
горизонтально, и N − n отрезков, расположенных вертикально. Аналогично п. (c) строится взаимно однозначное соответствие между всеми последовательностями из n единиц и N − n нулей и данными путями: на i-й
позиции последовательности стоит 1, если i-й отрезок пути расположен
горизонтально, и 0 иначе. Задача сведена к п. (b) данной задачи.
(e) Нумеруем элементы множества A числами от 1 до N. Аналогично
предыдущим пунктам строится взаимно однозначное соответствие между всеми последовательностями из n единиц и N − n нулей и всеми подмножествами множества A: на i-й позиции последовательности стоит 1,
если i-й элемент множества A принадлежит выбранному подмножеству,
и 0 иначе. Задача сведена к п. (b) данной задачи.

4. Рассматриваются неубывающие пути на целочисленной решетке Z2
+ = {(i, j) : i, j = 0, 1, 2, ...}, которые выходят из точки (0, 0)
и приходят в точку (n, n), при этом, однако, оставаясь ниже «диагонали» или касаясь ее (т. е. пути, проходящие через точки множества
{(i, j) ∈ Z2
+, 0 ⩽ j ⩽ i ⩽ n}).
Показать, что число таких путей равно Cn+1, где

Cn = 1

n Cn−1
2(n−1),
n ⩾ 1,

–– числа Каталана. (Иногда под числами Каталана понимают числа
cn = Cn+1, n ⩾ 0.)
Решение. По утверждению I.1.3(d) при N = 2n всего неубывающих путей, идущих из (0, 0) в (n, n), ровно Cn
2n. Нас интересуют только
те из них, которые не пересекаются и не касаются прямой y = x + 1.
Подсчитаем число ломаных, имеющих общие точки с указанной прямой.
Для этого каждой такой ломаной однозначно поставим в соответствие
ломаную, идущую из точки (0, 0) в точку (n − 1, n + 1), по такому
правилу –– выбираем самую верхнюю вершину ломаной на указанной

Гл. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ

прямой и отражаем часть ломаной, расположенную правее этой точки,
относительно нашей прямой. Обратное отображение строится аналогично (общая точка с прямой y = x + 1 будет существовать, так как
начало ломаной лежит ниже прямой, а конец выше). Следовательно,
в силу задачи I.1.3(d) число ломаных, имеющих с нашей прямой общие
точки, есть Cn−1
2n . Искомое же число равно

Cn
2n − Cn−1
2n
=
(2n)!

n!(n − 1)!

1

n −
1

n + 1

=
(2n)!

n!(n + 1)! =
1

n + 1Cn
2n = Cn+1.

5. Числа Каталана Cn, n ⩾ 1, допускают много интересных комбинаторных интерпретаций. Например, рассмотрим число Nn разных
способов подсчета суммы n чисел a, b, c, d, ..., при которых каждый
раз складываются лишь два числа (изменение порядка следования
слагаемых не допускается). Скажем, при n = 3 сумму a + b + c можно
подсчитывать, удовлетворяя сформулированному требованию «складывать по два числа», расставляя соответствующим образом скобки (·):
a + b + c = (a + (b + c)) = ((a + b) + c). (Здесь число разных способов
N3 = 2.) При n = 4 имеем уже пять возможностей (N4 = 5):

a + b + c + d = ((a + b) + (c + d)) = (((a + b) + c) + d) =

= ((a + (b + c)) + d) = (a + ((b + c) + d)) =

= (a + (b + (c + d))).

(a) Показать, что при любом n ⩾ 3 число Nn разных способов
подсчета равно Cn.
(b) Рассматриваются диагональные триангуляции правильного n-угольника, n ⩾ 4, т. е. разбиения на треугольники с помощью
непересекающихся диагоналей (выходящих из той или иной вершины;
очевидно, что число таких диагоналей, выходящих из одной вершины,
равно n − 3). Показать, что число Nn таких триангуляций равно Cn−1.
(c) Показать, что числа Каталана Cn, n > 1, удовлетворяют рекуррентным соотношениям

C∗
n =

n−1
i=1
C∗
i C∗
n−i
(∗)

(с C∗
0 = 0 и C∗
1 = 1).
(d) Установить, что производящая функция F ∗(x) = n⩾1
C∗
nxn по
следовательности (C∗
n)n⩾1, определенной рекуррентными соотношениями (∗), удовлетворяет уравнению

F ∗(x) = x + (F ∗(x))2.

§ 1. ВЕРОЯТНОСТНАЯ МОДЕЛЬ
9

(e) Показать, что (с учетом условия F ∗(0) = 0)

F ∗(x) = 1

2 (1 − (1 − 4x)1/2),
|x| ⩽ 1

4,

и вывести отсюда, что коэффициенты C∗
n (при xn) совпадают, как
и следовало ожидать, с числами Каталана Cn:

C∗
n = − 1

2 Cn
1/2(−4)n = 1

n Cn−1
2(n−1) = Cn.

Решение. (a) Построим взаимно однозначное соответствие между
ломаными из задачи I.1.4 и алгебраическими записями разных способов
подсчета суммы n чисел. Будем двигаться по такой записи слева направо. Заменим каждую открывающуюся скобку на шаг вправо в нашей
ломаной, а каждый плюс –– на шаг вверх. Поскольку открывающихся
скобок в выражении столько же, сколько и знаков суммирования,
т. е. n − 1, мы получим ломаную, идущую из точки (0, 0) в точку
(n − 1, n − 1). Поскольку перед каждым плюсом должна идти своя
открывающаяся скобка, в любой момент времени число сделанных
шагов направо в ломаной не меньше, чем число шагов вверх, и ломаная
действительно не поднимается выше прямой y = x.
Построим обратное отображение. Будем двигаться по ломаной из
точки (0, 0) в точку (n − 1, n − 1). Шаг направо мы заменяем на
открывающуюся скобку, шаг вверх –– на плюс. В получившейся последовательности открывающихся скобок и знаков сложения расставляем буквы перед каждым знаком сложения и в конце получившегося
выражения. Теперь расставляем закрывающиеся скобки так: выберем
самую правую открывающуюся скобку, тогда следующие три символа
будут –– буква, плюс и еще буква (плюс будет, поскольку последний
отрезок ломаной –– шаг вверх, буква будет, поскольку буквы расставлялись так, чтобы выражение было правильным). Поставим после этих
четырех символов закрывающуюся скобку и временно заменим это
подвыражение на какую-нибудь букву. С точки зрения ломаной, мы
убрали один «уголок», состоящий из шагов направо и вверх, поэтому
ее свойство не пересекать прямую y = x сохранилось. Продолжим эту
операцию, пока не получим одну букву. Затем постепенно развернем все
выражение, заменяя каждую новую букву обратно на подвыражение.
Итак, доказано, что отображение взаимно однозначно, значит, число
описанных способов действительно равно Cn.
(b) Сначала докажем по индукции, что число диагоналей при триангуляции равно n − 3. Для четырехугольника это очевидно. Диагональ