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

2.1. Размещения без повторений

Пример 4. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?


Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество А, содержащее m элементов из m элементов.

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


Формула размещений из n элементов по m.


Здесь n! – n – факториал (factorial – анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n

n! = 1*2*3*…*n; 0! =1.


Значит, ответ на выше поставленную задачу будет следующим:


Решение примера 4.


Пример 5. Число размещений 4 объектов на рисунке 1 будет равно:


Рис.1.


Решение примера 5.

2.2. Перестановки без повторений

В случае, если n = m (см. размещения без повторений) А из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают Pn.

Pn=n!


Действительно, при n=m:


Формула вычисления перестановок из n элементов.


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


Решение:


Найдем количество всех перестановок из этих цифр:


P6= 6! = 720


Пример 7. Число перестановок 4 объектов на рисунке 2 будет равно:


Рис.2.


Формула вычисления перестановок из 4 элементов.

2.3. Сочетания без повторений

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

Всякое множество X состоящее из m элементов, называется сочетанием из n элементов по m.

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

Число сочетаний из n элементов по m обозначается (см. рис.3):


Рис.3.


И вычисляется по следующей формуле (см. рис.4):


Формула вычисления числа сочетаний из n элементов по m.


Пример 8. Число сочетаний 4 объектов на рисунке 5 будет равно:


Рис.5.


Решение примера 8.