Комбинаторные методы перечисления плоских корневых деревьев и путей на решетках

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

Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1,2,7,8,10,34,35]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными.

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

В работе разрабатываются комбинаторные методы перечисления плоских корневых деревьев и путей на решётках.

При решении указанных задач использованы комбинаторные полиномы — однородные полиномы Белла и Платонова, а также как известные комбинаторные числа, так и новые, введённые автором данной диссертационной работы.

Диссертация состоит из трёх глав, которые разбиты на 15 параграфов. В главе второй параграфы разбиваются на пункты.

Кратко охарактеризуем содержание отдельных глав диссертации.

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

В 1665 г. вышел в свет «Трактат об арифметическом треугольнике» Блеза Паскаля, посвящённый наиболее изящной численной схеме во всей математике — треугольнику Паскаля (см. [37]).

В книгах [4,17] изложены классические и новые арифметические, геометрические и комбинаторные свойства арифметических треугольников и пирамид Паскаля. В монографии [17], в частности, рассмотрены треугольники, построение которых связано с известными последовательностями одпопараметрических комбинаторных чисел: треугольники Люка, Фибоначчи, Каталана, Моцкина, Трибоначчи (смк работы [5,39, 42, 46, 47, 50, 52, 53]) и др., а также треугольники, построенные из известных двупараметрических комбинаторных чисел: Стирлинга первого и второго рода, JTaxa, присоединённых чисел Стирлинга первого и второго рода и др. Элементы упомянутых выше арифметических треугольников определяются в соответствии с рекуррентными уравнениями и начальными условиями.

В данной диссертационной работе получила развитие идея М. Л. Платонова [30] распространения последовательности одпопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел.

Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств, А — и Я-полиномов.

В параграфе 1.1 приводится описание общей схемы построения комбинаторных чисел класса отображений.

В параграфе 1.2 изучаются комбинаторные полиномы разбиенийоднородные полиномы Белла и Платонова. Понятие «полином разбиения» -полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса — введено Беллом. Один из таких полиномов, связанный с производными от композиции функций, Риордан назвал полиномом Белла. Различные множества полиномов разбиений изучаются в [12,17,18,28,31,32].

Однородные полиномы Белла Л (п, кg) имеют вид п, к / =I где g = (g|, g2'" -) ~~ формальные переменные, а суммирование ведется по всем таким наборам (г, г2,., гк+1) неотрицательных чисел, что г, + Ъ +. + {п-к + 1)/-.,+1 = п, г, + г2 +. + гпш = к, т. е. по всем разбиениям натурального числа п на к натуральных слагаемых.

Полиномы Платонова B (n, k-g), сопряженные с однородными полиномами Белла А (п, кg), имеют вид it-k+l г 1 ,.

B{n, k-g) = {-rk{{k-)g*" -ky{ X (-l)" r,!(2/7-A:-/- -l)!^/'[nWl ,.

2n-2k, n-k /= I n>2,.

B (n, n-g) = gп> 1.

Переменные i — 1, участвующие в построении А (п, кg) и В (п, /сg), в частности, могут считаться совпадающими с последовательными a t' производными некоторой функции. Пусть g (t) = 2j ——. Если существует ряд г! Q и' — —-такой, что g (g (t)) = t, то для g = (g, g2.) и & = Я?,-) имеет место утверждение.

Утверждение 1.2 [28]. Между производными взаимно-обратных функций, если все они существуют, выполняются соотношения п) = л (п, г-g-), /7 > 1, 1 < г < /?.

В параграфе 1.3 излагается разработанная комбинаторная схема распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических чисел. Идея этой схемы основана на применении однородных Л-полиномов Белла и сопряжённых с ними 2?-полиномов Платонова. Использование известных свойств Аи В— полиномов (см., например, [17, 28, 29]), позволяет получить арифметические треугольники, связанные с заданной s последовательностью чисел, и распространить на все члены соответствующих нижних треугольных матриц перечислительную интерпретацию, первоначально установленную для элементов их первого столбца.

Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств, А — и /^-полиномов.

Опираясь на свойства, А — и В — полиномов, изучены комбинаторные и аналитические свойства полученных чисел.

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

В параграфе 1.5 приведены основные понятия и некоторые свойства обобщенного треугольника Паскаля и обобщенной пирамиды Паскаля [4, 9, 17]. Показано, что полученные в работе новые комбинаторные числа, являются частными случаями элементов обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля.

В параграфе 1.6. вводятся и изучаются новые комбинаторные объекты — числа Рпк, названные обобщенными числами Каталана, и числа Гпк, сопряженные с числами Рпк.

Число неассоциативных произведений из п фиксированных, линейно упорядоченных сомножителей совпадает с Сп, где Сп — числа Каталана.

С. = 1.

2пЛ п + 1 уП п > 0.

Числа Каталана достаточно хорошо изучены (см., например, [1,2,7,8,34,35,41−44,47−49,51,52,55,56]). Известно, что производящая функция смещенных чисел Каталана задается соотношением.

11 I/ ю u (t) = —-(l-4tyi=ZPt", Р,=1,Р.=С³ п> 2.

1 L п=I.

Следовательно, обратная ей функция равна t (u) — U — U.

Пусть п п.

Ря = Рпх =-A{nkt (uyu=Q = -B[n,-U{t)]t (r п п.

Распространяем указанные последовательности до матриц, полагая к} /с' рпк = — 4[n, k'Mt)l=o= — B[n, k-t (u)]u=Q п п.

II к) /с" рпк = — 4[n, k-t (u)]u=о =^-B[n, k-u (t)l=0 п п.

Для чисел Рпк получено явное выражение к (Ъг—к— п—к п п>2, <�к<�п-.

Теорема 1.1. Для чисел г &bdquo-к справедливы следующие соотношения:

Р = Р 4¦ Р.

1 пк 1 п, к +1 т 1 И-1Д-1 ' «-1.

Рцк ~ 1,/' i=k— i=I + 1 2/1+2 к k + где k>2, n>k-, /?,=!, w>2.

Числа Pnk, названные обобщенными числами Капгалана, имеют следующую перечислительную интерпретацию:

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

Числа Рпк, сопряженные с числами Рпк, имеют следующий явный вид: гк п —к и связаны с числами Фибоначчи соотношением: п-к V.

Рпк.

I Р пк I ~ F п. к = I.

Они имеют следующую перечислительную интерпретацию:

— число представлений п в виде композиции к слагаемых, каждое из которых или 1, или 2.

В параграфе 1.7 изучаются обобщенные числа Шредера Snk. Обычные числа Шредера Sn и их интерпретация широко известны (см., например, [39, 45, 46, 50, 53, 56]). Для чисел Sllk приводятся рекуррентное соотношеЕше и формулы, связывающие присоединенные числа Стирлинга второго рода и числа сопряжённые с обобщенными числами Шредера.

Результаты автора, изложенные в первой главе, опубликованы в работах [20, 22, 36]. Использованные в главе результаты принадлежат лично автору.

Вторая глава посвящена приложениям изучаемых комбинаторных объектов при исследовании некоторых свойств перечисления определённых классов плоских корневых деревьев. С точки зрения классической теории графов деревья — малопривлекательный объект для теоретических исследованийв монографиях по теории графов (см., например, [3, 11, 25, 38]) им редко отводится больше одной главы, однако совсем иное отношение к деревьям в прикладной теории графов. Они играют важную роль в программировании, теории информационных систем, теоретической физике, химии, могут быть использованы в качестве модели описания структур данных, встречаются в биологических задачах, относящимся к деревьям эволюции (см., например, работы [6, 11, 13]).

Для изучения деревьев широко используются самые различные методы. Так метод ветвящихся случайных процессов применяется при изучении графов, являющихся деревьями с помеченными вершинами [15, 16], и других видов деревьев [26, 27]. В монографии [13] предложен новый метод классификации помеченных графов (древесная классификация) и основанный на ней новый метод исследования степенных рядов.

Автором данной диссертации в работах [20, 21, 22] предложен метод классификации плоских корневых деревьев по разным признакам, в качестве последних рассмотрены: а) степень корня (количество всех вершин в первом слое) — б) количество внутренних вершинв) высота.

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

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

В параграфе 2.1 приведены некоторые основные понятия теории графов, используемые в работе.

В параграфе 2.2 рассмотрены плоские помеченные корневые деревья Шредера D. j уКаждому шредериану CeS (N), состоящему из к блоков, ставится в соответствие помеченное корневое дерево D с п висячими вершинами, построенное по определенному правилу.

На основе предложенной схемы получены новые комбинаторные объекты:

1) обобщенные числа Шредера Snk, где Snk — число корневых деревьев.

D, содержащих ровно к вершин в первом слое;

2) расщепленные числа Шредера второго рода Кпт, где Кпт — число деревьев D с т внутренними вершинами;

3) расцепленные числа Шредера первого рода Нnh, где Нnh — число деревьев D высоты h.

Теорема 2.1. Для чисел Кпт справедливо рекуррентное соотношение: = U К"т = 0 ПРИ пг + >п, («+, П ~ О^-М,-! + (>» + где п> 2, 1 < т < п.

Числа Кпт связаны с числами Sn соотношением: п-2 т=О.

Теорема 2.2. Для чисел НпХ справедливо следующее рекуррентное соотношение: и н"+л= X 2 гп.

1 У.

Нп +2″ +| -n-З, «>2.

Из перечисленного смысла чисел Нnh и, следует: л = о.

Установлена связь чисел с присоединенными числами Стерлинга второго рода и с числами Эйлера и Белла.

В параграфе 2.3 рассмотрена классификация плоских непомеченных корневых деревьев Каталана Zen ребрами.

В соответствии с классификацией получены числа C (n, N), где C (n, N) -число деревьев Z, имеющих п ребер среди которых N выходящих из корня.

Теорема 2.3. Для чисел Каталана Сп имеют место следующие разложения:

С&bdquo- =? D (n, m) = 2? cl (n, N, ш), п > 2, от=0 ш=0ЛГ = | п-1 п-2.

Н я/=| n-m-N с, = 5}/(>7,I, «о=Хфд /7?)' п-3 и, кроме того, d (n, N, m) = d (n —, N-, m)+^d (n — 1, tV + i, m -1), m > 1. 0.

Здесь D (n, m) — расщепленные числа Каталана второго рода, которые подсчитывают деревья Z с т внутренними вершинамиd (n, N, m) — число деревьев, имеющих п ребер, среди которых N выходящих из корня, и т внутренних вершин.

Пусть h (n, N, k) — число деревьев Z высоты к, имеющих п ребер, среди которых N выходящих из корня и Н (п, к) — число деревьев Z, имеющих п ребер и высоту к.

Теорема 2.4. Для чисел КаталанаСи имеют место следующие разложения:

А =1 Аг=1.

Числа Н (п, к) названы расщепленными числами Каталана первого рода. В теореме 2.5 выводятся соотношения, связывающие числа Н (п, к) с числами Стирлинга второго рода.

В параграфе 2.4 рассмотрены плоские корневые деревья Моцкина с петлями.

Числа Моцкина являются достаточно хорошо изученным объектом (см., например, [8,17,40,41,47]).

В соответствии с предложенной схемой классификации введены обобщенные числа Моцкина, а также расщешенные числа Моцкина первого и второго рода.

Результаты, изложенные во второй главе, опубликованы в работах [19, 20, 21, 22]. Использованные в главе формулировки и результаты из указанных статей получены в нераздельном соавторстве с О. В. Кузьминым. Предварительные расчеты и таблицы принадлежат лично автору.

В третьей главе широко известные и новые, введённые автором, комбинаторные числа и полиномы используются при перечислении путей на решётках специального типа. Такие пути, начинающиеся обычно в начале координат, являются последовательностями точек целочисленной решетки плоскости с некоторыми ограничениями на приращение координат при переходе от одной точки к следующей. Под шагом пути будем понимать упорядоченную пару чисел, показывающую взаимное расположение соседних точек пути. Таким образом, путь есть последовательность шагов, причем конец одного шага является началом следующего и высоты всех точек неотрицательны. В работах [4, 45, 50] путём подсчёта решётчатых путей на плоскости при некоторых ограничениях получен ряд комбинаторных тождеств.

В параграфе 3.1 рассмотрены пути Мак-Магоиа — пути с шагами (0,1) и (1,0) и приведены геометрические интерпретации нескольких известных комбинаторных чисел.

В параграфе 3.2 рассматриваются некоторые вопросы перечисления путей Моцкина.

Пусть и = (i, j) g Z, и и0, и1,., и1 — такая последовательность точек из.

Z, что:

1) и0 =(0,у0);

2)uk, f=uk+(l, Sk), 8к е {-1,0,1}, 0<к<1;

3) alt (iik) = jk — высота точки u, alt (uk)> 0, 0 < к < I.

Тогда и (). и, называется путем с началом и0 и концом и, и обозначается о • Высотой пути.

0 называется max alt (uk), 0 <к<1.

Если ге{-1, 0, l}, то (г), называется шагом на высоте j, который мы назовем подъемом, уровнем или спадом, если г равно 1, 0 или -1 соответственно.

Пусть Hi — множество всех путей S, у которых alt (u0) — alt (itj) = i и alt (uk)>i, 0</с</ для каждого ик eS. Множество //0 будем называть множеством путей Моцкина.

Рассматриваем бесконечную нижнюю треугольную матрицу М = 0 О, где тп к — число путей (<50.£и) е Н0 с к уровнями.

Теорема 3.1. Для чисел тп к, 0 < к < п, п> 0 справедливо соотношение:

2 л = - /г — к + 2.

0, п к, где и ^.

Kkjj п kl (n-k-l) п-к — п-к = 0(mod2), ti — k = l (mod2). — триномиальные коэффициенты.

Для чисел тпк получено следующее рекуррентное соотношение: п. , т =—т. , ., п > к, к> 1 п, к / /7—1, а — I 5 «к с начальным условием т () 0 = 1.

Числа Каталана С&bdquo-, Моцкина Мп и Шредера Rn могут быть заданы следующим образом:

1 (2п. «А.

С„

1=0 2Ь с i' i о V'.

77 + 1.

Теорема 3.2. Имеют место следующие утверждения:

Си&bdquoп> 0.

Zm, = M — n, k и' k= 0 И k=0 /2 где C" - числа Каталана, Mn — числа Моцкина и Rn — числа Шредера.

Введены в рассмотрение числа l (n, k, h), перечисляющие пути Моцкина длины п, высоты h с к уровнями.

Для чисел l (n, k, h) доказан ряд утверждений.

Теорема 3.3. Для чисел l{n, k, h) справедливы следующие утверждения: И к, h) = тпк, п > 0- li=" ь<].

А=0/-=0.

Ы] f]l (n, 0, h) = C" — h—0 ьм г=0 к=0 /2.

В параграфе 3.3 рассмотрены пути Дика и пути Моцкина с весами. Устанавлено, что обобщённые числа Каталана C (n, N) перечисляют пути Дика, состоящие из 2п шагов N из которых есть подьёмы, выходящие из начала координат.

В параграфе 3.4 изучаются числа Шредера Rn, рассмотренные в [45, 49, 50, 53, 56], и пути на плоскости. Введены в рассмотрение числа Т"к, для которых установлена перечислительная интерпретация и доказано следующее утверждение.

Утверждение 3.2. Числа Тпк удовлетворяют рекуррентному соотношению:

Тпк Tfi-jj^.j.

— i, k+i> где.

Тц=1, T"j=Sn.i, n>2.

Результаты, изложенные в третьей главе, опубликованы в работе [23]. Использованные в главе результаты из указанной статьи получены в нераздельном соавторстве с О. В. Кузьминым. Формулировки и доказательства теорем, приведенные в работе, получены лично автором.

Материалы, представленные в данной диссертации, использовались при чтении спецкурсов в институте математики и экономики Иркутского государственного университета.

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

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

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

3. Перечисление путей на целочисленной решётке: построен треугольник чисел, являющихся разложениями чисел Моцкина, Каталана и Шредера.

По результатам, изложенным в диссертации, имеется 6 публикаций.

Результаты докладывались на Всесоюзных и международных конференциях по дискретной математике (Третья конференция молодых учёных ИГУ, Иркутск, 1985; конференция «Математика и ее приложения», посвященная памяти профессора А. И. Кокорина и 275-летию РАН, Иркутск, 1999; Восточно-Сибирская зональная межвузовская конференция по математике и проблемам ее преподавания в вузе, Иркутск, 1999; XII Байкальская международная конференция «Методы оптимизации и их приложения», Иркутск, Байкал, 2001; XIII Международная конференция «Математика в вузе», Псков, 2001.).

Были сделаны доклады на семинарах ФПК МГУ (г. Москва), кафедры математической статистики и теории вероятностей ИГУ.

В диссертации нумерация формул, утверждений, теорем, таблиц идет по главам.

Список литературы

приводится в алфавитном порядке.

Заключение

.

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

Результаты, полученные в диссертации, использовались при написании монографии [17] и при чтении специальных курсов по перечислительной комбинаторике и комбинаторным методам теории вероятностей для студентов института математики и экономики ИГУ и могут быть использованы в курсе лекций, но дискретной математике.