Среди основных задач комбинаторики выделяют следующие: пересчет, перечисление, классификация и оптимизация. Если требуется определить количество элементов, обладающих некоторым свойством или совокупностью свойств, то это задача пересчета. Если при этом необходимо указать список элементов, то это задача перечисления. Если пересчет приводит к слишком большим числам, то отказываются от соответствующего перечисления и только классифицируют элементы с помощью какого-нибудь соотношения, - и тогда это задача классификации. В некоторых задачах на множестве решений можно ввести функцию величины и относительно этой функции рассматривать задачу оптимизации: найти экстремум функции на определенном множестве объектов, либо указать все или некоторые объекты, для которых достигается экстремальное значение.
Комбинаторная конфигурация - это расположение конечного множества элементов, удовлетворяющее ряду специальных свойств. К основным комбинаторным конфигурациям относятся сочетания, размещения и перестановки. Ряд других конфигураций может быть сведен к ним. Набор (множество или кортеж) элементов (хi1,хi2,...,хik ), составленный из элементов множества X=(х1,х2,...,хn), называется выборкой объема k из n элементов, или (n, К)-выборкой. Выборки, различающиеся составом элементов, всегда считаются различными. Выборка называется упорядоченной, если порядок элементов в ней задан (т.е. она представляет из себя кортеж). Две упорядоченные выборки, различающиеся только порядком следования элементов, считаются различными. Если порядок элементов в выборке несуществен, то выборка называется неупорядоченной.
Упорядоченная (n, К) - выборка, в которой элементы могут повторяться, называется (n,k) - размещением с повторениями, или размещением с повторениями из n элементов по k. Если элементы (n, k) -выборки попарно различны, то она называется (n, k)-размещением без повторений, или размещением без повторений из n элементов по k. (n, n)-размещения без повторений называются n-перестановками, или перестановками из n элементов.
Неупорядоченные (n, К) - выборки называются сочетаниями: с повторениями или без повторений. Заметим,
что (n, k)-сочетание без повторений - это k-элементное подмножество n-элементного множества.
Если элементы в (n, К) - выборке не могут повторяться, то, очевидно, выполнено неравенство k
≤ n. Для выборки с повторениями возможно условие k > n.
Пример
Выборка (b, d, e) может рассматриваться как (n, 3)-выборка с повторениями, так и без них при
любом n 3; выборка (b, d, e, d) -только как (n, 4)-выборка
с повторениями при n
3.
В комбинаторике можно выделить два основных правила: правило суммы и правило произведения.
Пусть X - конечное множество из n элементов. Тогда говорят, что
один объект из X можно выбрать n способами, и пишут |X| = n. Если X и
Y - непересекающиеся множества и |X|=n, |Y|=m, то |XY|=m+n.
Свойство может быть распространено на большее число множеств.
Пусть {Xi} - система попарно не пересекающихся множеств: Хi
Xj = Ø, если i
j.
Тогда
![]() |
Это правило суммы, или правило альтернатив.
Если объект х ≥ X может быть выбран n способами и после каждого из таких выборов объект у ≥ Y может быть выбран m способами, то выбор упорядоченной пары (х, у) может быть осуществлен m*n способами. Это правило произведения. Оно также распространяется на большее
число множеств. Для системы множеств {Хi}, i = 1, 2,..., k, где |Xi| = mi,
выбор упорядоченной последовательности из k объектов (х1,х2, ..,xk),
хi ≥ Xi, может быть осуществлен m1 ∙ m2∙ ... ∙mk способами.
Пример
Автомобильные номера имеют формат AZZZZAA (А - любая буква русского алфавита, кроме Ё, И, Ъ, Ы, Ь, которые не
употребляются в номерах; Z - произвольная цифра). Число различных возможных номеров равно произведению
28∙10∙10∙10∙10∙28∙28 = 219520000.
Для пересекающихся множеств выполнены более сложные соотношения. Нетрудно убедиться, что для двух множеств X, Y
число элементов, принадлежащих хотя бы одному из них, т.е. их объединению, равно
|X![]() ![]() | (2) |
|X![]() ![]() ![]() ![]() ![]() ![]() ![]() | (3) |
Соотношениям (2) и (3) можно придать другую форму. Если рассмотреть множества X, Y, Z как
подмножества универсального множества U, то , откуда
![]() | (4) |
![]() | (5) |
![]() ![]() | (6) |