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 (
):
.