Комбинаторные методы перечисления плоских корневых деревьев и путей на решетках тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Тюрнева, Татьяна Геннадьевна

• Тюрнева, Татьяна Геннадьевна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Тюрнева, Татьяна Геннадьевна

Введение.

Глава 1. Комбинаторные числа и полиномы.

§ IЛ .Общая схема построения комбинаторных чисел класса отображений.

§ 1.2. Комбинаторные полиномы разбиений.

§ 1.3. Комбинаторная схема распространения последовательности до матрицы.

§ 1.4. Обобщенные триномиальные коэффициенты.

§1.5. Обобщения треугольника Паскаля.

§1.6. Обобщенные числа Каталана.

§ 1.7. Обобщенные числа Шрёдера.

Глава 2. Перечисление плоских корневых деревьев.

§2.1. Плоские корневые деревья.

§ 2.2. Помеченные плоские корневые деревья Шредера.

2.2.1. Классификация по количеству всех вершин в первом слое.

2.2.2. Классификация по количеству внутренних вершин.

§ 2.3. Плоские непомеченные корневые деревьяКаталана.

2.3.1. Классификация по количеству всех вершин в первом слое.

2.3.2. Классификация по количеству внутренних вершин.

2.3.3. Классификация по высоте.

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

2.4.1. Классификация по числу петель и ребер, выходящих из корня.

2.4.3. Классификация по числу петель.

2.4.4. Классификация по высоте.

Глава 3. Перечисление путей на решетках.

§3.1. Пути Мак-Магона.

§3.2. Пути Моцкина.

§3.3. Пути Дика.

§3.4. Числа Шредера Rn и пути на плоскости.

Введение диссертации (часть автореферата) на тему «Комбинаторные методы перечисления плоских корневых деревьев и путей на решетках»

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

Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [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, \<k<n-\, где суммирование ведется по всем разбиениям натурального числа 2п-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,Р.=С^3 п> 2.

1 L п=I

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

Пусть п\ п\

Ря = Рпх =-A{nkt(uy\u=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. Для чисел г „к справедливы следующие соотношения:

Р = Р 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. Для чисел Каталана Сп имеют место следующие разложения:

С„ = £ 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 <V = I и-1 п-2 и, кроме того, и-А

Числа Н(п,к) названы расщепленными числами Каталана первого рода. В теореме 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 <k<n, п > О, где тп к - число путей (<50.£и) е Н0 с к уровнями.

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

2 л = - /г - к + 2

0, п к, где и ^

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

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

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

1 (2п\ . " А

С„

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

77 + 1

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

Си„ п> 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] и при чтении специальных курсов по перечислительной комбинаторике и комбинаторным методам теории вероятностей для студентов института математики и экономики ИГУ и могут быть использованы в курсе лекций но дискретной математике.

Список литературы диссертационного исследования кандидат физико-математических наук Тюрнева, Татьяна Геннадьевна, 2004 год

1. Айгиер М. Комбинаторная теория. М: Мир, 1982.

2. Андерсон, Джеймс А. Дискретная математика и комбинаторика — М: Изд. дом «Вильяме», 2003.

3. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

4. Бондаренко Б.А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения. Ташкент: Фан, 1990.

5. Воробьев Н.Н. Числа Фибоначчи,- 6-е изд., доп. М.: Наука, 1992.

6. Гасфилд Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский диалект; БХВ - Петербург, 2003.

7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.

8. Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука- 1990.

9. Докин В.Н. О треугольной схеме развития популяций // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. -Вып. 63.-С. 57-59.

10. Докин В.Н., Жуков В.Д., Колокольникова Н.А., Кузьмин О.В., Платонов М.Л. Комбинаторные числа и полиномы в моделях дискретных распределений. Иркутск: Изд-во Иркут. ун-та, 1990.

11. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: Наука. Сиб. издательская фирма РАН, 1994.

12. Жуков В.Д. Рекуррентные формулы для обобщенных А- и В-полиномов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. - Вып. 66. - С. 192-197.

13. Калмыков Г.И. Древесная классификация помеченных графов. М.: ФИЗМАТЛИТ, 2003.

14. Колокольникова Н.А., Кузьмин О.В. Обобщения триномиальных коэффициентов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. - Вып.63. - С. 60-67.

15. Колчин В.Ф. Случайные отображения. М.: Наука, 1984.

16. Колчин В.Ф. Случайные графы. М.: ФИЗМАТЛИТ, 2000.

17. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. -Новосибирск: Наука. Сиб. издательская фирма РАН, 2000.

18. Кузьмин О.В. Рекуррентные соотношения и перечислительные интерпретации некоторых комбинаторных чисел и полиномов // Дискр. математика, Т. 6, Вып. 3, 1994. С. 39-49.

19. Кузьмин О.В., Тюрнева Т.Г. Некоторые свойства и перечислительные интерпретации чисел Моцкина // Тр. XII Байкальской межд. конференции «Методы оптимизации и их приложения». Иркутск, 2001.-С. 87-91.

20. Кузьмин О.В., Тюрнева Т.Г. Числа Каталана, их обобщения и разложения. Сер. Дискретная математика и информатика. Вып.11. -Иркутск: Иркут. ун-т, 1999. 18 С.

21. Кузьмин О.В., Тюрнева Т.Г. Числа Моцкина и перечисление плоских корневых деревьев с петлями // Матем. в вузе: Мат. XIII Межд. научно- метод, конференции (Псков, сент. 2001 г.) СПб.: ППИ, 2001. С. 193-194.

22. Кузьмин О.В., Тюрнева Т.Г. Числа Шредера, их обобщения и приложения // Асимптотич. и перечислит, задачи комбинат, анализа. — Иркутск: Иркут. ун-т, 1997. С. 117-125.

23. Кузьмин О.В., Тюрнева Т.Г. Пути на решётках и некоторые специальные числа // Тр. Вост.- Сиб. зональной межвузовской конф.по математике и проблемам её преподавания в вузе. Иркутск: Изд-во Иркут. пед. ун-та, 1999. -С.159-160.

24. Ландо С.К. Лекции о производящих функциях. М.: МЦНМО, 2002.

25. Оре О. Теория графов. М.: Наука, 1968.

26. Павлов Ю.Л. Некоторые свойства плоских деревьев с висячим корнем. //Дискретная математика, Т. 4, Вып. 2, 1992. -С. 61-65.

27. Павлов Ю.Л. Случайные леса. Петрозаводск: Карельский научи, центр, 1996.

28. Платонов М.Л. Комбинаторные числа класса отображений и их приложения. М.: Наука, 1979.

29. Платонов М.Л. Комбинаторные числа. Иркутск: Иркут. ун-т, 1980.

30. Платонов М.Л. Применение полиномов биномиального типа при решении некоторых перечислительных задач // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. - Вып. 63.-С. 57-59.

31. Риордан Дж. Введение в комбинаторный анализ. М.: Иностр. лит., 1963.

32. Риордан Дж. Комбинаторные тождества. — М.: Наука, 1982.

33. Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во Моск. ун-та, 1985.

34. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

35. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.

36. Тюрнева Т.Г. Обобщения некоторых классов комбинаторных чисел // Третья конференция молодых ученых: Тез. докл. Иркутск: Иркут. ун-т, 1985, - Ч.1.-С.4.

37. Успенский В.А. Треугольник Паскаля М.: Наука, 1979.

38. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

39. Comtet L. Sur le quatricme problcme et les nombres de Schroder // C. R. Acad. Sci. Paris, 1970. - Scrie A, 271, № 19. - P.913-916.

40. Donaghey R., Shapiro L.W. Motzkin numbers // J. Combin. Theory. Ser. A. 1977.-Vol. 23, №2.-P. 291-301.

41. Donaghey R. Restricted plan tree representations of four Motzkin- Catalan equations //J. Combin. Theory. Ser. B. 1977. - Vol. 22, №2 - P. 114-121.

42. Donaghey R. Automorphisms on Catalan trees and bracketing // J. Combin. Theory. Ser. B. 1980. - Vol. 29, № 1. - P. 75-90.

43. Eplett W.J.R. A note about the Catalan triangle // Discrete Math. 1979. -Vol. 25, №3.-P. 289-291.

44. Finucan H.M. Some decompositions of generalized Catalan numbers//Lect. Notes Math. 1982. - Vol. 952. - P. 275-293.

45. Gouyou-Beauchamps D., Vauquelin B. Deux proprictes des nombres de Schroder // Inf. thcor. et Appl. 1988. - Vol. 22, № 3. - P. 361-388.

46. Kremer D. Permutations with forbidden subsequences and a generalized Schroder number // Discrete Math. 2000. - Vol. 218. - P.l21-130.

47. Kettle St.J.G. A class of natural bijections between Catalan families // Lcct. Notes Math. 1982. - Vol.952. - P. 327-348.

48. Olive G. Catalan numbers revisited // J. Math. Anal, and Appl. 1985. -Vol. 111.-P. 201-235.

49. Rogers D.G. Pascal triangle, Catalan numbers and renewal arrays // Discrete Math. 1978. - Vol. 22, № 3. - P.301-310.

50. Rogers D.G. Schroder triangle: three combinatorial problems // Lect. Notes Math. 1977. - Vol. 622. - P. 175-196.

51. Sands A. D. On generalized Catalan numbers // Discrete Math. 1978. — Vol. 21, № 2. - P.219-221.

52. Shapiro L.W. A Catalan triangle // Discrete Math. 1976. - Vol. 14, №1. -P. 83-90.

53. Shapiro L.W., Stephens A. B. Boomstap percolation, the Schroder numbers, and the N-kings problem // Discrete Math. 1991. - Vol. 4, №2. - P.275-280.

54. Sulanke R.A. Catalan path statistics having the Narayana distribution // Discrete Math. 1998. - Vol. 180. - P. 369-389.

55. Sulanke R. A. A recurrence restricted by diagonal condition: generalized Catalan arrays // Fibonacci Quart. 1989. - Vol. 27, № 1. - P. 33-46.

56. West J. Generating trees and the Catalan and Schroder numbers // Discrete Math. 1995. - Vol. 146, №1-3. - P. 247-262.