1.9 Комбинаторика

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

1.9.2 Формулы пересчёта числа комбинаторных конфигураций

1.9.3 Перечисление перестановок

1.9.4 Приложения к теории вероятностей

 

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

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

Комбинаторная конфигурация - это расположение конечного множества элементов, удовлетворяющее ряду специальных свойств. К основным комбинаторным конфигурациям относятся сочетания, размещения и перестановки. Ряд других конфигураций может быть сведен к ним. Набор (множество или кортеж) элементов (хi1i2,...,хik ), составленный из элементов множества X=(х12,...,х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 объектов (х12, ..,xk), хi ≥ Xi, может быть осуществлен m1 ∙ m2∙ ... ∙mk способами.
Пример

Автомобильные номера имеют формат AZZZZAA (А - любая буква русского алфавита, кроме Ё, И, Ъ, Ы, Ь, которые не употребляются в номерах; Z - произвольная цифра). Число различных возможных номеров равно произведению 28∙10∙10∙10∙10∙28∙28 = 219520000. Для пересекающихся множеств выполнены более сложные соотношения. Нетрудно убедиться, что для двух множеств X, Y число элементов, принадлежащих хотя бы одному из них, т.е. их объединению, равно

|XY| = |X| + |Y| - |XY|    (2)
(ср. формулу вероятности суммы двух событий в теории вероятностей). Для трех множеств X, Y, Z число элементов, принадлежащих их объединению, равно

|XYZ| = |X|+|Y|+|Z|-|XY|-|X||Z| = |Y||Z|+|X||Y||Z|    (3)

Соотношениям (2) и (3) можно придать другую форму. Если рассмотреть множества X, Y, Z как подмножества универсального множества U, то , откуда

   (4)
Аналогично:

   (5)
Равенства (4) и (5) представляют частные случаи принципа включения и исключения, называемого также принципом решета.
Пусть рассматриваются n свойств Р(1), Р(2)..... Р(n) и N, - число элементов некоторого N-элементного множества, обладающих свойством P(i), Nij - число элементов, обладающих свойствами P(i) и P(j), и вообще Xi1i2...is - число элементов, обладающих свойствами (Рi1),(Рi2), ...(Рis). Тогда число N(0) элементов, не обладающих ни одним из этих свойств, задается знакопеременной алгебраической суммой:

(6)