Для удобства, рассмотрим в качестве исследуемого комбинаторного объекта множество B^m наборов из m нулей и единиц. Для этого множества дадим ответы на поставленные вопросы.

Понятно, что множестве наборов из m нулей и единиц содержит ровно 2^m элементов.

Для того, чтобы создать вычислительный процесс, при котором на каждом шаге будет формироваться новый, не встречавшийся ранее, элемент рассматриваемого множества, достаточно заметить, что существует взаимнооднозначное соответствие между числами из 0…2^m1 и наборами 0-1 векторов. Т. е. достаточно первым взять число 0 и его двоичное представление 0, …, 0, а затем просто добавлять по единице, имитируя это на текущем наборе, пока мы не дойдем до набора из одних единиц.

Кроме рассмотренного способа перебора наборов, можно предложить другой алгоритм, который на каждом шаге меняет значение только одной компоненты. Этот алгоритм основан на идее рекурсии.

Фиксируем нулевое значение m-й компоненты и перебираем все наборы длины m1 для оставшихся компонент.

Меняем значение m-й компоненты с 0 на 1. Перебираем наборы длины m1 в обратном порядке.

Приведем таблицу, показывающую процесс перебора наборов длины 4. Столбец it показывает номер текущей итерации, а столбец k_it — номер компоненты, которая подлежит обновлению.

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

Ранее мы рассматривали рекурсивный алгоритм перебора 0-1 наборов. Этот алгоритм позволяет перебирать все наборы B^m так, чтобы каждый следующий набор отличался от предыдущего только в одном разряде. Построенная с помощью этого алгоритма последовательность наборов (приводится в таблице) называется кодом Грея. Вообще, n-разрядный код Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из 2ⁿ n-разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.

Приведем еще один (на этот раз нерекуррентный) алгоритм генерации кодов Грея. Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается единственное число n, которое указывает порядок кода Грея. По ходу выполнения алгоритма мы получим последовательность всех подмножеств n-элементного множества, в которой каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента (наименьшим возможным изменением) — код Грея. При этом каждое подмножество будет представляться бинарной последовательностью B[1], …, B[n].

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

Если мы рассматриваем два каких-либо множества A и B, то будем называть их прямым (декартовым) произведением (A×B) множеств A и B, множество всевозможных упорядоченных пар (i, j), где i A, j B. Мощность же множества, получившегося при декартовом произведении множеств, будет равна произведению мощностей этих множеств.

Более того, мы можем определить прямое произведение любого конечного числа множеств. Например, если рассматривать экземпляры только одного множества, состоящего из двух элементов 0 и 1, то прямое произведение m таких экземпляров будет представлять собой ранее расcмотренное множество B^m.

Итак, рассмотрим прямое произведение k множеств: M₁×M₂×…×M_k. Очевидно, что

|M₁×M₂×…×M_k| = m_i,

где m_i = |M_i| — количество элементов множества M_i.

Пусть множество M_i состоит из целых чисел от 0 до m_i1, i 1:k. Тогда каждый элемент прямого произведения M₁×M₂×…×M_k можно представить как последовательность неотрицательных чисел r₁, r₂, …, r_k, где 0 r_i < m_i.

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

Перестановка n-элементного множества X — это взаимно однозначная функция f: XX. Если для простоты принять X = {1, …, n}, то перестановкой можно назвать упорядоченный набор из n различных чисел, лежащих в промежутке от 1 до n (далее будет рассматриваться именно этот случай).

Обозначим множество всех перестановок множества X через S_n. Понятно, что |S_n| = n!, т. к. на первое место набора можно поставить любое число из n возможных, на второе — любое из n1 оставшихся и т. д. до последней позиции, в которую мы помещаем последний оставшийся элемент: в результате, мы получим произведение, которое и будет являться факториалом n.

Рассмотрим множество M_i из предыдущей части. Пусть каждое M_i будет представлять собой множество чисел от 0 до i1. Обозначим через T_n произведение n таких множеств. Тогда если будет существовать взаимнооднозначное соответствие между S_n и T_n, то мы сможем, в частности, перенумеровать все перестановки S_n. Предъявим механизм перехода от перестановки r₁, …, r_n Sn к элементу t₁, …, t_n Tn. Для этого для любого i 1:n найдем номер позиции s значения i в перестановке (r_s = i) и примем в качестве ti количество элементов меньших i среди r₁, …, r_s−1. А при обратном переходе от элемента к перестановке, можно использовать то, что место любого элемента i (начиная с самого большого) на единицу больше, чем число элементов, предшествующих i, а само это число равно сумме t_i и числа элементов, бОльших i.

Кроме того, каждую перестановку f S_n можно представить с помощью ориентированного графа с множеством вершин X = {1, …, n}, в котором ребро идет от x к у, когда f(x) = y. Легко можно показать, что такой граф состоит из некоторого числа элементарных циклов с различными множествами вершин, которые в сумме дают множество X. Т. е. каждую перестановку мы можем разложить на циклы. Например, рассмотрим перестановку f(1234567) = 7514236 и разобьем ее на циклы:

Введем некоторые обозначения для записи алгоритмов. Элементы перестановки будем запоминать в виде элементов массива P[1], …, P[n]. Обмен значениями переменных будем обозначать через P[i] :=: P[j]. Напомним, что мы рассматриваем только перестановки, заданные на множестве X = {1, …, n}.

На множестве S_n зададим лексикографический порядок:

(x1, …, xn) < (y1, …, yn) существует k 1, такое что x_k y_k и x_l = y_l для каждого l < k.

Аналогично задается антилексикографический порядок:

(x₁, …, x_n) < (y₁, …, y_n) существует k n, такое что x_k > y_k и x_l = y_l для каждого l > k.

Теперь представим алгоритм генерации всех перестановок в антилексикографическом порядке. Заметим, что этот алгоритм является рекурсивным.

Среднее число транспозиций, приходящихся на каждую перестановку, приблизительно равно 1.543, т. е. для порождения n! перестановок используется приблизительно 3.077n! сравнений.

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

Однако, существует еще более быстрый алгоритм генерирования перестановок, он строит последовательность перестановок, в которой каждая следующая образуется из предыдущей с помощью однократной транспозиции соседних элементов. Обозначим через PR[i] булеву переменную, содержащую информацию о том, переносится ли элемент i вперед (PR[i] = true) или назад. Переменнная C[i] будет показывать, какую из возможных ni+1 позиций элемент i занимает относительно элементов i+1, …, n на своем пути вперед и назад. Вот его код:

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.

Перстановки часто встречаются в самых различных областях математики и используются в разных задачах. Например, можно рассмотреть неалгебраическое использование перестановки в следующей экстремальной задаче: даны 2m чисел x₁, …, x_m и y₁, …, y_m, нужно найти такое разбиение чисел на пары (x_i, y_j), при котором значение суммы, составленной из произведений чисел каждой пары, будет наименьшим.

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

Размещение из n элементов по m — это упорядоченный (здесь нам важен порядок) набор из m различных чисел, лежащих в промежутке от 1 до n (т. е. X). Другими словами размещение — это множество с повторениями. Обозначим число его элементов через A_n,m.

Для того, чтобы вычислить значение A_n,m, нужно следовать тем же рассуждениям, что и в случае с перестановками. Тогда получим следующий результат:

A_n,m =

Перебор и нумерация размещений в целом схожи с соответствующими действиями с перестановками. Рассмотрение этих вопросов предлагается читателю в качестве полезного упражнения.

Сочетание из n элементов по m — это неупорядоченный набор (множество) из m различных чисел, принадлежащих множеству X. Обозначим число элементов множества сочетаний через C_n,m.

Т. к. сочетание является неупорядоченным набором, то каждому такому набору соответствует m! размещений (т. е. упорядоченных набора тех же элементов). Тогда получаем, что

C_n,m =

Можно привести некоторые свойства сочетаний:

1.C_n,m = C_n,n−m

2.C_n,m + C_n,m+1 = C_n+1,m+1

3.C_n,m * C_m,k = C_n,k * C_n−k,m−k

Эти свойства следуют из самих определений и проверяются непосредственно.

Теперь приведем алгоритм генерации сочетаний в лексикографическом порядке:

Нумерацию сочетаний можно организовать, используя свойство 2) сочетаний, приведенное выше. Для этого с каждым сочетанием из n по m свяжем вектор из n нулей и единиц. В этом векторе будет m единиц, а числа сочетания будут задавать номера этих единиц. Тогда такому вектору можно, в свою очередь, сопоставить траекторию, в которой единицам соответствуют горизонтальный шаги, а нулям — вертикальные. Тогда формула для номера будет выгляеть, как

num(b[1:n], m) = { если b[n] = 0, то num(b[1:n1], m); если b[n] = 1, то C_n−1,m + num(b[1:n1], m1)},

где b[1:n] — 0-1 вектор из n элементов.

Если в узлах положительного квадранта прямоугольной координатной решетки поместить количество путей от начала координат до этих узлов и повернуть эту решетку так, чтобы начало координат было наверху, то мы получим треугольник Паскаля:

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

(a + b)ⁿ = C_n,ka^kb^n−k

В этой формуле при раскрытии степени алгебраического двучлена коэффициенты при степенях совпадают с числом сочетаний. Исходя из формулы Ньютона значения Cn,m также еще называют биномиальными коэффициентами.

Разбиение n-элементного множества X на k блоков — это семейство Q = {B₁, …, B_k}, в котором B₁ … B_k = X, B_i B_j = Ø, Bi Ø, для 1 i < j k. Обозначим множество всех разбиений множества X на k блоков через Π_k(X), а через Π(X) — множество всех разбиений.

Довольно интересным является вопрос генерирования разбиений множества. Рассмотрим идею алгоритма, отвечающего на этот вопрос, описав ее в рекуррентной форме. Сначала сделаем ряд полезных замечаний. Можно показать, что разбиение Q множества {1, …, n} однозначно определяет разбиение Q_n−1 множества {1, …, n1}, которое получается из Q после удаления элемента n (или пустого блока) из соответствующего блока. Также, если имеется разбиение W = {B₁, …, B_k} множества {1, …, n1}, то можно отыскать все разбиения Q множества {1, …, n}, для которых Q_n−1 = W, т. е. такие разбиения:

B₁ {n}, …, B_k,

…

B₁, …, B_k {n},

B₁, …, B_k, {n}.

Обозначим такую последовательность через E. Тогда сформулируем несложный метод генерирования рабиений: если у нас есть список L_n−1 всех разбиений множества {1, …, n1}, то список L_n разбиений множества {1, …, n} будем создавать, заменяя каждое разбиение Q в списке L_n−1 на соответствующую ему последовательность E. Проиллюстрируем построение списка L_n для n = 1, 2, 3.

Число Стирлинга второго рода S(n, k) — это число разбиений n-элементного множества на k блоков, т. е.

S(n, k) = |Π_k(X)|,

где множество X состоит из n элементов. Например, S(4, 2) = 7.

Любопытны некоторые тождества, связанные с числами Стирлинга второго рода:

S(n, n) = 1, для n 0,

S(n, 0) = 0, для n > 0,

S(n, k) = S(n1, k1) + kS(n1, k), для 0 < k < n

xⁿ = S(n, k)[x]_k, для n 0, где [x]_k = x(x1)…(xk+1).

Первые две формулы очевидны. Доказательство последних формул предлагается читателю в качестве несложного упражнения.

Число Белла Bn — это число всех разбиений n-элементного множества:

B_n = |Π(X)|, где |X| = n.

Рассмотрим несложное рекуррентное соотношение:

B_n+1 = C_i,nB_i

Для доказательства достаточно заметить, что множество всех разбиений множества X = {1, …, n+1} можно разделить на различные классы в зависимости от блока B, который содержит элемент n+1, или в зависимости от множества X \ B. Далее для каждого множества X \ B из {1, …, n} имеется |Π(X \ B)| = B_|X\B| разбиений множества X, которое содержит B в качестве блока. Группируя классы в зависимости от мощности множества X \ B, приходим к требуемому.

Числа Стирлинга первого рода s(n, k) — это коэффициенты при последовательных степенях переменной x в многочлене [x]_k:

[x]_n = s(n, k)x^k.

Для них определяются аналогичные рекуррентные соотношения, что и для чисел второго рода:

s(n, n) = 1, для n 0,

s(n, 0) = 0, для n > 0,

s(n, k) = s(n1, k1) + (n1)s(n1, k), для 0 < k < n.

Разбиение числа (натурального) n на k слагаемых — это последовательность a1, …, ak, такая что

n = a₁ + … + a_k, a₁ … a_k > 0.

Существует довольно простой способ представления разбиения числа — диаграмма Феррерса. Для разбиения a₁, …, a_k она состоит из k строк, которые соответствуют слагаемым разбиения, где i-я строка состоит из a_i точек. Сопряженное разбиение — это разбиение, получающееся при перемене ролями строк и столбцов в диаграмме Феррерса.

Заметим, что с помощью диаграммы Феррерса можно доказать много интересных свойств числа всех разбиений рассматриваемого числа.

Рассмотрим теперь несложный алгоритм генерирования всех разбиений числа. Обозначим через S[1], …, S[d] само разбиение числа, а через R[1], …, R[d] — информацию о том, сколько раз слагаемое S[i] появляется в разбиении.

Производящая функция — это функция, которая позволяет определить явный вид общего члена рассматриваемой числовой последовательности. Так, пусть имеется последовательность {a_n}, для главного члена a которой нужно найти общую формулу. Тогда введем функцию A(x) = a_nxⁿ. Если, используя свойства рассматриваемой последовательности, удастся решить составленные для A(x) уравнения, то можно будет получить искомые элементы последовательности.

Один из примеров применения производящих функций относится к числам Фибоначчи. Они являются решением рекуррентного уравнения F_n+1 = F_n + F_n−1, где F₀ = F₁ = 1.

Рассмотрим производящую функцию F(x) = f_nxⁿ. Она удовлетворяет уравнению F(x) = 1 + x + (F_k−2 + F_k−1)x^k = … = 1 + (x + x²)F(x). Отсюда получаем, что F(x) = (1 x x²)⁻¹. Далее находим разложение 1 x x² = (1 ax)(1 bx), где a = (1 + 5) ⁄ 2, b = (1 5) ⁄ 2. Далее, используя метод неопределенных коэффициентов, получаем F(x) = a^k+1 b^k+1)x^k ⁄ (ab).

Интересно, что предел отношения f_n+1 ⁄ f_n равен a, т. е. «золотому сечению». Также существует связь между числами Фибоначчи и треугольником Паскаля: можно выбрать линии, пересекающие узлы треугольника, так, чтобы сумма всех чисел на одной линии соответствовала числу Фибоначчи.

Другим примером являются числа Каталана. Они появляются в контексте следующей задачи: нужно найти число различных последовательных действий, чтобы вычислить сумму S₀, …, S_n, складывая любые два рядом стоящих числа и результат помещая на их место. Тогда если обозначить искомое число через с_n, то производящая функция будет выглядеть, как С(x) = c_nxⁿ. Следуя аналогичным рассуждениям, как и в случае с числами Фибоначчи, получим, что С(x) = C_2n,nxⁿ ⁄ (n+1).

Для общего представления приведем иллюстрацию для трех множеств A, B и C:

|A_i| = |A_i| |A_i A_j| + |A_i A_j A_k| … + (1)ⁿ⁻¹|A₁ … A_n|.

Доказательство. Будем доказывать теорему по индукции. База индукции очевидно верна. Тогда пусть для A₁, …, A_n−1 выполняется | A_i| = |A_i| |A_i A_j| + |A_i A_j A_k| … + (1)ⁿ⁻²|A₁ … A_n−1|. Если мы применим эту формулу к сумме (A₁ … A_n−1) A_n = (A_i A_n), то получим | A_i A_n| = |A_i A_n| |A_i A_j A_n| + |A_i A_j A_k A_n| … + (1)ⁿ⁻²|A₁ … A_n−1 A_n|. Отсюда уже получаем | A_i| = |( A_i) A_n| = | A_i| + |A_n| | A_i A_n| = |A_i| |A_i A_j| + |A_i A_j A_k| … + (1)ⁿ⁻¹|A₁ … A_n|.