Элементы комбинаторного анализа

Теория

Общие определения комбинаторики

Понятие -выборки

Определение.Пусть заданоrмножеств:, при этом_, тогдаr-выборкойназывается упорядоченная совокупность элементов вида:

(5.1)

Определение.Множество всех выборокназываетсятеоретико-множественным произведениемили произведением r множеств. Обозначается

!!! -выборка не множество, а элемент теоретико-множественного произведения.

В -выборке каждый элемент(компонента) может повторяться, но их порядок фиксирован.

Определение.Две упорядоченные выборкиравныилиэквивалентнытогда и только тогда, когда соответствующие элементы равны

Определение.r-выборка с произвольным порядком размещения компонент называетсянеупорядоченной r-выборкой. Обозначается

Модели комбинаторных конфигураций

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

Определение.Размещением изэлементов поназываетсяупорядоченный наборизразличных элементов некоторого-элементного множества.

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

Определение.Сочетаниемизпоназывается наборэлементов, выбранных из данныхэлементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаютсяодинаковыми, этим сочетания отличаются от размещений.

Определение.Композицией числаназывается всякое представлениев виде упорядоченной суммы целых положительных чисел.

Определение.Разбиением числаназывается всякое представлениев виде неупорядоченной суммы целых положительных чисел.

Общие правила и задачи комбинаторики

Основными и типичными операциями и связанными с ними задачамикомбинаторики являются:

1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, –

составление перестановок;

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

3) образование упорядоченных подмножеств – составление размещений.

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

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

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

Правило суммы. Если и– несвязанные события, и существуетвозможных исходов события, ивозможных исходов события, то возможное число исходов события «или» равно сумме.

Интерпретация. Если элемент можно выбратьспособами, а элемент–способами, то выбор элементаможно осуществитьспособами. Пусть – попарно непересекающиеся множества, , где. Тогда, очевидно, выполняется равенство.

Правило произведения. Если дана последовательность событий свозможными исходами первого,– второго, и т.д., вплоть довозможных исходов последнего, то общее число исходов последовательности k событий равно произведению.

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

Пример. Из 28 костей домино берутся 2 кости. В каком числе комбинаций вторая кость будет приложима к первой?

На первом шаге имеется два варианта: выбрать дубль (7 комбинаций) или не дубль (21 комбинация). В первом случае имеется 6 вариантов продолжения, во втором – 12.

Общее число благоприятных комбинаций равно: .

А всего вариантов выбора 2 костей из 28 равно 378; т. е. при большом числе экспериментов в 7 случаях из 9 (294/378 = 7/9) при выборе 2 костей одна кость окажется приложимой к другой.