Определим мощность булеана . Булеаном называется множество всех подмножеств некоторого заданного множества А. Если A = { a₁, a₂, ...a_n } , то булеан определится так:

= { Ж, { a₁ } , { a₂ } , ...{ a_n } , { a₁, a₂ } , { a₁, a₃ } , ...{ a₁, a_n } , ...

Как определить { a₁, a₂, a₃ } , число элементов в таком множестве? Допустим, что элемент а_n исключен из А. При этом из булеана исчезнут все выборки, содержащие а_n. А их ровно столько же, сколько останется после исключения а_n. Ведь исключенные выборки могут быть получены присоединением а_n к каждой из оставшихся выборок. Следовательно, уменьшение числа элементов с n до n-1 уменьшает мощность булеана вдвое, что можно записать так:

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

Затем доказать, что правая часть равенства представляет сумму элементов одной строки треугольника Паскаля. Ввиду того, что в треугольнике Паскаля каждый элемент является суммой двух вышележащих, сумма членов с каждой новой строкой удваивается. Вследствие этого за n шагов получается сумма, равная 2ⁿ.

Другой, еще более простой способ: можно противопоставить каждому из составляющих булеан подмножеств n-разрядное двоичное число, где единица заменяет соответственный элемент А_i , присутствующий в подмножестве, а нуль - отсутствующий элемент. Тогда общее число n- разрядных двоичных чисел определится как число размещений с повторениями, т.е. как 2ⁿ.

Над комбинаторными конфигурациями можно выполнять преобразования, описываемые средствами специальных алгебр. Возьмем один уже знакомый нам вид конфигураций: перестановки, т.е. кортежи длины n, составленные из неповторяющихся элементов, число которых тоже равно n. Будем обозначать перестановки буквой П с порядковыми индексами. Допустим П₁ = (1, 2, 3); П₂ = (1, 3, 2) ...

Подстановкой назовем унарную операцию, позволяющую получить одну перестановку из другой. Например, подстановка a выполняет преобразование П₁ в П₂ или П₂ = a (П₁). Подстановки задают сопоставлением двух кортежей в общей паре скобок

Верхний кортеж в паре скобок называют операндом, а нижний - результатом подстановки. Из свойств подстановки очевидным образом вытекает, что это не просто функция. Она всюду определена и сюрьективна и к тому же инъективна, т.е. является взаимно - однозначным отображением или биекцией. Число различных подстановок равно числу перестановок P_n = n!. В это число входит единичная подстановка . Зададимся другой операцией подстановки и применим её к ранее полученной конфигурации П₂ = (1, 3, 2): . В результате получилась новая конфигурация П₃ = (2, 3, 1). Следовательно, композиция подстановок дает новую подстановку g :

b (П₂) = b (a (П₁)) = g (П₁).

Назовем бинарную операцию композиции ab произведением подстановок и исследуем свойства алгебры, которую образует множество подстановок с операцией произведения. Зададимся n = 3 и определим все n! = 3! = 6 возможных при этом подстановок (рис. 13.2).

a (b d ) = b и (a b )d = b .

Проверка коммутативности произведения подстановок дает отрицательный результат: a b № b a . Если набраться терпения, то можно составить таблицу Кэли для операции произведения подстановок. Для нашего примера получается таблица 13.1, из которой видно, что эта алгебра обладает свойствами некоммутативной группы (мультипликативной)

Беспорядком называется подстановка, при которой ни один из элементов конфигурации не остается на своем месте. В рассмотренном примере беспорядков только два: b и e .

Латинским прямоугольником называется конфигурация из m строк и n столбцов. Каждая строка представляет одну перестановку и, в то же время, каждая строка, кроме первой, задает один беспорядок. Латинский прямоугольник называется нормализованным, когда в первой строке все элементы расположены в естественном порядке. При m = n латинский прямоугольник превращается в латинский квадрат.

При m = 2, n = 3, как в рассмотренном примере с перестановками, существует всего два нормализованных латинских прямоугольника (рис. 13.3).

Ненормализованных прямоугольников получается в n! раз больше, так как верхняя строка может быть задана n! = 6 способами. Нормализованных латинских квадратов при n = 3 имеется также два (рис. 13.4). Они отличаются расположением второй и третьей строк. Заметим, что всегда m n , и что в столбцах латинского прямоугольника или квадрата ни один элемент не должен повторяться. Иначе говоря, соответствие между любой парой строк должно являться беспорядком.

Комбинаторику интересуют не сами латинские прямоугольники, а связанные с ними типовые задачи перечисления. Число латинских прямоугольников, состоящих из одной строки, определяется просто. Оно равно числу перестановок из n элементов P_n = n! Из них один прямоугольник будет нормализованным, остальные - нет.

При m = 2 число латинских прямоугольников равно числу беспорядков D_n,0, увеличенному в n! раз, так как первая строка может быть задана n! способами. Число D_n,0 мы определим позже (индекс "0" означает отсутствие элементов, оставшихся на своих местах). При m = 3 определение числа латинских прямоугольников представляет сложную задачу, но с уже известным алгоритмом решения. А вот при m 4 эта задача не решена.

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

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

В это число входят как беспорядки, так и подстановки, беспорядками не являющиеся, которые придется отсеять. Определим W₁ М M, как совокупность всех подстановок, у которых первый элемент остается на своем месте, а остальные переставляются произвольно всеми мыслимыми способами. Подстановки, принадлежащие W₁, не являются беспорядками. Аналогично определим подмножества: W₂, W₃,...W_n, у которых соответственно второй, третий, ... элементы остаются на своих местах. Объединение подмножеств W₁, W₂,... составит множество всех подстановок, не являющихся беспорядками. Число беспорядков выразится разностью

D_n,0 = n! - |W₁ИW₂И...ИW_n|.

Величину мощности объединения можно заменить соответствующим рядом членов по формуле включения и исключения, но мы воспользуемся общим выражением промежуточного члена этой формулы. Промежуточный член состоит из С_n^k слагаемых, а каждое слагаемое равно числу элементов пересечения k множеств. Элементы пересечения должны одновременно принадлежать всем пересекающимся множествам. Значит, этими элементами окажутся подстановки, у которых на своих местах остаются элементы с индексами i₁, i₂,...i_k. Разнообразие подстановок будет получаться только за счет оставшихся n-k индексов. Это в свою очередь означает, что каждое слагаемое в промежуточном члене равно (n-k)!, а весь промежуточный член равен

Ряд, находящийся внутри скобок, в математике известен. При бесконечном количестве членов их сумма сходится к 1/е. Следовательно, при больших n число беспорядков приближенно определяется как D_n,0 @ n!/e.

Выведенная нами формула позволяет решить и более сложную и общую задачу о встречах. Конкретная постановка задачи может быть например следующей. Имеется две колоды из n карт каждая. В первой колоде сохраняется некоторая упорядоченность. Сколькими способами можно уложить вторую колоду так, чтобы затем, при одновременном открывании верхних карт обеих колод, получилось ровно k совпадений?

Математически это означает, что нужно найти число подстановок из n элементов с k совпадениями, т.е. число D_n,k. Искомое число нужно искать как произведение двух сомножителей: числа сочетаний остающихся на месте элементов, т.е. C_n^k, и числа беспорядков, образуемых остальными элементами, т.е. D_(n-k),0

С помощью выведенной нами формулы подобные задачи решаются просто. Например, приняв n=36 и k=4 получим D_36,4 @ 10³⁷.

Содержание