Тема 1. Случайные события

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

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

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

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

Пусть множество состоит из элементов, а множество  – из элементов. Рассмотрим множество, состоящее из всевозможных упорядоченных пар (a, b), где элемент принадлежит множеству A, а элемент b принадлежит множеству B (такое множество называется декартовым произведением множеств A и B и обозначается A × B).

Правило произведения. Множество содержит элементов.

Вообще, множество состоит из элементов, где  – число элементов в ,  – в и т.д.

Для решения задач комбинаторики удобна следующая формулировка правила произведения.

Пусть объект можно выбрать различными способами, после каждого выбора объекта объект можно выбрать различными способами, …, после каждого выбора объектов объект можно выбрать различными способами. Тогда количество способов, которыми можно выбрать , равно .

Пример. Сколько четырехбуквенных слов можно составить из карточек «в», «е», «ч», «н», «о», «с», «т», «ь»?

Решение. Пусть  – k-я буква слова . Тогда и по правилу произведения сразу получим ответ: .

Пример. Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?

Решение. Выбор объекта  – поля для белой ладьи – может быть сделан способами. Независимо от выбора этого поля белая ладья бьет 15 полей, поэтому для черной ладьи остается 64 – 15 = 49 полей: .

Пример. Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

Решение. Все четырехзначные числа, а их 9999 – 999 = 9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра.

Всего нечетных цифр – пять, поэтому выбор k-й цифры числа может быть сделан способами , а количество четырехзначных чисел, у которых все цифры нечетные, равно .

Следовательно, количество чисел, в записи которых есть хотя бы одна четная цифра, равно 9000 – 625 = 8375.

Замечание. Обратите внимание на идею, которую мы использовали – переход к дополнению изучаемого множества. Это пример применения второго общего правила комбинаторики – правила суммы.

Правило суммы. Если объект можно выбрать различными способами, а объект можно выбрать различными способами, причем результаты выборов объектов и никогда не совпадают, то выбор «либо а, либо » можно осуществить различными способами.

Часто в задачах приходится применять сразу оба правила комбинаторики.

Пример. Сколько различных слов можно получить, переставляя буквы слова «комбинаторика»?

Решение. В слове «комбинаторика» 13 букв и если бы все они были различными, то, переставляя их, можно было бы получить слов. Но в нашем случае буквы «к, о, u, а» встречаются по два раза. Обозначим их через Ясно, что слова, отличающиеся друг от друга перестановкой букв и одинаковые, так что разбиваются на пары одинаковых слов. Каждая такая группа из слов тоже разбивается на пары одинаковых с точки зрения буквы слов и т.д.

Следовательно, различных слов, переставляя буквы слова «комбинаторика», можно получить

.