Основные формулы комбинаторики

⇐ ПредыдущаяСтр 6 из 11Следующая ⇒

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

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

Правило суммы. Если некоторый объект может быть выбран из множества объектов m способами, а другой объект может быть выбран n способами, то выбрать либо , либо можно способами.

Правило произведения. Если объект можно выбрать из множества объектов m способами и после каждого такого выбора объект можно выбрать n способами, то пара объектов ( , ) в указанном порядке может быть выбрана способами.

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

Замечание 5.1. Для пустого множества принимается соглашение: пустое множество можно упорядочить только одним способом; по определению полагают .

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

Решение:

Ответ: 24.

Определение 5.2. Размещениями называют множества, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.

Число размещений определяют по формуле:

Пример 5.2. Расписание одного дня состоит из 5 уроков. Определить число способов, которыми можно составить расписание при выборе из 15 дисциплин.

Решение:

Ответ: 3603600.

Определение 5.3. Сочетаниями из n различных элементов по m элементов называются множества, содержащие m элементов из n числа заданных, и которые отличаются хотя бы одним элементом.

Число сочетаний определяют по формуле

Пример 5.3. Сколькими способами можно выбрать из 20 человек трёх человек на три одинаковые должности.

Решение:

Ответ: 1140.

Замечание 5.2. Если в размещениях из n элементов по m элементов некоторые из элементов (или все) могут оказаться одинаковыми, то такие размещения называют размещениями с повторениями из n элементов по m элементов.

Число размещений с повторениями из n элементов по m элементов равно

Пример 5.4. В конкурсе по 5 номинациям участвуют 10 фильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены различные призы.

Решение:

Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций как составом фильмов, так и их порядком по номинациям (или и тем, и другим). Причём одни и те же фильмы могут повторяться несколько раз (любой фильм может получить призы как по одной, так и по нескольким, включая все пять, номинациям).

Ответ: 100000.

Замечание 5.3. Если в сочетаниях из n элементов по m элементов некоторые из элементов (или все) могут оказаться одинаковыми, то такие сочетания называют сочетаниями с повторениями из n элементов по m элементов.

Число сочетаний с повторениями из n элементов по m элементов равно

Пример 5.5. В конкурсе по 5 номинациям участвуют 10 фильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены одинаковые призы.

Решение:

Если по каждой номинации установлены одинаковые призы, то порядок следования фильмов в комбинации пяти призёров не имеет значения, и число вариантов распределения призов представляет собой число сочетаний с повторениями из 10 элементов по 5 элементов. В результате получим

Ответ: 2002.

Замечание 5.4. Если в перестановках из общего числа n элементов есть k различных элементов, при этом первый элемент повторяется n₁ раз, второй элемент n₂ раз, k-й элемент – n_k раз, причём , то такие перестановки называют перестановками с повторениями из n элементов. Число перестановок с повторениями из n элементов равно:

Пример 5.6. Сколько существует семизначных чисел, состоящих из цифр 4, 5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 – по 2 раза?

Решение:

Каждое семизначное число отличается от другого числа порядком следования цифр. В семизначном числе цифра 4 повторяется 3 раза, т.е. ; цифра 5 повторяется 2 раза, т.е. ; цифра 6 повторяется 2 раза, т.е. . Т.к. получаются семизначные числа, то . Используя формулу перестановок с повторениями из 7 элементов получим

Ответ: 210.

Действия над событиями

Введем понятия суммы, произведения событий.

Определение 6.1. Суммой двух событий называется событие, состоящее в появлении хотя бы одного из них.

Сумма двух событий и обозначается через . Аналогично определяется и обозначается сумма n событий – событие, состоящее в появлении хотя бы одного из них. Сумму n событий обозначают .

Пример 6.1. Если случайное событие – попадание в мишень при первом выстреле, а событие – попадание в мишень при втором выстреле, то – событие хотя бы одного попадания.

Определение 6.2. Произведением двух событий называется событие, состоящее в одновременном их появлении.

Произведение двух событий и обозначается через .

Пример 6.2. Если – деталь годная, – деталь окрашенная, то – деталь годная и окрашенная.

Аналогично определяется и обозначается произведение в случае большего числа событий. Произведение n событий обозначают .

Пример 6.3. Если случайные события , , – появление герба соответственно в первом, втором и третьем подбрасывании монеты, то – выпадение герба во всех трех испытаниях.

Пример 6.4. Победитель соревнования награждается призом (случайное событие ), денежной премией (случайное событие ), медалью (случайное событие ). Что представляют собой события: а) ; б) ?