8.1. Задачи подсчета числа комбинаторных решений

В комбинаторном анализе рассматриваются задачи о расположении элементов в соответствии с точно определенными правилами, выясняется, могут ли быть осущест­влены такие расположения и сколькими способами. Особенностью комбинаторных исследований является то, что в них используются преимущественно три операции: отбор подмножеств некоторого множе­ства, упорядочение и размещение элементов этих подмножеств. Набор элемен­тов a_i1,a_i2,…,a_ir множества A={a₁,a₂,…,a_n} называется выбор­кой объема r из n-множества или (n,r)-выборкой. Выборки бывают упорядоченными и неупорядоченными, с повторениями и без повторений элементов. Любое допустимое расположение элементов в выборке называют решением комбинаторной задачи.

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

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

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

Числом перестановок Р(п) является число различных последовательностей, которые можно составить из п предметов.

Р(n) = п · (п – 1) · … · 2 · 1 = п!

Приведем формулу для числа различных перестановок из n эле­ментов, среди которых r₁ элементов 1-го типа, r₂ элементов 2-го типа, ..., r_k элементов k-го типа:

По данной формуле подсчитывается число неупорядоченных разбиений n-множества на S на r_i-подмножества S_i, i=1÷k такие, что , , для

Неупорядоченная (n,r)-выборка, в которой элементы могут повторяться, называется (n,r)-соче­танием с повторениями. Их число обозначают символом Ĉ(n,r). Если все элементы неупорядоченной (n,r)-выборки различны, она называется (n,r)-сочетанием, а число таких сочетаний обозначается через C(n,r).

При подсчете числа комбинаторных решений используются два правила. Правило суммы: если объект A может быть выбран n способами, а объект B – другими m способами, то выбор «либо A, либо B» может быть осуществлен (n+m) способами. Правило произ­ведения: если объект A может быть выбран n способами и после каждого такого выбора объект B в свою очередь может быть выбран m способами, то выбор «A и B» в указанном порядке может быть осуществлен m·n способами. Применяя оба правила, нетрудно получить формулы для числа перестановок и сочетаний:

Размещения. Операцию размещение можно интерпретировать как отображение множества элементов на множество классов ("ячеек") в соответствии с определенными требованиями. Задачей на размещение будем называть задачу о числе размещений элементов по ячейкам. Раз­нообразие задач на размещение связано с тем, что учитывается вид элементов и их число, вид ячеек и их вместимость, порядок элементов в ячейках. Выделяют следующие классы задач на размещение: (А) элементы различимы, ячейки различимы, (В) элементы неразличимы, ячейки различимы, (С) элементы различимы, ячейки неразличимы, (D) элементы неразличимы, ячейки неразличимы.

Если на характер отображения не на­кладывается ограничений, то типичными задачами класса А являются:

1) размещение n различных элементов по r различным ячейкам, 2) об­разование слов длины r из алфавита в n букв, 3) образование (n,r)-перестановок с повторениями. Число возможных размещений определяет­ся формулой . Взаимно-однозначное отображение накладывает на размещения ограничения, соответственно: 1) каждая ячейка вмещает один и только один элемент; 2) буква внутри слов не повторяется, 3) в перестановках не допускается повторений. В этом случае число возможных размещений вычисляется по формуле .

К задачам класса В можно отнести следующие: а) элементы n- множест­ва размещаются по r ячейкам так, что ни одна ячейка не пуста; б) элементы n-множества размещают по r ячейкам так, что могут быть пустые ячейки. Решение задачи а) сводится к подсчету числа способов провести (r-1) линий в (n-1) промежутках между элементами, кото­рое равно . При решении задачи б) к n-множеству элементов присоединяют r символически "пустых" элемента и подсчитывают число способов провести (r-1) линий в (n-1) промежутках между эле­ментами ().

Общие задачи на размещение из класса С оказываются сложными. При отсутствии ограничений по занятости любой ячейки получен простой результат: число размещений n различных элементов по r одинаковым ячейкам (ячейки могут быть пустыми) равно .

Теория решений за­дач класса D почти не разработана, однако и для этого класса задач получены интересные формулы. Например, число способов размещения n различных элементов по r различным ячейкам с учетом их порядка в ячейках равно . Если среди n элементов есть n₁ элементов 1-го типа, n₂ – элементов 2-го типа,..., n_k – элементов k-го типа, то число различных размещений определяется формулой .

Рассмотрим простейшие задачи подсчета.

Число размещений U(m, n) показывает, сколькими способами можно разместить п предметов по т ящикам. Для каждого из п предметов имеется т вариантов размещения. Следовательно,

U(m, n) = т^п.

Числом перестановок Р(п) является число различных последовательностей, которые можно составить из п предметов. В последовательности всего п позиций. Зафиксируем один предмет. Его можно разместить в одну из п позиций, т. е. имеем п вариантов размещения. Для следующего предмета имеется п – 1 вариантов размещения по незанятым позициям и т. д. Таким образом,

Р(n) = п · (п – 1) · … · 2 · 1 = п!.

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

А(m, n) = т · (т – 1) · … · (т – п + 1) =.

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

С(m, n) ==.

Метод производящих функций. Производящие функции были введены в комбинаторный анализ в качестве средства, позволяющего с боль­шей общностью подходить к комбинаторным задачам перечислительно­го типа. Рассмотрим множество элементов X={x₁,x₂,…,x_n}.

Построим полином вида

где a₀=1, a₁= , a₂= . a_r= есть функции от (n,r)-выборки множества X, r=0÷n.

Каждый бином вида (1+x_kt) отражает две возможности:

элемент x_к вошел в выборку один раз (слагаемое x_kt),

элемент x_k не вошел в выборку ни разу (слагаемое 1).

Если все x_­k=1, то и коэффициенты есть число (n,r)-сочетаний без повторений. Функция называется производящей функцией для последовательности чисел . Она однозначно связана с этой последовательностью.

Дадим общее определение производящей функции. Рассмотрим по­следовательность целых чисел. Ей взаимно однозначно соответствует функция , называемая обыч­ной производящей функцией для последовательности a. Функция вида называется экспоненциальной производящей функцией для последовательности a.

При конечном n функция соответствует неупорядоченным (n,r)-выборкам или функциям от них, а функция -упорядоченным (n,r)- выборкам или функциям от них. С помощью производящих функций можно находить число (n,r)-выборок с заданными свойствами.

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

Пример 1. Рассмотрим задачу о нахождении числа (n,r)-сочетаний с неограниченным числом повторений из множества элементов Для ее решения воспользуемся полиномом вида , каждый сомножитель которого отражает появление элемента "либо 0, либо 2,... либо К,...,либо,.. раз". Полагая все , приведем полином к виду

Функция является производящей функцией для искомого числа сочетаний. Поскольку при |t|<1, f_нп(t)=(1-t)^-n= Из полученной формулы для производящей функции видно, что число (n,r)-сочетаний с неограниченным числом повторений равно . Этот результат согласуется с полученным ранее.

Пример 2. В урне находятся 4 красных, 5 синих и 2 зеленых шара, (а) Сколь­ко существует способов выбора 7 шаров из урны? (б) Сколько существует спосо­бов выбора из урны 7 шаров, если 1 шар красный и 2 синие.

Для части (а) производящая функция имеет вид

(1 + х + х² + х³ + х⁴)(1 + х + х² + х³ + х⁴ + х⁵)(1 + х + х²),

и количество способов выбора 7 шаров равно коэффициенту при х⁷ в разложении этой производящей функции.

В части (б) нужно учесть, что 1 вытянутый шар красный, соответствующий многочлен имеет вид (х + х² + х³ + х⁴), что представляет вытягивание 1, 2, 3 или 4 красных шаров. Точно так же, учитывая, что 2 вытянутых шара синие, соответствующий многочлен должен иметь вид (х²+х³+х⁴+х⁵), что представляет вытягивание 2, 3, 4 или 5 синих шаров. Таким образом, производящий многочлен имеет вид

(х + х² + х³ + х⁴)(х² + х³ + х⁴ + х⁵)(1 + х + х²),

и количество способов выбора 7 шаров равно коэффициенту при х⁷ в разложении производящей функции.

Метод включений и исключений применяется при разделении множества на подмножества, элементы которых обладают определённой совокупностью свойств, а также при подсчёте числа элементов в этих подмножествах. Пусть дано n-множество S некоторых элементов и m-множество свойств P={p₁, p₂, …, p_m}, которыми элементы из S могут как обладать, так и не обладать. Выделим r-выборку свойств {p_i1,p_i2,…,p_ir}. Обозначим через n(p_i1,p_i2,…,p_ir) число элементов множества S, каждый из которых обладает всеми выделенными r свойствами. Отсутствие у элемента свойства p_r будем обозначать . Так, число элементов, обладающих свойствами p₁, p₃, p₅ и не обладающих свойствами p₂, p₄ из выборки свойств P={p₁, p₂, p₃, p₄, p₅} запишется как . Если имеется только одно свойство p, т.е. P={p}, то число элементов n-множества, не обладающих свойством p. Если P={p₁, p₂, …, p_m} – конечное множество свойств, несовместимых друг с другом, то число элементов, не обладающих ни одним из этих свойств, определяется формулой

Если P={p₁, p₂, …, p_m} – конечное множество совместимых между собой свойств, то имеет место формула

известная как формула включений и исключений. Её можно записать и в несколько ином виде:

Область применения метода, включений и исключений довольно широка. С его помощью решаются задачи на подсчет числа перестановок с запретами, задачи теории вероятностей, задачи из теории чисел.

Рассмотрим одну из задач на перестановки с запретами. Ее принято называть задачей о беспорядках. Имеется упорядоченное множе­ство чисел 1,2,..., n. Из них могут быть образованы перестанов­ки a₁, a₂ ,…,a_n . Число всех возможных перестановок из n элементов равно n!. Перестановки, в которых ни один элемент не сохранил своего первоначального места ( , ), называются беспорядками. Число беспорядков из n элементов можно найти по фор­муле включений и исключений:

(₁, , –+),

где означает свойство “ -ый элемент перестановки стоит на -м месте", - множество свойств элементов оста­ваться на своих местах, - число перестановок из элементов, в которых на своих местах стоят элементов. Если элементов из закрепляются на своих местах, то . При этом "неподвижных" элементов из можно выбрать способами, тогда по правилу произведения получим, что . Окончательно имеем фор­мулу для числа беспорядков:

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

Задаче о беспорядках можно дать следующую техническую интер­претацию: пусть проектируется дискретное устройство, состоящее из нескольких узлов и работающее в различных режимах. Каждый режим работы устройства определяется вектором , компо­ненты которого соответствуют состояниям узлов (верхний индекс обо­значает номер узла, нижний - номер состояния). В процессе проек­тирования устройства следует исключить запретные состояния узлов, в которых ни один номер состояния узла не соответствует номеру узла устройства.