2.1  Основные комбинаторные понятия

 

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

Пусть Е = {а1, а2, …, аn} – конечное множество.

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

Пример 1. Е = {а1, а2, а3} и k=2. Выпишем все размещения из этого подмножества по 2:

{а1, а2}, {а1, а3 }, {а2, а1 }, {а3, а1}, {а2, а3}, {а3, а2}.

Обозначим число размещений из n элементов по k через . При построении конкретного размещения на 1-ое место можно поставить любой из n элементов, на 2-ое – любой из оставшихся n-1 элементов и т. д. Поэтому

 при .

Считаем

 при ,

поскольку при  не существует размещений из n элементов по k. Кроме того, полагаем

.

Перестановками называются упорядоченные подмножества из n элементов множества Е.

Пример 2. Е = {а1, а2, а3}. Перестановками множества Е будут {а1, а2, а3}, {а1, а3, а2}, {а2, а1, а3}, {а2, а3, а1}, {а3, а1, а2}, {а3, а2, а1}.

Обозначим число перестановок из n элементов через . Очевидно, что перестановки – частный случай размещений элементов из Е по k, когда k=n. Поэтому для числа перестановок имеем

.

Как обычно, считаем 0!=1.

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

Пример 3. Е = {а1, а2, а3} и k=2. Сочетаниями из Е по 2 будут {а1, а2}, {а1, а3}, {а2,  а3}.

Сочетание отличается от размещения тем, что в нем не учитывается порядок. Поэтому каждому сочетанию соответствует k! размещений. Отсюда получается формула для числа  сочетаний из n элементов по k ():

.