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

В этой главе излагаются начала комбинаторики и теории вероятностей. Если вы знакомы с ними, советуем просмотреть начало главы и внимательно прочесть последние разделы. Многие главы этой книги не используют теорию вероятностей, но кое-где она необходима.

Раздел 6.1 напоминает основные факты комбинаторики (в том числе формулы для перестановок и сочетаний). Раздел 6.2 содержит аксиомы вероятности и основные факты о распределениях вероятностей. В разделе 6.3 определяются понятия случайной величины, ее математического ожидания и дисперсии. Раздел 6.4 посвящен геометрическому и биномиальному распределениям. Исследование биномиального распределения продолжается в разделе 6.5 (оценка «хвостов»). В последнем разделе 6.6 применение теории вероятностей иллюстрируется на примере трёх задач: парадокса дня рождения, случайного распределения шаров по урнам и оценки длины выигрышных участков при бросании монеты.

6.1. Подсчёт количеств

Иногда можно найти число предметов определённого вида, не перечисляя их все. Например, легко найти число всех га-битовых строк или всех перестановок га объектов. В этом разделе мы рассмотрим основные методы такого подсчёта. Предполагается, что читатель знаком с понятиями теории множеств (см. разд. 5.1).

Правила суммы и произведения

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

Правило суммы (rule of sum) гласит, что \А U В\ = \А\ + \В\ для непересекающихся конечных множеств А и В (частный случай формулы (5.3)). Если символ на номере машины должен быть

либо латинской буквой, либо цифрой, то всего есть 26 + 10 = 36 возможностей, так как букв 26, а цифр 10.

Правило произведения (rule of product) утверждает, что \А x В\ = \А\ \В\ для конечных множеств А и В, см. (5.4). Например, имея 28 сортов мороженого и 4 вида сиропа, можно изготовить 28 • 4 = 112 вариантов мороженого с сиропом (не смешивая разные сорта мороженого и сиропа).

Строкой (string; по-русски говорят также о словах) называют конечную последовательность элементов некоторого конечного множества S (называемого алфавитом). Например, существует 8 двоичных (составленных из нулей и единиц) строк длины 3:

Иногда строку длины к называют /г-строкой (/г-string). Подстрокой (substring) s строки s называется произвольная последовательность идущих подряд элементов строки s. Говоря о /г-подстроке (/г-substring), имеют в виду подстроку длины к. Так, 010 является 3-подстрокой строки 01101001 (она начинается с позиции 4), а 111 - нет.

Строка длины к из элементов множества S является элементом прямого произведения Sk, так что всего существует \S\k строк длины к. В частности, имеется 2к двоичных строк длины к. Это можно объяснить ещё и так: первый элемент строки можно выбрать 15*1 способами; для каждого из них есть 15*1 вариантов продолжения, и так далее - всего к выборов, получается S х S х ... х S (к множителей) вариантов.

Перестановки

Перестановкой (permutation) конечного множества S называется упорядоченная последовательность всех его элементов, в которой каждый элемент встречается ровно один раз. Так, существует 6 перестановок множества S = {а, Ь, с} :

Всего имеется га! перестановок множества из га элементов, так как первый элемент перестановки можно выбрать га способами, второй га - 1 способами, третий га - 2 способами, и т.д.

Строки

000, 001, 010, 011,100,101, ПО, 111.

abc, acb, Ьас, bca, cab, cba.

Размещения без повторений

Если каждый элемент можно использовать только один раз, но не требуется использовать все элементы, говорят о размещениях без повторений. Пусть фиксировано множество S из га элементов и некоторое к, не превосходящее га. Размещением без повторений из га по к называют последовательность длины к, составленную из различных элементов S. (Английский термин - fc-permutation.) Число таких размещений равно

так как существует га способов выбора первого элемента, га - 1 способов выбора второго элемента, и так далее до к-то элемента, который можно выбрать га - к + 1 способами.

Например, существует 12 = 4 • 3 последовательностей из двух различных элементов множества {а, Ь, с, d}:

Частным случаем этой формулы является формула для числа перестановок (поскольку перестановки являются частным случаем размещений при га = к).

Сочетания

Сочетаниями (/г-combinations) из га элементов по к называются к-элементные подмножества какого-либо га-элементного множества. Например, у множества {а, Ь, с, d} из 4 элементов имеется 6 двухэлементных подмножеств

Число сочетаний из га по к в к\ раз меньше числа размещений без повторений (для тех же пик), так как из каждого /г-сочетания можно сделать к\ размещений без повторений, переставляя его элементы. Поэтому из формулы (6.1) следует, что число сочетаний из га по к равно

аЬ, ас, ad, Ьа, be, bd, са, cb, cd, da, db, dc.

{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.

ra!

Для к = 0 эта формула даёт 1, как и должно быть (есть ровно одно пустое подмножество; напомним, что 0! = 1).