Основные понятия комбинаторики

Для решения задач с использованием классического определения вероятности остановимся вкратце на основных правилах и понятиях комбинаторики.

Правило суммы. Если некоторый элемент а может быть выбран из совокупности элементов т способами, а другой элемент b может быть выбран п способами, то выбрать либо а_} либо b можно т + п способами.

Пример 1.11. В автосалон «Антилопа Гну» поступило 100 автомобилей одной марки «Форд», среди которых 30 автомобилей с автоматической коробкой передач и кондиционером и 20 с механической коробкой передач, но с климат-контролем. Остальные автомобили имеют другую комплектацию. Сколько существует способов извлечь случайно из этой партии автомобилей автомобиль с автоматической коробкой передач и кондиционером или автомобиль с механической коробкой передач, но с климат-контролем?

Решение. Автомобиль с автоматической коробкой передач и кондиционером может быть извлечен т = 30 способами, а с механической коробкой передач, но с климатконтролем — п = 20 способами. По правилу суммы существует т + п = 30 + 20 = 50 способов извлечения одной автомашины первого или второго вида.

Лемма 1.1. Из т различных элементов одной группы (а_{,…, а_гп) и п различных элементов другой группы можно составить ровно т • п

различных пар вида (a_if bj), содержащих, но одному элементу из каждой группы.

Доказательство

Составим из этих пар матрицу, содержащую т строк и п столбцов, так, чтобы пара (a_v /;_;) стояла на пересечении г-й строки и j-rо столбца, тогда каждая пара встретится только один раз.

Замечание 1.4. Лемма 1.1 определяет так называемое правило произведения комбинаторики.

Пример 1.12. В колоде карт имеем: мастей — 4, значений — 9 или 13, следовательно, всего различных карт 4 • 9 = 36 или 4 * 13 = 52.

Пример 1.13. Из пункта А в пункт В ведет 5 дорог, а из пункта В в пункт С — 3 дороги. Тогда число возможных путей из, А в С будет 5−3 = 15.

Обобщим лемму 1.1 на k групп различных элементов.

Лемма 1.2. Пусть дано k групп различных элементов: 1-я группа ;

«П…2-Я группа — «21>->^й2и₂> k-я группа — а_к1,…, а_к«_к. Тогда можно образовать ровно N =п_х? п₂ ?… • п_к различных комбинаций вида (^ai_l'^a2j₂'-'^ak_Jk)' содержащих по одному элементу из каждой группы.

Доказательство. Доказательство проводится методом математической индукции. При k = 2 эта лемма превращается в предыдущую. Предположим, что утверждение выполняется при k = /, т. е. можно образовать М = п_х? п₂- … • щ различных комбинаций {а_х^, а₂^,…, ащ). Докажем, что для k = I + 1 существует N = п_х • п₂- … • п_1+{ различных комбинаций вида (й_1;|, й_2;-₂ ^aij, > ^а/+1,>_/+|)• Каждую такую комбинацию можно представить как пару (й_)у1, а₂м'—>^ай) ^{и a}l+lji±

Число элементов первой из этих двух групп М = п_х? п₂-… • n_t, и по лемме 1.1 имеем.

Рассмотрим конечное множество, состоящее из различных элементов, например шаров, занумерованных от 1 до п. Из элементов данного множества можно образовать различные комбинации по k (k < п) элементов, выбирая элементы определенным образом. Различают два способа выбора: выбор с возвращением и выбор без возвращения. При выборе с возвращением эксперимент заключается в том, что на каждом шаге выбранный шар возвращается обратно, т. е. один и тот же шар может быть выбран более одного раза. В случае выбора без возвращения выбранный шар обратно не возвращается, так что каждый шар может быть выбран только один раз, т. е. комбинация не содержит повторяющихся номеров шаров.

Если в комбинации существенен порядок следования элементов (номеров шаров), то набор называют упорядоченным, в противном случае — неупорядоченным.

Определение 1.16. Упорядоченные наборы без возвращения назовем размещениями. Число различных размещений, которые можно образовать, выбирая k элементов из п, будем обозначать Д*.

Определение 1.17. Размещения из п элементов, но п называются перестановками. Число различных перестановок обозначается Р_п.

Определение 1.18. Неупорядоченные наборы без возвращения называются сочетаниями. Число различных сочетаний, которое можно образовать из п элементов по k, обозначается С* или (р.

Определим число комбинаций, которое можно получить, выбирая k элементов из п различными способами. При выборе с возвращением каждый из k элементов комбинации может быть выбран п различными способами, поэтому, но лемме 1.2 при п_х = п₂ = … = п_к = п получаем, что число возможных комбинаций равно N — п^к. При этом существенен порядок элементов в наборе.

Пример 1.14. Бросание двух костей — выбор из т = 1, 2, 3, 4, 5, 6. Учитываем порядок — 1-й элемент — число очков на первой кости, 2-й элемент — число очков на второй кости. Тогда N = 6? 6 = 36.

В случае выбора без возвращения первый элемент может быть выбран п способами, 2-й — (п- 1),k-и — (п — k + 1) способами. Тогда по лемме 1.2 число комбинаций равно п? (п — 1) • … • (и — k + 1). При этом существенен порядок элементов в наборе, т. е. число возможных размещений:

Отметим частный случай, когда к = п. В этом случае.

т.е. число возможных перестановок из п различных элементов равно п. Используя этот факт, мы можем получить число возможных неупорядоченных наборов без возвращения. Действительно, каждому набору из k различных элементов (х_{,…, х_к) отвечает к различных упорядоченных наборов, г. е. число неупорядоченных наборов в k раз меньше числа упорядоченных наборов без возвращения, г. е. число различных сочетаний.

Неупорядоченные наборы с возвращением подсчитываются сложнее, и мы приведем их число без вывода.

Таким образом, можно составить следующую итоговую таблицу:

Набор Выбор «—.	Упорядочен.	Неупорядочен.
С возвращением.
Без возвращения.

Остановимся на некоторых свойствах сочетаний, которые могут понадобиться в дальнейшем:

Эти свойства следуют непосредственно из формулы числа различных сочетаний, приведенной выше.

Пример 1.15. На оптовой базе имеется 100 телевизоров, из которых 5 неисправны. В магазин случайным образом отбирается 10 телевизоров. Найдем вероятность того, что 2 из отобранных телевизоров неисправны.

Решение. Эксперимент заключается в выборе 10 телевизоров из 100. Результат эксперимента — со, = (х_х, х₂, …, х_И)), где х, х₂,…, х₁₀ — любые из 100 телевизоров. Очевидно, в данном случае осуществляется выбор без возвращения, и поскольку нас нс интересует, в какой последовательности выбираются телевизоры, то наборы неупорядочены. Таким образом, общее число исходов определяется числом сочетаний из 100 по 10, т. е. |Q|=C^₀Обозначим через А событие {среди 10 отобранных 2 неисправных}. Благоприятствующими событию А являются исходы, когда из общего числа 5 неисправных телевизоров взято 2 (это можно сделать (^способами), а остальные 8 телевизоров исправны, т. е. они взяты из общего числа 95 исправных (количество способов Сд₅). Поэтому число благоприятствующих событию А исходов по лемме 1.1 | А | = С|? С|₅. Искомая вероятность равна.

Пример 1.16. Найдем вероятность того, что у 25 студентов группы дни рождения приходятся на разные дни.

Решение. Очевидно, элементарные исходы данного случайного эксперимента представляют собой упорядоченные наборы с возвращением, а элементарные исходы, благоприятствующие событию А, представляют собой упорядоченные наборы без возвращения, следовательно,.

Пример 1.17. Из колоды карт (52 карты) наудачу извлекаются три карты. Найдем вероятность того, что это будут тройка, семерка и туз.

Решение. Эксперимент — извлечение случайным образом трех карт из 52. Результат эксперимента со>,• = (.г, х₂, х₃) — комбинация из трех любых карт из 52. Очевидно, эксперимент определяет неупорядоченный выбор без возвращения. Тогда общее число элементарных исходов — это число сочетаний из 52 по 3, т. е. | Q|= С|₂.

Пусть событие А = (выбраны тройка, семерка и туз}. Благоприятствующими событию А исходами являются только комбинации из тройки, семерки и туза. Поскольку в колоде содержится по 4 тройки, семерки и туза различных мастей, то каждую из указанных карт можно выбрать 4 способами. По лемме 1.21А |= 4 -4 -4 = 4³.

Следовательно, искомая вероятность.

Пример 1.18. Слово «СТАТИСТИКА» составлено из карточек, на каждой из которых написана одна буква. Затем карточки перемешивают и наудачу раскладывают в ряд. Найдем вероятность того, что вновь получится слово «СТАТИСТИКА».

Решение. Эксперимент заключается в случайном расположении 10 букв в ряд. Результат эксперимента (элементарный исход) — последовательность из 10 букв. Очевидно, множество элементарных исходов ПЭИ определяется числом перестановок из 10 букв. т. е. |Q| = 10!

Пусть событие А = {получится слово «СТАТИСТИКА"}. Благоприятствующими событию А будут исходы, когда получится нужное нам слово. Некоторые буквы в слове «СТАТИСТИКА» повторяются (С — 2 раза, Т — 3 раза, А — 2 раза, И — 2 раза), поэтому возможны перестановки из данных букв, при которых слово не изменится. Число таких перестановок определяет число благоприятствующих событию Л исходов и равно | А |= 2!3!2!2! = 48.

Таким образом,