ЛЕКЦИЯ 1

ТЕМА: ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

1. Краткие исторические сведения. Цель науки теория вероятностей.

1. Краткие исторические сведения. Цель науки теория вероятностей.

Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (16-17 века). Кардано. Гюйгенс, Паскаль. Ферма и др.). Следующий этап развития связан с именем Якоба Бернулли (1654-1705). Доказанная им теорема "Закон больших чисел", которую мы рассмотрим позже, была первым теоретическим обоснованием накопленных фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу и Пуассону. Качественно новый период развития теории вероятностей связан с именами русских математиков П.Л. Чебышева, А.А. Маркова, А.М. Ляпунова.

Цель науки теория вероятностей - описание, объяснение, предсказание явлений действительности на основе установленных законов, что позволяет находить решения в типичных ситуациях.

2. Правила умножения и сложения.

Рассмотрим два правила, которые применяются при решении комбинаторных задач и задач теории вероятностей.

2.1. Правило умножения.

Установим данное правило, рассмотрев задачу:

Необходимо составить варианты контрольной работы, каждый из которых должен содержать три задачи. Первая задача из любого параграфа первой главы, вторая- из второй главы, третья- из третьей главы. Причем, первая и третья главы содержат по два параграфа, а вторая глава- три параграфа.

Решение:

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

Первая задача

Вторая задача

Третья задача

Согласно полученного графа, количество вариантов контрольной работы равно 12. Выбор первой задачи сопровождается двумя способами, каждый из способов- выбором второй задачи тремя способами, в свою очередь каждый из них - выбором третьей задачи двумя способами. Таким образом , количество вариантов контрольных работ равно произведению 2·3·2=12.

Рассуждения, которые были проведены при решении задачи, подтверждают справедливость правила умножения:

Пусть требуется выполнить одно за другим какие-то k действий. Если первое действие можно выполнить n₁ способами, второе- n₂ способами, третье- n₂ способами, …k-ое действие- n_k способами. Тогда все k действий можно выполнить n₁n₂...n_k способами.

2.2. Правило сложения.

Как и предыдущее правило выведем его с помощью задачи:

Имеется 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколько способов выбора двух изделий возможно, если учитывается порядок выбора изделий?

Решение:

Пусть первое действие- выбор изделий первого сорта, второе действие- выбор изделий второго сорта. По правилу умножения два изделия первого сорта можно выбрать 20·19=380 способами. Аналогично, два изделия второго сорта можно выбрать 30·29=870 способами .

Согласно условию задачи нужно выбрать два изделия какого-либо одного сорта. Значит должно быть выполнено либо первое действие, либо второе. Эти действия не могут быть выполнены одновременно, т.к. взаимно исключают друг друга. Поэтому общее число способов равно 380+870=1250.

Теперь сформулируем правило сложения:

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

Это правило распространяется на любое конечное число действий.

3. Размещения.

Пусть имеется множество из четырех различных цифр {3,5,7,8}. Необходимо составить всевозможные двузначные числа, каждое из которых состоит из различных цифр.

Каждое число является упорядоченным подмножеством, состоящим из двух элементов, данного множества, состоящего из четырех элементов. Перечислим их: 35, 37, 38, 53, 73, 83, 57, 58, 75, 85, 78, 87. Всего таких подмножеств- двузначных чисел получилось 12. Каждое упорядоченное подмножество называется размещением .

Определение : Размещением из п элементов по т называется любое упорядоченное подмножество из т элементов множества, состоящего из п элементов.

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

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

Доказательство: необходимо заполнить т мест элементами множества из п элементов. Каждое действие- это выбор определенного элемента. Действия совершаются последовательно, значит применимо правило умножения. Первый элемент можно выбрать п способами, второй- (п-1) способами, последний т-ый элемент- (п-(т-1)) способами. Тогда количество размещений равно п(п-1)(п-2)…(п-(т-1)). Умножим и разделим данное выражение на (п-т)!, преобразовав получим более удобный вид :

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

Решение: В числе важен порядок следования цифр. Следовательно, нужно найти количество размещений из 10 по 4:

Но среди них есть числа с нулем в начале. из полученного значения 5040 необходимо вычесть количество таких чисел. Найдем это количество: т.к. на первом месте стоит о, то оставшиеся три выбираем из 9, т.е.

Искомое количество чисел равно 5040-504=4536.

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

Рассмотрим случай, когда п=т. Такие размещения называются перестановками.

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

Формулу для определения количества перестановок дает теорема.

Теорема: Число перестановок п различных элементов равно п!, т.е. Р_п=п!

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

Следовательно, Р_n= n!

Пример1: Сколькими способами можно расставить 4 книги на полке?

Решение: Необходимо составить всевозможные упорядоченные множества из 4 элементов, т.е. составить перестановки. Количество их равно Р₄=4!=24.

Пример2: Сколькими способами можно расставить 9 книг на полке, но чтобы определенные 4 книги стояли рядом.

Решение: Будем считать выделенные 4 книги за один элемент. Тогда данное множество содержит 6 элементов. Количество способов расстановки этих элементов есть количество перестановок из 6 элементов: Р₆=6!=720. Но сами 4 книги, которые стоят рядом можно расставить Р₄=4!=24 способами. Расстановка 4 книг- это первое действие, расстановка 5 книг с блоком из 4-х книг - это второе действие. Данные действия последовательны, значит применимо правило умножения. Тогда способов всего 720 ·24=17280.

5, Сочетания.

В размещениях и перестановках важен порядок элементов. Рассмотрим случаи, когда порядок элементов в множествах не учитывается, т.е. случаи составления неупорядоченных множеств. Например:

Из чисел 3, 5, 2 составить всевозможные произведения из двух различных множителей.

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

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

Вернемся к задаче. Составим требуемые произведения:

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

Теорема: Число сочетаний из п элементов по т равно

Доказательство: Число размещений из п по т можно получить следующим образом: выбирать по т элементов, не учитывая порядок. Это есть сочетания из п по т. А затем в каждом подмножестве произвести перестановки. Пользуясь правилом умножения, получим

Откуда имеем:

Свойства сочетаний:

Пример 1. Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?

Решение: Среди выбранных шаров 4 белых и 3 черных. Т.к. порядок не учитывается, то белые можно выбрать количеством способов, равным

а черные

По правилу умножения искомое число способов равно 210·10=2100.

Пример2. Сколькими способами группу из 12 человек можно разбить на две подгруппы, в одной из которых должно быть не менее 5, а в другой- не более 9 человек?

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

Учитывая, что выбор первой подгруппы одновременно означает выи выбор второй, по правилу сложения найдем искомое число способов: 220 +495+792=1507.

Пример 3. 10 команд участвуют в розыгрыше первенства по футболу, лучшие из которых занимают 1-е, 2-е и 3-е места. Две команды, занявшие последние места, не будут участвовать в следующем первенстве. Сколько разных вариантов результата первенства может быть, если учитывать только положение первых трех и последних двух команд?

Решение: Распределение первых трех мест - это размещения

В результате остается 7 команд, две из которых выбывают из следующего первенства. Порядок выбывших команд не важен, поэтому это может произойти С₇²=21 способами. По правилу умножения имеем искомый результат 720 ·21=15120.

Контрольные вопросы

1. Цель науки- теория вероятностей ?

2. Сформулируйте основные правила комбинаторики- правила умножения и сложения.

3. Определение размещения и теорема о количестве размещений.

4. Определение перестановки и теорема о количестве перестановок.

5. Определение сочетания и теорема о количестве сочетаний.