Перестановки, размещения и сочетания

Элементы комбинаторики

И МАТЕМАТИЧЕСКОЙ СТАТИСТИКЕ

ЛЕКЦИИ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ

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

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

Правило суммы. Если элемент первого типа можно выбрать k₁ способами, элемент второго типа – k₂ способами, …, элемент s-ого типа – k_s способами, то один элемент можно выбрать k₁ + k₂ + … + k_s способами.

Правило произведения. Если элемент первого типа можно выбрать k₁ способами, элемент второго типа – k₂ способами, …, элемент s-ого типа – k_s способами, то выбрать по одному элементу каждого типа можно k₁ × k₂ × … × k_s способами.

Пример 1. В мешке 6 груш, 4 яблока, 3 киви и 7 мандаринов. Сколькими способами можно выбрать один фрукт?

Решение. По правилу суммы: 6 + 4 + 3 + 7 = 20 способами.

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

Решение. По правилу произведения: 6 × 7 × 4 = 168 способами.

Определение 1. Размещениями без повторений называют упорядоченные k-элементные подмножества n-элементного множества, содержащие различные элементы. Их количество обозначают символом (буква А от французского слова arrangement – размещение).

Определение 2. Размещениями с повторениями называют всевозможные упорядоченные k-элементные подмножества n-элементного множества. Их количество обозначают символом .

Теорема 1.Число размещений без повторений (с повторениями) вычисляется по формуле

Пример 3. В непрозрачном мешке шесть фишек пронумерованных числами 1, 2, 3, 4, 5 и 6. Перемешав фишки извлекают по одной четыре и выкладывают в ряд. Получившееся число записывают, фишки возвращают в мешок и процедуру повторяют. Сколько чисел может получиться?

Решение. Элементы различные и располагаются упорядоченно (цифры четырехзначного числа), следовательно, общее число чисел равно = 6!/(6 – 4)! = 6 × 5 × 4 × 3 = 360.

Пример 4. Последовательность четырех клеток закрашена четырьмя разными красками (одна клетка – одной краской). Сколько можно образовать четырехклеточных последовательностей, если для закрашивания можно использовать семь красок, и одной краской можно закрасить любое число клеток?

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

Определение 3. Перестановками из n элементов без повторений называют размещения без повторений из n элементов по n. Их количество обозначают Р_n (буква Р от французского слова permutation – перестановка).

Определение 4. Перестановками с повторениями состава (k₁, k₂, …, k_n) из элементов а₁, а₂, …, а_n называют упорядоченные множества из k = k₁ + k₂ + … + k_n элементов, в каждое из которых элемент а₁ входит k₁ раз, элемент а₂ – k₂ раз, …, элемент а_n – k_n раз. Их количество обозначают Р (k₁, k₂, …, k_n).

Теорема 2. Число перестановок без повторений (с заданным числом повторений) вычисляется по формуле

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

Решение. Р₆ = 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 чисел.

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

Решение.

Определение 5. Сочетаниями из n элементов по k без повторений называют неупорядоченные k-элементные подмножества n-элементного множества, содержащие различные элементы. Их количество обозначают (буква С от французского слова combination – комбинация).

Определение 6. Сочетаниями из n-элементов по k называют всевозможные неупорядоченные k-элементные подмножества n-элементного множества. Их количество обозначают

Теорема 3.Число сочетаний без повторений (с повторениями) вычисляется по формуле

Пример 7. Сколькими способами можно составить команду из пяти человек для соревнования по плаванию, если имеются восемь пловцов?

Решение. способами.

Пример 8. Сколькими способами можно разложить 20 одинаковых конфет по 5 разным мешкам?

Решение. способами.

Для того, чтобы безошибочно различать виды комбинаций (перестановки, размещения и сочетания) следует применять следующие алгоритмы:

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

Пример 9. В мешке 25 шаров: 4 красных, 6 синих, 7 зеленых и 8 желтых. Сколькими способами можно достать 4 шара так, чтобы среди них были хотя бы три одинаковых?

Решение. «Хотя бы три» обозначает «ровно три» или «ровно четыре». Три одинаковых шара в четверку можно выбрать способами, а четыре одинаковых – способами. Отсюда, общее число способов равно 2046 + 121 = 2167. Для решения использовалась не только формула числа сочетаний, но и основные правила комбинаторики.