1. Элементы комбинаторики

1.1. Простейшие комбинаторные конфигурации

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

Каждое правило определяет способ построения некоторой конструкции из элементов исходного множества. Полученные конструкции называются комбинаторными конфигурациями.

Цель комбинаторного анализа заключается в изучении комбинаторных конфигураций, алгоритмов их построения, а также решении задач по их перечислению.

1. Основные правила комбинаторики

Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения.

Правило суммы. ПустьA, B– конечные множества,|A| = n, |B| = m.

,

следовательно

.

Комбинированная интерпретация.

Если некоторый объект Aможно выбратьnспособами, а другой объектBможно выбратьmспособами, то выбор "либоA, либоB" можно осуществитьn+mспособами.

Правило произведения. Если мощность|A| = n, |B| = m, то.

Комбинаторная интерпретация.

Если объект Aможно выбратьn способами, а после каждого такого выбора другой объектB можно выбрать (независимо от выбора объектаA)m способами, то пары объектовAиBможно выбратьспособами.

Пусть , и |А| - число элементов множестваA. Составим декартово произведениемножествAиB, т.е. множество пар.

Тогда правило произведения записывается следующим образом:

Пример.Сколько всего существует двузначных чисел?

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то A= {1, 2, ..., 9},B= {0, 1, 2, ..., 9} и_,

2. Выборки элементов без повторений

Простейшими комбинаторными конфигурациями являются перестановки, размещения и сочетания.

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

Пусть. Перестановкой элементов множестваMназывается любой упорядоченный набор элементов, состоящий изnразличных элементовмножестваM.

Перестановки отличаются друг от друга порядком следования элементов.

Теорема. Число всех перестановок равноn!

Доказательство. На первом месте можно разместитьn элементов, на втором – любой из оставшихся (n-1) элементов и т.д. Для последнего места остается 1 элемент. В силу правила произведенияимеем:

.

Пример. Сколькими способами можно разместить 5 студентов при наличии 5 мест.

.

Размещения.

Пусть множество M состоит изnэлементов. Размещением (упорядоченной выборкой) изn элементов поmэлементовназывается любой упорядоченный набор элементов, состоящий изm различных элементов множестваM.

Теорема. Число размещенийnэлементов поm элементов обозначается .. Справедлива формула:

Доказательство. РазмещениеMэлементов множестваMможно представить, как заполнение некоторыхmпозиций элементами множестваM. При этом первую позицию можно заполнитьnспособами, вторую позицию (n-1) способами. Последнюю позицию можно заполнить (n-m+1) способами.

Пример. Из 10 книг производным образом берутся 3 книги и ставятся на полку. Сколько существует способов такой расстановки книг.

.

Заметим, что размещение из nэлементов поn элементам представляет собой перестановку, т.е.:

Сочетания.

Сочетанием (неупорядоченной выборкой) из n элементов поm, где , называется неупорядоченное подмножество множестваM, состоящее изn различных элементов.

Теорема. Число сочетаний изn элементов поmобозначается каки определяется по формуле:

Доказательство. Если объединить размещения изn элементов поm, которые состоят из одних и тех же элементов (то есть не учитывать порядка расположения элементов), то получим сочетание изn элементов поm. Так как для каждого такого сочетания можно получитьn! размещений. Тогдаи, следовательно:

.