Основные комбинаторные конфигурации

ГЛАВА 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

1. Среди основных задач комбинаторики выделяют следующие: пересчет, перечисление, классификация и оптимизация. Если требуется определить количество элементов, обладающих некоторым свойством или совокупностью свойств, то это задача пересчета. Если при этом необходимо указать список элементов, то это задача перечисления. Если пересчет приводит к слишком большим числам, то отказываются от соответствующего перечисления и только классифицируют элементы с помощью какого-нибудь соотношения, - и тогда это задача классификации. В некоторых задачах на множестве решений можно ввести функцию величины и относительно этой функции рассматривать задачу оптимизации: найти экстремум функции на определенном множестве объектов, либо указать все или некоторые объекты, для которых достигается экстремальное значение.

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

Набор (множество или кортеж) элементов

составленный из элементов множества , называется выборкой объема k из n элементов, или (n,k –выборкой). Выборки, различающиеся составом элементов, всегда считаются различными.

Выборка называется упорядоченной, если порядок элементов в ней задан (т.е. она представляет из себя кортеж). Две упорядоченные выборки, различающиеся только порядком следования элементов, считаются различными. Если порядок элементов в выборке несуществен, то выборка называется неупорядоченной.

Упорядоченная (n,k)-выборка, в которой элементы могут повторяться, называется (n,k)-размещением с повторениями, или размещением с повторениями из n элементов по k. Если элементы (n,k) -выборки попарно различны, то она называется (n, k)- размещением без повторений, или размещением без повторений из n элементов по k.