Исследования по теории перечисления перестановок с ограниченными позициями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АШЕМЙЯ НАУК тмт 5ШСТШТ К4ЕЗРНВТЛКИ им. З.М. ГЛУИКОВА

На правах рукописи

SSBEJl ЕЗ ВЛАДШР САМШОЗЛЧ

УДК 519.I

ЛССЛЕЛОЗАНЛЯ ПО ТЕОРЛЛ ЛВРЕЖЛйШ ПЗРЗСТАНОВОК С ОГРАНИЧЕННЫМ ПОЗЛЦЖМЛ

01.01.09 - Математическая киоернет<1ка

Авторефе par диссертации на соискание ученой степени доктора физико-математических наук

Киев - 1992

Диссертация выполнена в Ростозском на Дону инженерно-, строительном институте

Официальные оппоненты: доктор физико-математических наук,

профессор З.Л.Гирко доктор физико-математических наук, профессор Г.П.Йгорычев доктор физико-математических наук, член-корреспондент АН Украины Н.З.Ш

Ведущая организация: институт математики им. В.А.Стеклова АН К>Р

Зашита диссертации состоится "_"__1992 года в

часов на заседания, специализированного совета Д 0164 501 при институте кибернетики им. В.М.Глушкова АН Украины по адресу; 252550 ГСП, Киев, просп. Академика Глушкова 40.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан "_и__1992г,

Ученый секретарь специализированного совета, кандидат физико-математических наук

В.Ф.Синя вс*

?

I

* ОБ ЛАЯ ХАРШЗРуГСТЛКА РАБОТЫ '1

, . п | • г. , -

~-^~124:гуальность темы. Проблема перечисления перестановок с ограниченными позициями (п.о.п.) возникает в ряде задач комбинаторного.анализа и его приложений. Основные понятия теории таких задач и связанной с ними ладейной л перманентной теории били введены Тушаром, Риорданом, Каплансвям, Твзрбергом, Минком и ;др.' 1

В диссертация предложены новые подходы, поззолившиёс с-одной стороны существенно усилить классические результаты Тушара-Кап-ланского-Риордана с помощью развитом автором полиладейной техники, а с другой стороны - получить практически исчерпывающие результаты в теории перманентов СО,1)-циркулянтов, развитой"в последнее 20-летие Мегаполисом, М.Стейном, П.Стейном и Минком/ 'а' также получить ряд других важных результатов.

Цель работы. I. Перечисление п.о.п., допустимые (запрещенные) позиции которых характеризуются циклическим;!, теп лицевыми и близкими, к ним матрицами инцидентности. •

2. Получение общего алгоритма перечисления п.о.п. с произвольно фиксированным числом циклов.

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

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

Научная новизна. Основными новыми научными результатами, полученными в диссертации, являются:

- ь -

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

2. Построение на основе этого явных формул, одномерных интегральных представлений и формализованного рекуррентного процесса вычисления перманентов циркулянтов порядка н за время 0(*>) без прямого вычисления начальных условий.

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

4. Построение общего алгоритма перечисления п.о.п. с фиксированным числом циклов.

5. Решение обратной задачи перечисления п.о.п. для дихотомических классов.

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

I -циркулянт получается из циркулянта умножением на 1 элементов, расположенных ниже главной диагонали.

• ■>• Оониьнне результаты тмссер'; .¡к.'.л доклп-

- ча 11 и 1" Зоо1: .взкгх се.'лнар.чх по дискретно'! ыигзкегалке и ое ги.илс-.'е.:л'.:и. (:!л.-ко.д, 1"с7;

- на семлнаре ч- лнмитутс г1ийе7н!.;тлк;1 АН Украины чк.З.М. Глуаковп (рук. агм/мпак АК Укра.:ш Д.ЙЛозялеико);

- но ряде :?аооди.-м'; объедлнонного семлнара при лнетлтутв физики им. Л^.,-{цренокого СО АН СССР, Нрасноярзком политехническом институте и др. (сух. проф. Г.П.Згорычез);

- з институте • ^:>блем машиностроения АН Украины;

- в институте математики им. В.А.Стеклова АН СССР;

- систематически но заседаниях семинара по комбинаторному анализу Московского университета (рук. проф. К.А.Рыбников и проф. М.З.Меньшиков).

Публикации. Основное содержание диссертации опубликовано и работах /1-12/.

Объем работы. Диссертация состоит из введения, разделенного на части А и Б, и четырех глав, разбитых на 52 пункта, заключения, списка оснозных обозначений и составляет 359 страниц машинописного текста. Библиография состоит из 158 наименований .

СОДЖАШЕ РАБОТЫ

В часта А введения дан обзор современного состояния теории перечисления п.о.п.

В пункте 0.3 на основании результатов Н. Бебиано^ и З.'Л.Больша-2

кова показано, что перечисление 7- - перестановок из И элементов (с повторениями) с ограниченными позициями сводится к перечислению /7 -перестановок с ограниченными позициями. В части Б введения приведено описание результатов диссертации.

Глава I, Первая глава (п. п. 1.1 - 1.10) посвящена развитию общей теории перечисления п.о.п. с множествами допустимых позиций циркулярного или теплицева типа в том случае, когда матрица А инцидентности, класса п.о.п. является либо к-диагональным циркулянтом 21 «V ^ 1 » теплицевой матрицей вида ,

„ (£-/) , г /

Л ¿¿Р (г,У2>о)> 1

(здесь Р -матрица перестановки, соответствующая циклу (I, 2, .... Щ ). р( )при ¿V П-1 получается из Р после замены единиц ниже главной диагонали нулями,

р°= р(0К Г , ( Р(°) г

1 Ьекапс М Оу! -Мк е/^иа/Сс» о/ рс гта лт /ь // А с ч А\cdh.~ ¡922.-А!Ю1. - Р.

Большаков 3.''.. (/!_,,- . пкрминонтн и их приложения

Вестник МГУ, сер.1- 11-65, 3 .-С.16-22.

При этом (о, 1 ) -матрица А является матрицей инцидентности, или характеристической матрицей класса Зу (А) п.о.п., если для любой перестановки ¿А) ее матрица перестановки Н^~4 .

Поскольку при решении целого ряда перечислительных задач на классах (1\) приходится иметь дело с параметрическим множествами матриц А 1х>,хг) ■■• 1)=^') и в дальнейшем использовать аналитическую зависимость перманента от параметров, в первой главе строится единая теория перманентов указанных и близких к ним классов матриц над полем комплексных чисел.

Как известно, важной работой, внесшей существенный вклад в фундамент единой ^оории перманентов циклических матриц, явилась статья Н.Метрополиса и М. и П.Стейков*, в которой предложен глубокий алгебраический метод построения рекуррентных формул для перманентов (0,1) - циркулянтов в случае, когда единицы в каждой строке образуют серию фиксированной длины. Зтот метод, который мокно было бы назвать "методом характеристических многочленов матриц преобразования" был спустя 16 лет (1985) усовершенствован Х.Минком^ что позволило ему' получить рекуррентные формулы для перманентов (0,1)-циркулянтов, в каждой строке которых единицы образуют несколько серий фиксированной длины. Путем дальнейшего усовершенствования указанного метода в первой главе диссертации получены:

- общая линейная рекуррентная формула для перманентов к -диагональных циркулянтов над полем комплексных чисел;

- линейная рекуррентная формула для перманентов введенных автором центрально-стационарных классов ленточных матриц ' цикли-

У, , ¿¿есп И,, 57<?»>7 Р. Реп/пилепЬ о[ сус&с(е,.

>тга'Ысе^!/ у7. Соп^л . ТЬеотр, А/7. ~ Р, 2У/-224.

МсПС Н- йесиЛГ-епсе /(Jzmu^JJ ^'сг ^с'гтапе'ггА с/'^О-

сиси^п /х // ¿с/каъ А/^. 1 - р. 24/-26У.

ческого и теплицева типа и, в частности,

- однородное линейное разностное соотношение с постоянными коэффициентами для перманентов теплицевых матриц вида

- общая линейная рекуррентная формула для перманентов К -диагональных 2 -циркулянтов;

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

Обратим внимание на то, что ранее метод характеристических многочленов матриц преобразования применялся к вычислению перманентов лишь (0,1) циркулянтов.

Клпчом к получению указанных общих рекуррентных соотношений для перманентов (детерминантов) в обобщенном варианте метода характеристических многочленов явились алгоритмические матрицы метода (матрицы преобразования или алго-матрицы) ¿¿^¡(З) ... к/ , й€С* . явное построение которых дано в пункте 1.1. Заметим, что в предшествовавших работах даже в частном случае (0,1)-циркулянтов матрицы преобразования явно выписаны не были.

В пункте 1.3 на основании результатов пункта 1.1 показано что в случае ¿, = 4 ¿5) является (/^ )-и ассоциирован-

ной с Д1(з1 (й) матрицей, а А1&р^5) - (с-* )-й "перманентно-ассоциированной" матрицей с Л61 (^)^м. ее ( /-1 )-м "перманентным компаундом". Последнее означает, что элементами являются подперманенты порядка /- ( матрицы Мб ¿(о.) .упорядоченные лексикографвческ» по строкам и столбца] В случае ¿й) это обобщает аналогичные результаты для

матриц преобразования, полученные в случае а — и

(ОД)-вектора Л в цитированных, выш» работах^ Структура же матриц И (й} весьма проста. Так, А

(при «¿^■=i ) является сопровождающей матрицей многочлена А*-'- у, ) . - ^ , а С- ¿5) ) - сопровок-даюаей матрицей многочлена ,) Л -+•'■■

Показано, что при = ин = 4 с-,

- . Л п с-г > 'Л , А./ кг *

¿¿т с реп Л <■ С, ^ 'о Шаг (, $ ")),

где I и .V соответственно спектральные радиусы матриц ^^ (&) и М(э (Ю

К-2

Центральным результатом первой главы является формула для

/"->,_ . ...... _......... .....

перманента I -идркулннта г уитапиамаппап а иу пп.1 сг

1.5:

х-/ р ^ /

г*"'«^", (I)

Лг г

где внутреннее суммирование проводится по всем собственным значениям матрицы ¿а) с учетом их кратностей.

Этот результат является новым и принципиально важным и в частном случае перманентов (0,1)-циркулянтов К.7-1, ¿¡=0 или 4 ). Следует отметить, что в ятом частном случае он не был получен ни в работе Н.Петрополиса, М.Стейна и П.Стейна , ни в последующих работах Х.Минка. Это связано с тем, что доказательство формулы (I) существенно использует аналитическую зависимость перманента от элементов циркулянта, что предопределяет необходимость перехода от (0,Г)-циркулянтов к циркулянтам над полем комплексных чисел. Доказательство формулы (I) опирается на серию из II лемм (леммы 1.5-1.15). В отличие от случая Ъ-{ /3 / в доказательстве формулы (I) выжную роль играет то обстоятельство, что число точек слабого превышения ^¿Л) подстановки 7Г& является инвариантом при конгруэнтном ¿/-сдвиге

- 10-

C /i d ^ И ) подстановки

r^ Мс/ (vk м = vi*- J®(

где символом ф обозначено сложение в кольце вычетов по модулю П , так что (лемма 1.6).

пусть Сн{л) С (ё; Я = i CV J •

Положим

I?

Из основного результата (I) следует, что

(к'

где ¿м), I -Л •?, С^) ~ собственные значения матрицы

МС (й) с учетом их кратностей, (^) -матрица

Нп

размера 1x1.

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

Отметим, что детерминантный аналог формулы (I), установленный в пункте 1.3 и имеющий вид

¿¿С I

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

О—'

чениям матрицы . С&) , не носит столь глубокого характера,

как (I), так как, как показано в пункте 1.3, может быть записан в хорошо известной эквивалентной форме

cblCH (5;г) = + —К^Л

(5)

где £ | ^ - корни Л -й степени из 1 .

Заметим, что с вычислительной точки зрения яри больших л формула (4) предпочтительнее, чем (5), поскольку число слагаемых в С») не зависит от Ш . Более того, для вычисления У)-ос степенных сумм 2"Г* , Лу3^- в (I) и (4) с помощью коэффициентов характеристических многочленов алго-матрщ Лв),

¡¿о) можно использовать классические рекуррентные формулы Ньютона, позволяющие, таким образом, организовать формализованный рекуррентный процесс вычисления регг С^(ац) ,

за "".(¡мя ОМ без прямого вычисления начальных

условий.

В пункте 1.6 рассмотрены дуальный случай (й *= 5

и палинтропический случай ( ). Домзано, что если

— £ 1 т0 спектры матриц ^¿С^^о) и {2а ) совпадают, что влечет упрощение формулы (I)

в палинтропическом случав. В частности, установлено равенство

(1р& с (*)(ры с (**» (**

В пунктах 1.7 - 1,8 приведены многочисленные примеры применения формулы (I) . В частности, с общих позиций обобща-. ются различные формулы для перманентов циркулянтов Ямамото, Минка, Немета, Себерри и Шу, Идеса, Прагера и Себберри, Кинга и Паркера, Петрополиса, М.Стейна и П.Стейна и приводятся детер-минантные аналоги этих формул. Отметим, что большинство результатов цитированных авторов обобщается в другом направлении в главе Ш.

В пункте 1.8 дано конструктивное уточнение результатов Стенли, получивиего при применении метода трансферматрицы качественные результаты об энумераторах п.о.п. с множествами до-

пустимых позиций циркулярного или теплицева типа. При этом ;

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

- дан положительный ответ на вопрос !<1инка о том, будет ли полученная им рекуррентная формула для перманентов (0,1) циркулянтов справедлива уже начиная с ¡7=2* (а не с п-2><,г2н--1/1 как установлено Цинком).

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

В пункте 1.9 получены явные формулы и одномерные интегральные представления для перманентов и детерминатов X -диагональных 1 -циркулянтов.

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

К -диагонального циркулянта или теплицевой матрицы. Наряду с традиционными методами изучения этих классов с помощью ладейной техники, во второй главе для них ставится более общая полихроматическая задача о ладьях /12/ и связанная с ней обобщенная проблема Туиара и дается их решение для ряда известных классов. С этой целью, по-видимому, впервые применяется полиладейная техника, важную роль в которой играет функция Твербер-га О", (Л) -сумма подперманентов порядка квадратной матрицы А порядка И . В свою очередь, для вычисления (Д) применяется развитый автором /1,2,'4 / метод индекса размещений .

В пункте 2.1 выясняется комбинаторный смысл обобщенных циклической и линеиной задач о супружеских парах С Мепауе^ ), называемых также циклической и линейной проблемами Тушара. а "перманентной" терминологии, циклическая проблема Тушара индекса К состоит в вычислении перманента

а линейная проблема Тушара индексов ( V )- в вычислении перманента

» - " - С:/

Циклической обобщенной проблемой Тушара (ОПТ) индекса к на-

у

зывается проблема вычисления репС~]п+ 2Г Р1 ), Л

Помимо большей общности (в рамках ОПТ, например, появляется возможность устранения позиций некоторых внутренних диагоналей £из системы ограничений), ОПТ обладает свойством преемственности: из решения ОПТ индекса к>2 немедленно вытекает решение ОПТ меньших индексов. Кроме того, в рамках циклической ОПТ появляется возможность перечисления перестановок с заданным числом точек с/-сдвига по модули И .

Аналогично ставится линейная ОПТ индексов к, £ , состоя-чая в вычислении, р&г _ ¿Р 1

В пункте 2.2 изложены основы ладейной техники и ее роль в решении проблемы Тушара. Заметим, что уже в случае циклической ОПТ индекса 2 традиционная монохроматическая ладейная техника недостаточна.

В пункте 2.3 введены основные понятия полихроматической ладейной техники ( сокращенно, полиладейной техники): полихроматический ладейный многочлен матрицы (ПЛИ) и полихроматический многочлен попаданий (ПМП). Центральным результатом здесь является теорема о связи между ПЛМ и ПМП, обобщающая основное соот-

ношение классической ладейной теории.

Иэ нее вытекает, что роль функции Тверберга в решении (циклической) ОПТ состоят в следующем: если

ок ч.^.*!'-'Л «о

1-1

то

г (г ,

В пункте 2.4 доказана основная лемма, на которой базируется метод индекса размещений. Пусзь ¿Г - некоторое множество (раз-метэние)неколлинеарных единиц квадратной (0,1) -матрицы/^ порядка /7 . Рассматривается множество его максимальных подмножеств вида (¿„ ¿2), ¿¿ьЬ) > -> {, '¿У, ' Число тех из них, которые не являются циклическими, назовем индексом Е (Сис/Е).Проекцией Е(ргЕ) на главную диагональ назовем множество позиций вида {^О , коллинеарных по крайней мере одной из позиций Е . Основная лемма состоит в равенстве

из которого, в частности, следует, что о О* [1-] }

¿¿) = Н ■*#> ¿"«//Г=о . Пусть {.хМ-П . Индикаторной функцией ^ матрицы р] называется число размещений к* неколлинеарных единиц матрицы М-Т , имеющих индекс Эе , с соглашениями

при Ж>к; 1„_1{о>о) = ±, В пункте 2.5 установлена важная формула для ладейного многочлена матрицы Д/ /1,2 /

лежащая в основе применения метода индекса размещений ' к '- 'перечислению п.о.п. В частности, в пунктах 2.16-2.17 получены формулы

, С«,*) I

где Y- yrntjf oe, /-<) v-O,

i, 2i / ■)/ x-■?/>-/ 1

из которых с помощью (8), по-видимому, впервые получены явные представления чисел и (¿J*'** обобщенной линейной задачи

" PtoiOe'me Jes Menajes В пункте 2.18 получены асимптоти-

ческие формулы для ¿jJ5'^,

В основе применения метода индекса размещений к вычислению функции Тверберга G^ циркулянта 7

с, (*) = СЩ (\;ltI+Z ¿fPJ''

лежит следующее естественное обобщение формулы (8) в том случае, когда М-Сп1 />/,..,1). Пусть l^j t\ J -"полихроматическая индикаторная функция" матрицы M-L , означающая число размещений ¿ неколлинеарннх единиц матрицы М-1 , имеющих индекс 36 , ¿j из которых принадлежат диагонали

Р1' 1 ( так что Z £•■= С ). Здесь принадлежность едини-n/-t S-г J

цы диагонали у ассоциируется с ее окраской в цвет у, j-1,1,.,.,7 • Тогда для полихроматического ладейного многочлена матрицы М имеет место формула

нмz с nt?)z ¿«.a,-,¿r,'оД

- 16 -

Следовательно, если Л"-*» С,, ю

ги. 7

сЛс.г«»^ I ("-"Г")*

I . ^ гг е*

X Ь (*г>-> 1г; *) ¿л 4 -Л . М-1

Сопоставление о (б) - (7) приводаг к равенству:

¿СТ

т ■

* К-1 ;*>{*-*>! /]/•$-')е/) С10)

Вполне аналогичные формулы можно записать и для теллицевой матрицы Р ^" ^ ^

Вычисление полихроматической индикаторной функции {¿г, ^'^осуществлено: ~ в п. 2.7 для матриц М~Т„+Р, +

- в п. 2.8 для матриц вида

, где // -подстановочная матрица подстановки F<f^S>J о заданной цикловой структурой (в этих случаях /. является монохроматической индикатор-М-1

ной функцией);

- в п.п. 2.10-2.16 для матриц

где для вычисления/ ра5вит достаточно тонкий комбинатор/7-1

ный метод "стыковки-расцепления гипермассивов";

- в п.2.19 для матрицыгде использован "метод отображения".

Таким образом, во всех указанных случаях решена обобщен-

- П -

ная проблема Тупара.

В-третьей главе диссертации, по-видимому, впервые развивается теория перечисления п.о.п. с фиксированным числом циклов. Основным инструментом теории является так называемый циклический многочлен, или цикломент квадратной матрицы, введенный автором в /8/:

/у? *

" у ' (Ш

где

р/>егк //-^ '.'«¿его-

частичный перманент индекса к матрица /б'У-Число циклов^"-

/У ;

В пункте 3.1 индукцией по числу циклов устанавливается основная лемма о подстановках, состоящая в том, что числа /а//> ¡Vциклов подстановок

^ - / ' 2 ■ - • ") ^ Л'

уф./'* •■•/■' / М--»-' " о -С*.* - ^ » -- ^ "

связаны равенством I~ 1о/1->-„ где -символ

¡¡> " </'

Кронекера.

На основании этого результата в пункте 3.2 устанавливается теорема о разложении цикломента по элементам 1-й строки матрицы $ . Формула разложения имеет вид

I) = г?,, ? ¿^Л ; г ) у- а/г ; ?) +

азу

где Л¿1' - квадратная матрица порядка Яг/ , -получаемая из /) вычеркиванием ¿ -й строки и у -го столбца, матрица, получаемая из единичной матрицы 1 перестановкой с -го и } -го столбцов.

Формулу (13.) можно рассматривать как общий алгоритм перечисления п.о.п. с фиксированным числом циклов. Уто -центральный результат третьей главы.

' В пункте 3.2 устанавливается также возможность разложения цикломента и частичных перманентов по любой строке (столбцу) матрицы Л .

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

В пункте 3.5 вычислены цикломенты и частичные перманенты

- матрицы Т„ /7 , где П - подстановочная матрица подстановки Ж £ Ъь с заданной цикловой структурой. При этом обобщаются известные формулы для ^ ^) и

-матриц ^ ( -1 (при этом получены новые доказательства известных соотношений для чисел Стирлинга и присоединенных чисел Стирлинга I рода ( <)) )

- матриц "у^-рМ 1 ^„-Р » При этом получена рекуррентная формула

-некоторых других матриц.

В пункте З.б развит (в двух вариантах) метод коэффициентов вычисления цикломентов теплицевых матриц и получено' одномерное интегральное представление для циооменга теплицевой матрицы. В частности, получены явная и рекуррентная формулы для GjJ < Ti- ^ Рш; Ю,

В пункте 3.7 метод коэффициентов использован для вычисления цикломента 5-диагонального циркулянта: P^+jiP'^fl-i ¿Pte Рг

Центральным результатом заключительной части главы (п.3.9) является обоснование возможности применения развитого во второй главе метода индекса размещений для. вычисления цикломента (0,1)-матрицы М при некоторых ограничениях на множество ее единиц.

_ y¿¿,¿H) т ¿Ct!, 1+2) T¿J-?.J-0 • s

Пусть /7¿/-I„., 1„ч ----'h-, > I*1'

Для квадратной матрицы J¡ порядка И положим

11£>п Ш^сс > kf) ¿Л) - Л/ ^у, /> < ; 4' И-

Оператор l^^j) , очевидно, сохраняет (не)колаинеарность невы-черкнутых элементов матрицы у/ . Пусть () -некоторая позиция матрицы 4 • При некоторой последовательности итераций оператора j) » когда ( ¿>f ) пробегает некоторое множество неколли неарных ( ^ г* )псзиций, координаты позиции принимают некоторую последовательность значений, и мы будем писать (¿,m)l/\ \ ... Назовем множество

FdFhs)

неколлинеарных позиций, расположенных вне главной диагонали матрицы Д , Т-множеством, если при любой нумерации позиций р- {(i,<,jx)}f., последовательности итераций оператора l(i,f) . в которой ( i ,j ) последовательно пробегает позиции < ^ ^ J¿z¡jz)l'\ 0\,h)U), - > ни один элемент f~ не окажется в какой-либо момент на главной диагонали. В лемме 3,6 показано, что любое множество F ~

- условием является X -

множеством. Однако условие ¿м<у* (или ) не являет-

ся необходимым. Так, в лемме 3.7 установлено, что множество позиций единиц матрицы Р=Р„ (и, следовательно, любое его подмножество) является Т -множеством. Между тем, в нем ( н0 Сп >)„ .

В основе применения метода индекса размещений к вычислении цикломентов лежит утверждение: если А -фиксированное ~Г -мне жество позиций единиц матрицы ^„-1 > т° число ее диагоналей из единиц, содержащих п имеющих К циклов, равно

J

На примере показана существенность условия при котором справедлива формула (14).

С помощью стого основного утверждения в пункте 3.9 получен следующий важный результат: если М -(0,1)-матрица с единичной главной диагональю, то при условии, что множество позиций единиц матрицы М-1 является / -множеством, справедлива формула

+ т 2 (15)

?-/ ре-о

где ЯЯЪ^ЯыЧ?)^*',**..

/=о У /

(ъ)р =• ¿V?-/; .. + Л/, ^гл-л

С помощью формулы (15) вгчислены цикломенты следующих матриц: Р> "} ']_-рС1>, ~Р1-Р^прячеы дяя циклсмента первоп из этих матриц получена и вторая, более компактная формула, имеющая вид

Сус/ (]„ - Т-Р; ?) - /-/; V? *

Далее установлена некоторая модификация утверждения, связанного с формулой (14), позволяющая вычислить методом индекса размещений также цикломенты матриц Д,-р~~1~Р, ~ Р* и дана комбинаторная интерпретация полученных результатов.

В заключительном пункте третье» главы установлен алгоритм перечисления п.о.п. с заданным вычетом декремента соответствующих подстановок по произвольному модулю.

Четвертая глава диссертации посвящена изучению наиболее простых в структурно!--: отношении классов п.о.п., характеристические матрицы которых в каждой строке имеют лишь две единицы. Такие классы называютсядихотоиическими. Поскольку задача перечисления п.о.п. для таких классов достаточно проста (эта задача полностью решена в пункте 4.6, где указан алгоритм перечисления п.о.п. на любом дихотомическом классе), то наиболее содержательной на воем множестве/^/2/дихотомических классов, или на некотором его подмножестве является обратная задача перечисления п.о.п., которая сводится к перечислению матриц подмножества *•„ ( на которых перманент равен и , . Решение обратной задачи перечисления п.о.п. на множествах дихотомических классов оказывается тесно связанным с представляющим и самостоятельный интерес перечислением пар противоречивых перестановок грл различных ограничениях

на их цикловую структуру, 3 связи с ?тиы 4-ая глава по существу разбивается на две подглавы. Пункты посвящены перечислению пар противоречивых перестановок, а пункты 4.5-4.7 -теории дихотомических классов п.о.п.

В первом пункте вводятся некоторые новь'е понятия и устанавливается ряд предварительных соотношений.

Пусть Г - - последовательность неотрицательных

чисел, -о . Класс пар противоречивых перестановок чисел

п будем называть V-редуцированным, если число входящих в него элементов (7?, О" ), для которых перестановка 7/"' имеет цикловую структуру к -/о, ¡¿г> ■ ) • оправляется формулой

Множество {¡(¿з'патлнеких прямоугольников размера кхп назовем р- редуцированны;!, велл совокупность различных пар противоречивых перестановок, соответствующих первым двум строкам всех латинских прямоугольников из ^ является /^-редуцированный классом пар перестановок. Латинские прямоугольники из называются -редуцированными.

Определим последовательность функций <~-0) /) с помощью производящей экспоненты

ехриЖР; ¿) = ^ //А; ,

где f{ц)JSZfl.t^^\

' ' язляется производящей функцией для числа пар (7г,0 ) п^иворечивых перестановок класса с заданным числом циклов в их относительной цикловой структуре:

и-

ЯУЛП/^Г с/(/7,¿г?/

Числа с1(£)Н,к) назовем £~ -присоединенными числами Стерлинга. При этом собственно присоединенным числам Стерлинга первого и второго рода соответствует подходящий выбор последовательности.

При {-I положим так что их производящей

экспонентс-Я; является ехрТ/£Ч • Числа являются естест-

венным обобщением чисел беспорядков С соответствующих выбору

,), ) и перечисляют -редуцированные двустроч-ныэ латинские прямоугольники.

Показано, что естественное требование целочисленности последовательностей , {(/(^¡^.х)} накладывает следую-

щее ограничение на последовательность Г: { } должна быть целочисленной последовательностью. Однако в пункте Ч.З показано, что вполне определенный интерес представляют и последовательности Г , Для которых целочисленна лишь последовательность 1?п!/„ ]

В пункте 4.2 установлен один из центральных результатов главы, состоящий в широком счэтнопараметрическом обобщении классической фсмулы Риордана. Доказано, что

I % I ¿'Я'СГ) = / [ IМ. (П^пи^

' (1б)

где

Более того, показано, что число трехстрочных Р-

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

' " \ ( T Ii

-2K UO

3 луакте 4.3 рассмотрены риил::чн:;е сп&1.л«л4:»а;ал полученных результатов при

(«> 4 ^ Ь U-^ih "¿а = Ii ct-K's, w>i)

ce> K-i-, -

Формула (15) в случае (Ct) янлиетсл собственно *ормуло* Рлорда-Hti, а в случае )- лормуяоч .-¡озера. Формула (17) для всех споичаллзаияй, зклвчая (Q) и ( £ ), является, по-ли диисм/, ново'!. Зо ос лс rij чаях (й ) - (О» список которых лохег сыть прсчольу: и далее'®", пояучени простое формулы для F-беспорядков л J- -прасоецявеникх чисел Стлрляига, ¿уяснен комбинаторный смысл формул (15) - (17). Та;;, в случае (</) формула (15) перечисляет трехстрочные латинские прямоугольнлки, сукна неподвижных элементов первых двух строк которых равна П . Такие латинские прямоугольники названы полуредуиироваиными. Их перечисление мокко трактовать также, как перечисление пар противоречивых перестановок без единичных циклов, если элементы одно;', из перестановок окраиены в два цвета.

Специализация (f ) занимает особое место.

^ Так, могут быть рассмотрены специализации типа а также "смененные" типы специализаций, такле, как (е)-Сс) ; ±./1°у ¿~ имеющие ясный комбинаторный смысл.

и? О 1

С помощью (/) осуществляется "процесс монохроматизации" -переход от перечисления лаглнскнх прямоугольников к перечислению (0,1) матриц классов я , содержащих соответственно 2 и 3 единицы в каждой строке и в каждом столбце. Так, в случае (/ ) формула (16) перечисляет матрицы класса с единичной главной диагональю, а формула (17) - те ке маарицы при условии, что (любые) две другие диагонали из единиц образуют 7 циклов. 3 пункте приводятся используемые в д«ли:гЛ2!ем асимптотические формулы для ¿^(Р) в случаях специализаций (&), (г/) и (/ ).

В пункте 4.5 исследована обратная задача перечисления п.о.п. на следующих множествах дихотомических классов:

- (строчные и столбцовые суммы характеристических матриц классов равны 2);

(следы характеристических матриц классов

равны 0);

- А^^ (характеристические матрицы классов содержат подматрицы классов А *,(*><. и) лишь четных порядков);

- /7*ííJ^^/,)<^ Д? (характеристические матрица классов получаптся из матрицы Я путем замены некоторых неколлинеарных единиц нулями).

В птях случаях получены следующие результаты:

I) } {АеА*

^ _- (Ь . Я«»А + 0( ^Д

где У - постоянная Эйлера.

При этом среднее число перестановок, содержащихся в случайном дихотомическом классе, при задании на равномерного вероятностного распределения определяется формулами ■

М>7,/; = у2 = + ),

где ¿>о как угодно мало при достаточно большом п ,

а дисперсия - формул а 1-я

С г ^ (

где п

I п ~ ' —у/к-''*/*'

Числа ^д^ , , 1Н являются Р -беспорядками соответственно специализаций (а ), (/) и (</.).

МГрел 4)= & ,

где ,(5 , Нп являются числами Г-редуцированных латинских прямоугольников соответственно для специализаций (а,), {/ ) И с с/); бГ„ ОЗ

ОЛ рб ДСЛЯ 8ТСЯ формулой (.17} ПрИ СПСЦИй Лй 3£Ц*ГЛ

с/").

Асимптотические значения среднего и дисперсии совпадают с теми же величинами ьа ^ 1 (,с-точностью до указанных там остаточных членов).

3) При четных И

' г /'

. (.»-п!

{*-/)! 2

I

¿7 ' )

где - члсла Стерлинга первого рода, Jí -постоянная

Эйлера.

(с^- )

С

7 ( i7z-In + l-t(-l) ") ; 2i H / ГГ-НГ-/ Л

«( J) >

= (fc -'<> ^ o/O , М(среаАУ) = (i7U(.,ry(¿¿f*)\¿'f)

/ fti -i / \ *

Заметим, что сравнительно с рассмотренными выше множествами дихотомических классов, множество ^Р) можно харак-

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

3 заключительном пункте 4.7 получен центральный результат второй половины главы. 3 ггом пункте дано полное решение обратной задачи перечлсленля п.о.п. на множестве всех дихотомических классов.

Пусть - класс (ОД)- матриц, eco строчные су..;ш

- СС -

к.>тошх т.^з.чг < (оез огт':,-!,тчс'лич аь столСп-о^ь« с\':-:ш). С кяьс • сом //.„•(' ?/ азеочлмруо*?ея кио> сстио хашг.те^ютйчееких гглу •'.; всох адхсугоклчьзкйх ¿хассо„>. Ооозючии чео-„а Д, * / но.;-миос^зодь :«.;отли класса А ^ \'} , перманент которых т-овзи „?" -Пилсетк }А„ К I ЛС Г2 • Получены слегу мне гс^-.ул

а) яъные формули

б) рекуррентные формулы

¿Аа-Л! ■ —

//

К/ ,-2

с начальным условием Лч, — ;

I * . *

с начальным условием А/,, в которой числа в свою очередь определяются рекуррентном формулой

-г5»-)'

с начальными условиями 3 ~/, ,

- л

в) Асимптотические формулы

^ \7Ттт , . п - 4 / л

к

б>><? как угоаьо мало пои достаючьо бол: ¡.оч . г) Пгл з^дан;:; Д /?/ ъ^вномер^огс ^ г-с: :

дихотомическом классе, определяется формулами

а второй момент - формулой

из которой следует, что

Публикации автора по теме диссертации

1. Шевелев B.C. Об одном методе построения ладейных многочленов и некоторых его приложениях// Комбинаторный анализ, вып.б.-ЯГУ, 1989.-0.124-138.

2. Шевелев З.С. Об одном представлении ладейных многочленов// Успехи математических наук.- 1990.-С. 17Г-172.

3. Шевелев З.С. Основная теорема о последовательности перманентов циркулянтов, порождаемой К -мерным арифметическим вектором// Докл. АН УССР, сер.Л. -1590,S 9.- С.38-42.

4. Шевелев B.C. Суммы подперманентов линейных оболочек подстановочных матриц// Дискретная математика.- I9S0.-T.2, }$.-

С.5 5-80.

5. Шевелев B.C. О характерктичееком многочлена трансферматрицы, возникающей при перечислении перестановок с ограниченными позициями// Вопросы технической диагностики.- Ростов н/Д, 1990.-0.134-138.

5. Шевелев B.C. Некоторые вопросы теории перманентов циклических матриц // Перманенты: теория и приложения / Под ред. Г.П.Егорычева/, Красноярск, 1990.- С.Г09-126.

7. Шевелев З.С. Обобщенная формула Риордана и ее приложения// Докл. ЛН УССР, -IS9I,J£.- С.8-12.

8. Шевелев B.C. 0 циклических многочленах квадратных матриц// Докл.АН УССР.-1991, №3.-С.27-31.

9. Шевелев З.С. Рекуррентные формулы для перманентов и ■•детерминантов тел лицевых матриц// Докл. АН УССР .-1991,^10. С.32-36.

10. Шевелев З.С. Редуцированные латинские прямоугольники и квадратные матрицы с одинаковыми суммами в строках и столбца: Дискретная математика.-1992, т.U, JSI.-C.SI-IIO.

11. Шевелев B.C. Распределение значений перманента в классе дихотомических (0,1)-матрвд // Докл. АН Украины.- 1992, №2.- С. \б-19.

12. Шевелев B.C. Некоторые вопросы теории перечисления перестановок с ограниченными позициями// Теория вероятностей. Математическая статистика. Теоретическая кибернетика (итоги науки ч техники).-I9S2, т.ЗО.-С.//3-/?Я

/

' "f ■