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

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

Тюрнева Татьяна Геннадьевна

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

Специальность 01.01.09 — «Дискретная математика и

математическая кибернетика»

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

Иркутск - 2004

Работа выполнена в Иркутском государственном университете

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

Кузьмин Олег Викторович

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

Зуев Юрий Анатольевич;

Защита состоится 22 июня 2004 года в 14.00 часов на заседании диссертационного совета Д 212.074.01 в Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в научной библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина,24).

Автореферат разослан мая 2004г.

Ученый секретарь

кандидат технических наук, Семёнов Александр Анатольевич

Ведущая организация

Нижегородский государственный университет им. Н.И. Лобачевского

диссертационного совета

Общая характеристика работы

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

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

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

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

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

Понятие «полином разбиения» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса -введено Беллом. Один из таких полиномов, связанный с производными от композиции функций, Риордан назвал полиномом Белла. Свойства однородных А- полиномов Белла А(п,к,$ и сопряженных им В- полиномов

Платонова B(n,k,g) изучались в работах М.Л. Платонова1, О.В. Кузьмина2, В.Д. Жукова3.

Комбинаторные А- и В- полиномы успешно применяются при решении целого ряда перечислительных задач. Метод распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел, был предложен М.Л. Платоновым 4. Указанный метод основан на применении однородных А- полиномов Белла и сопряжённых с ними В- полиномов Платонова. Использование известных свойств А— и В— полиномов позволяет получить арифметические треугольники, связанные с заданной последовательностью чисел, и распространить на все члены соответствующих нижних треугольных матриц перечислительную интерпретацию, первоначально установленную для элементов их первого столбца.

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

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

5 6

плоских корневых деревьев и путей на решётках специального вида .

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

2Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. - Новосибирск: Наука. Сиб.

издательская фирма РАН, 2000.

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

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

5Харари Ф., Палмер Э. Перечисление графов - М: Мир, 1977; Donaghey R. Automorphisms on Catalan trees and bracketing // J. Combin. Theory. Ser. B. - 1980. - Vol. 29, №1. - P. 75-90.

6Gouyou-Beauchamps D., Vauquelin B. Deux propnetes des nombres de Schrdder // In£ theor. et Appl. -

1988. - VoL 22. № 3. - P. 361-388.

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

Для изучения деревьев широко используются самые различные методы. Метод ветвящихся случайных процессов, применяемый при изучении графов, являющихся деревьями с помеченными вершинами, рассмотрен в книгах В.Ф. Колчина 7, для других видов деревьев - в работах Ю.Л. Павлова 8. В монографии Г.И. Калмыкова 9 описан новый метод классификации связных помеченных графов (древесная классификация) и основанный на ней новый метод исследования степенных рядов.

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

Основная цель работы состоит в разработке метода распространения

последовательности однопараметрических комбинаторных чисел до

7Колчин В.Ф. Случайные отображения. — М.: Наука, 1984; Колчин В.Ф. Случайные графы. - М:

ФИЗМАТЛИТ.2000.

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

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

'"Rogers D.O.. Schróder triangle: three combinatoria] problems // Lect Notes Math. - 1977. - VoL 622. - P. 175-196; Gouyou-Beauchamps D., Vauquclin B. Deux proprietM des nombres de SchrSder II Inf. tb^OT. Ct Appl. - 1988. - VoL 22, № 3. - P. 361-388; Бондаренко Б.А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения. - Ташкент Фан, 1990.

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

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

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

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

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

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

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

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

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

Отдельные разделы диссертации используются в учебном процессе Института математики и экономики ИГУ (в рамках курса «Перечислительная комбинаторика» и выполнения курсовых и дипломных работ).

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

Публикации. Основные результаты диссертации опубликованы в работах [1]-[6].

Личный вклад автора состоит в развитии метода распространения

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

Структура и объём работы. Диссертационная работа состоит из введения, трех глав и списка литературы из 56 наименований.

Краткое содержание работы

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

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

В параграфе 1.2 изучаются комбинаторные полиномы разбиений -однородные полиномы Белла и Платонова.

Однородные полиномы Белла А(п, к, ф имеют вид

где £ = ) - формальные переменные, а суммирование ведется по

всем таким наборам (г^,гг,... неотрицательных чисел, что

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

Полиномы Платонова сопряженные с однородными

полиномами Белла имеют вид

где суммирование ведется по всем разбиениям натурального числа 2п-2к на натуральных слагаемых. В параграфе 1.3 предложено развитие метода распространения последовательности однопараметрических комбинаторных чисел до матрицы. Метод основан на применении однородных А- полиномов Белла и сопряжённых с ними В- полиномов Платонова. Использование известных свойств А- и В- полиномов позволяет получить арифметические треугольники, связанные с заданной последовательностью чисел, и распространить на члены матрицы перечислительную интерпретацию, первоначально установленную для элементов первого столбца.

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

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

В параграфе 1.6. изучаются новые комбинаторные объекты, полученные описанным в параграфе ,1.3 методом распространения последовательности до матрицы.

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

Известно, что производящая функция смещенных чисел Каталана задается соотношением

Следовательно, обратной ей функцией будет:

Пусть

Р.=Р.1=А{ПМи))=В{ггХи{г)).

Распростр И И

и

я! п\

Для чисел получено явное выражение

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

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

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

Числа Р^ , сопряжённые с числами Р^ имеют следующий явный вид:

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

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

из которых или 1 или 2.

В параграфе 1.7. изучаются обобщенные числа Шредера Для чисел

^пк приводится рекуррентное соотношение; указаны формулы, связывающие присоединенные числа Стерлинга второго рода и числа сопряжённые с обобщенными числами Шредера.

Результаты, изложенные в первой главе, опубликованы в работах [2,4,6].

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

Автором данной диссертации в работах [1,2,3,4] предложен метод классификации плоских корневых деревьев по разным признакам, в качестве последних рассмотрены:

а) степень корня (количество всех вершин в первом слое);

б) количество внутренних вершин;

в) высота.

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

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

В параграфе 2.2 рассмотрены помеченные корневые деревья.

Каждому шредериану СвБ{Ы), состоящему из к блоков, ставится в соответствие помеченное корневое дерево Бси висячими вершинами, построенное по определенному правилу.

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

1) обобщенные числа Шредера $1Л> где - число корневых деревьев D, содержащих ровно к вершин в первом слое;

2) расщепленные числа Шредера первого рода Н„/,, где - число деревьев D высоты ^

3) расщепленные числа Шредера второго рода К,,,,,, где АГ^-число деревьев D с m внутренними вершинами.

Теорема 2.1. Для чисел Кт справедливо рекуррентное соотношение: Кпо=1<Кпт=0 при т + 1>п,

Кпт=(п + т- + (от + 1)АГЯ_1^И>

где п £ 2, 1 ¿т<, п.

Теорема 2.2. Для чисел Нп1 справедливо следующее рекуррентное соотношение:

Из перечислительного смысла чисел и Н^ следует:

= ^^ = ¿^лА' Я >2.

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

В параграфе 2.3 рассмотрена классификация непомеченных корневых деревьев Zcn ребрами, общее число которых совпадает с п-м числом Каталана С„.

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

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

и, кроме того,

d{n,N,m) = d(n-l,N-l,m) + "Z-UN + i, m-l), m > 1,

где D(n,m) - расщепленные числа Каталана второго рода, которые подсчитывают деревья Z с т внутренними вершинами;

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

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

и, кроме того,

п-к

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

следующими соотношениями: Я(и,1) = 5(и,/1), «¿1,

Н(п,3) + Н(п,4) = 5(и,3), п^З.

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

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

Для рассматриваемых чисел выводятся рекуррентные формулы и соотношения, связывающие их с числами Фибоначчи и Стерлинга второго рода.

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

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

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

Пусть - такая последовательность точек из

■7 г

,что:

3) а11(ик) = Л ■ высота точки и, аП(ик)£0, 0

Тогда и0 ...и, называется путем с началом и^ и концом щ и обозначается •••^1-1 )./„• Высотой пути (¿>о •••'^/¡-1 )у0 называется

шахаЛ(и^), 0£к<,1.

Если г е{— 1,0,1}, то (г)^ называется шагом на высоте _/, который мы

назовем подъемом, уровнем или спадом, если Г равно 1, 0 или —1 соответственно.

Пусть Н) - множество всех путей 5, у которых яЛ(и0) = аЛ(м,) = / и ак(ик)>1, 0<к<,1 для каждого Множество Н0 будем называть

множеством путей Моцкина.

Рассматриваем бесконечную нижнюю треугольную матрицу

- число путей с к уровнями.

Теорема 3.1. Для чисел , О^к^п, л20 справедливо

соотношение:

где

кШ(п-к-Г)\

- триномиальные коэффициенты.

Для чисел тП ^ получено следующее рекуррентное соотношение:

'V

с начальным условием

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

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

где С„ - числа Каталана, Мп - числа Моцкина и Яп - числа Шредера.

Введены в рассмотрение числа ¡(п,к,И), перечисляющие пути Моцкина высоты к c к уровнями.

Для чисел 1(п,к,Н) доказан ряд утверждений.

Теорема 3.3. Для чисел 1{п,к,К) справедливы следующие утверждения:

А=0*=0

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

В параграфе 3.4 рассмотрены числа Шредера Я„ и пути на плоскости. Введены в рассмотрение числа для которых установлена

перечислительная интерпретация и получено рекуррентное соотношение.

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

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

- Т.1.-С.4.

2. Кузьмин О.В., Тюрнева Т.Г. Числа Шредера, их обобщения и приложения II Асимптотич. и перечислит. задачи комбинатор. анализа.

- Иркутск: Иркут. ун-тет, 1997. - С. 117-125.

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

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

5. Кузьмин О.В., Тюрнева Т.Г. Числа Моцкина и перечисление плоских корневых деревьев с петлями II Матем. в вузе: Материалы ХШ Межд. научно- метод. конференции. Псков, сентябрь 2001 г. - СПб.: Псковский политех. ин-т., 2001.- С. 193-194.

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

Автореферат

Редакционно - издательский отдел Иркутского государственного университета Лицензия ЛР №020592 от 9.07.97г. 664000, Иркутск, бульвар Гагарина,36

Подписано в печать 5.05. 04. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная. Уч. печ. л.1,25. Уч.-изд.л. 1,12. Тираж 100 экз. Заказ № 100.

Отпечатано в Иркутском Доме печати, 664009, г. Иркутск, ул.Советская, 109.

" 1 4584

Введение.

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

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.