Элементы комбинаторного анализа (стр. 2 из 4)
Утверждение 2.Если 
- конечные попарно непересекающиеся множества, то множество 
также конечно и 
.
Утверждение 3 (принцип включения-выключения).Если - конечные множества, то множество
также конечно и 
.
Утверждение 4.Если - конечные множества, то множество 
также конечно и 
.
1.2. Комбинаторные объекты и комбинаторные числа
В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества
, а также числовые характеристики этих объектов.При подсчете числа объектов с наперед заданными свойствами используются следующие два правила.
Правило суммы. Если объект
может быть выбран 
способами, а объект 
способами, то выбор «либо , либо » может быть осуществлен 
способами.Правило произведения. Если объект
может быть выбран способами и после каждого из таких выборов объект в свою очередь может быть выбран способами, то выбор « и » в указанном порядке может быть осуществлен 
способами.Набор элементов
из множества 
называется выборкой объема из 
элементов или 
-выборкой.Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной.
В выборках могут допускаться или не допускаться повторения элементов. Если повторения элементов не допускается, то выборка называется выборкой без повторений. Если повторения элементов допускаются – выборкой с повторениями. В выборках без повторений все элементы попарно различны
Рассмотрим некоторые комбинаторные объекты и их комбинаторные числа.
1.Размещения.Размещением элементов из
по (или размещением из nэлементов по k) называется упорядоченная -выборка без повторений.Пример 1. Пусть
и 
. Выпишем все размещения из этого множества по два: 
, 
, 
, 
, 
, 
.Обозначим число размещений из n по k через
. Для подсчета числа используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из элементов множества , вторым элементом – любой из 
оставшихся в элементов и т.д. Поэтому 
при 
.При
не существует размещений из по , следовательно, 
при ; при 
полагаем 
.Упражнение 1. Показать, что для чисел
выполняются тождества 
, 
.2.Перестановки.Перестановками элементов множества
(или перестановками из n элементов) называются упорядоченная 
-выборка без повторений.Пример 2. Пусть
. Выпишем все перестановки этого множества: 
, 
, 
, 
, 
, 
.Очевидно, что перестановки из
элементов – частный случай размещений из элементов по 
, когда 
. Поэтому их число равно 
3.Сочетания.Сочетанием элементов из
по (или сочетанием из nэлементов по k) называется неупорядоченная -выборка без повторений.Пример 3. Пусть
и . Выпишем все сочетания из этого множества по два: , , .