Комбинаторика

Определение

Комбинаторика

Слово "комбинаторика" происходит от латинского
"combinare", которое означает "соединять, сочетать".
Комбинаторика - раздел математики, в котором
изучаются вопросы о том, сколько различных
комбинаций, подчиненных тем или иным условиям,
можно составить из заданных объектов.
Комбинаторными задачами интересовались и
математики, занимавшиеся составлением и
разгадыванием шифров, изучением древних
рукописей.
Сейчас комбинаторика находит приложения во многих
областях науки: в биологии, в химии, механике  и т.д.

Определение

Факториал

Факториа́л числа n (обозначается n!,
произносится эн факториа́л) — это
произведение всех  натуральных чисел
до  n  включительно:

Факториал

4! = 1•2•3•4 = 24

3! = 1•2•3 = 6

Главное свойство факториала

Следствие

1! = 1
0! = 1

Несколько первых значений для n!:

1! = 1

2! = 1 ∙ 2 = 2

3! = 1 ∙ 2 ∙ 3 = 6

4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24

5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120

6! = 5! ∙ 6 = 720 и т. д.

Принято считать,
что 0 ! = 1

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

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке.

Pn = 1·2·3·…·(n − 2)(n − 1)n

Pn = n!

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

Количество размещений из n элементов
по два обозначают через

(по первой букве французского слова
arrangement – размещение)

Размещения

Запишем все размещения из 3 элементов a, b, с по 2:

Размещения

Сколькими способами можно распределить два билета на разные кинофильмы между семью друзьями?

Размещением из n элементов по k называют любой упорядоченный набор из k элементов, составленный из данных n элементов.

Аналогично можно получить: А3n, А4n, Аkn.

Размещения

Размещением из n элементов по k ( k ≤ n ) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из
n элементов.

Два размещения из n элементов считаются различными, если они отличаются самими элементами или порядком из расположения.

Формула числа
размещений

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

Сочетания

Сочетания

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

В сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по k отличаются друг от друга хотя бы одним элементом.

Формула числа
сочетаний

Задача. «Проказница Мартышка, Осёл, Козёл и косолапый Мишка затеяли сыграть квартет» и для начала стали выбирать 4 инструмента из 11, имеющихся на складе. Найти число возможных выборок.

Решение. Воспользуемся тем, что число всех сочетаний из n элементов по k элементов вычисляется по формуле

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

Сколькими различными способами можно
распределить между шестью лицами две
разные путевки в санатории?

Сколькими способами можно присудить шести лицам три одинаковые премии?