§ 17. Денумераторы цикловых классов

В этом параграфе рассматриваются различные способы пересчета подстановок (или, что то же самое, перестановок), обладающих некоторыми свойствами. Процесс перечисления будет рассмотрен позже (гл. IV, § 41).

Напомним формулу (16.10) предыдущего параграфа:

где

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

где суммирование производится по всем -выборкам удовлетворяющим (17.2). Подставляя (17.1) в (17.3), имеем

При суммировании по этой формуле удобно пользоваться некоторыми свойствами экспоненциального -преобразования.

Приведем пример прямого использования (17.4). Пусть

Выборки для которых это (3,0,0), (1, 1,0), (0,0,1). Таким образом,

Отсюда следует, что имеется одна подстановка класса (3,0,0), три подстановки класса (1, 1,0) и две — класса (0,0, 1). Действуя аналогично, можно получить

Решение уравнения Можно решать это уравнение непосредственно последовательным лексикографическим перечислением. Напомним понятие лексикографического порядка.

Лексикографический порядок — это порядок, принятый в словарях, -выборка предшествует -выборке если первых элементов (считая слева направо или справа налево, по соглашению) этих -выборок равны, а элемент первой предшествует элементу второй. Например, (3, 5, 7, 2, 5, 8) предшествует ( предшествует предшествует (0,0,2,18), (3, 8, 2, 0, 0) предшествует (7, 1,3, 0,0) (направление отсчета указано стрелкой).

Разумеется, отношение порядка может быть произвольным: «предшествует», «больше чем», «меньше чем», «содержит» и т. д. Решим лексикографически уравнение

Образуем восемь колонок . В строку (1) помещаем наибольшее возможное число, т. е. (1, 0, 0, 0, 0, 0, 0. 0), в строку (2) — следующее за ним по величине и удовлетворяющее (17.9), т. е. (0, 1, 0, 0, 0, 0, 0, 1), и т. д.

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

Рассмотрим некоторые интересные соотношения. Имеем

так как каждая подстановка входит в точности в один класс, а также

Из (17.4) вытекает тогда

Сравнивая (17.11) в (17.12), получаем

где суммирование производится по всем -выборкам для которых Тождество (17.13) часто называют тождеством Коши.

Напомним формулу (10.53) из § 10:

где и суммирование производится по всем -выборкам, для которых

Очевидно, что от формулы (17.14) можно перейти к (17.4) и обратно с помощью следующего соответствия:

Заметим, что при выводе формулы Бруно (см. (10.46) и можно считать независимыми переменными так как там речь идет о символических биномиальных разложениях. Следовательно,

где суммирование производится по всем «-выборкам для которых Используя экспоненциальное разложение, подобное (10.51), заменяя а на а на на можно получить

Соотношениям (17.16) и (17.17) отвечает аналог (10.46):

где положено

Разложим (17.18) по формуле бинома:

(кликните для просмотра скана)

или

Заменим на по формуле (17.19):

или

Эта формула позволяет вычислить зная и полагая

Продифференцируем (17.17) по

Отсюда получаем

где слева стоит

а справа

Отождествляя коэффициенты при получаем

или

Дадим примеры применения формул (17.23) и (17.29). Найдем считая известными

Пример на формулу (17.29):

Обозначим через сумму членов в содержащих Интегрируя (17.29), имеем

Эта формула дает способ рекуррентного вычисления исходя из Получим этим способом

Тогда

где в суммирование производится по правилу: сумма подобных членов равна одному из них.

Например,

Можно сказать, что есть объединение членов в выражениях

В общем случае (17.38) имеет вид

Рис. 29.

Найдем теперь денумератор подстановок разлагающихся в произведение циклов (без учета числа элементов в цикле). Рассмотрим, например, подстановки пяти элементов. Сколько существует цикловых классов с числом циклов, равным 3? Нетрудно увидеть, что таких классов два (рис. 29): (1,2, 0, 0,0) и (2,0, 1,0,0).

Общая задача сводится к решению системы линейных уравнений:

или

Денумератор классов содержащих в точности циклов (длина которых не фиксируется), можно получить с помощью (17.16) и (17.17). Для этого полагаем

и согласно (17.17)

Так как

то

или

Окончательно для имеем

Пример.

Итак, для имеем соответственно 1 подстановку с 5 циклами, 10 — с 4 циклами, 35 — с 3 циклами, 50 — с 2 циклами, 24 — с 1 циклом.

Рис. 30.

На рис. 30 изображены 10 подстановок с 4 циклами (рис. 30).

Из (17.48) получается рекуррентная формула

Сравним, другой стороны, (17.48) и (10.1) (числа Стирлинга)

Полагаем

Сравнивая (17.53) и (10.3) видим, что

Таким образом, таблица 10.1 дает числа если в ней везде опустить знак

Рис. 31

Подобными рассуждениями можно найти денумератор цикловых классов, состоящих из циклов, длина которых не фиксируется, и не содержащих -циклов, т. е. беспорядков с -циклами. Рис. 31 изображает беспорядок, состоящий из двух циклов.

Положим

тогда в силу (17.17)

и

или

Наконец,

Положим также

Сравнивая коэффициенты в (17.59) и (17.60), имеем

Числа называются «присоединенными числами Стирлинга первого рода».

Подсчитаем для некоторых значений Для этого запишем (17.61) с помощью (17.54):

При имеем

По таблице 10.1 (стр. 48) находим :

В таблице 17.1 приведены значения до Полагаем

Для можно указать непосредственно интересную рекуррентную формулу. Используя (17.62) и (10.9) имеем

Можно также выразить через Для этого рассмотрим (17.57):

Таблица 17.1 (см. скан) Таблица присоединенных чисел Стирлинга первого рода до

или

Отсюда

Подставляя (17.53) и (17.60) в (17.68), получаем

или, возвращаясь к числам Стирлинга первого рода,

С помощью можно вычислить число беспорядков элементов:

Предел суммирования в (17 71) взят, исходя из того, что бес порядок не содержит -циклов.

Выпишем денумераторы четных и нечетных подстановок:

Например, в силу (17.8) имеем

Имеем соответственно одну четную подстановку класса (6, 0, 0, 0, 0, 0), 45 — класса (2, 2, 0, 0, 0, 0), 40 — класса (3, 0, 1, 0, 0, 0), 40 — класса (0, 0, 2, 0, 0, 0), 90 — класса , 144 — класса .

Для нечетных подстановок в силу (17.8) получаем аналогично

Имеем соответственно 15 нечетных подстановок класса (4, 1, 0, 0, 0, 0), 15 — класса (0, 3, 0, 0, 0, 0), 120 — класса (1, 1, 1, 0, 0, 0), 90 — класса (2, 0, 0, 1, 0, 0), 120 — класса (0, 0, 0, 0, 0, 1).

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

Тогда

Отсюда ввиду (17.46)

Например, для

Таким образом, существуют одна четная подстановка 6 элементов, содержащая 6 циклов, 85 — содержащих 4 цикла и 274 — содержащих два цикла.

Денумераторы циклов с предписанным порядком элементов.

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

Пусть задана подстановка класса (0, 0, 1, 1, 0, 0, 0) (рис. 32). По соглашению (см. стр. 89) ее можно записать так:

Это соглашение позволяет не различать циклы

а также

Однако циклы (1427) и (1724) различны.

Рис. 32.

Пересчитаем подстановки элементов, в циклах которых элементы расположены в предписанном порядке. Таким образом, приходим к задаче пересчета классов циклов, составленных из одних и тех же элементов. Например, если это отношение эквивалентности обозначить через то

Так как, очевидно, для -цикла можно образовать ему эквивалентных, то для получения искомого денумератора

достаточно в денумераторе заменить каждое на

Следовательно, подставляя в (17.8), имеем

Сравнивая (17.87) и (10.54), замечаем, что коэффициенты полиномов от с помощью которых образуется этот денумератор, совпадают с коэффициентами полиномов Белла, если в (10.54) заменить на 1, а на

Из (17.87) можно вывести ряд соотношений. Аналогично (17.17) имеем

Обозначим

денумератор, не учитывающий длины циклов, а только их число. Тогда в силу (17.90) имеем

Положим

Легко убедиться, что удовлетворяют дифференциальному уравнению

для которого

( — числа Стирлинга второго рода) — также решения.

Так как

как решения одного и того же дифференциального уравнения с одинаковым начальным условием.

Таким образом,

и

Тем самым легко выписываются с помощью чисел Стирлинга второго рода (таблица 10.2). Для первых значений

В силу (17.96) и (17.98) имеем

Разлагая по формуле бинома, получаем

При этом, как указал Айткен, можно использовать несколько видоизмененный треугольник Паскаля ([36]).

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

Применяем экспоненциальное -преобразование:

Разлагая обе части (17.103) по степеням имеем -

и аналогично

Полагая

получаем соотношение, подобное (17.60); называются присоединенными числами Стирлинга второго рода. Принимают

В таблице 17.2 приведены числа до

Таблица 17.2 (см. скан) Таблица присоединенных чисел Стирлинга второго рода до

Из (17.103) или (17.104) получается рекуррентная формула

Аналогичные результаты можно получить и при других ограничениях на классы подстановок. Различные ограничения на -циклы могут привести к денумератору вида

Например, если фиксировать два первых элемента каждого цикла, то в

УПРАЖНЕНИЯ

(см. скан)