Оглавление
Введение...............................................................3
Глава І. Комбинаторные числа и полиномы...............................18
£ /. I.Общая схема построения комбинаторных чисел класса
отображений.........................................................18
§ 1.2. Комбинаторные полиномы разбиений.............................23
$ 1.3. Комбинаторная схема распространения последовательности до матрицы...........................................................28
§ 1.4. Обобщенные триномиальные коэффициенты...................... 31
§1.5. Обобщения треугольника Паскаля................................34
§1.6. Обобщенные числа Каталаиа.....................................35
§ 1.7. Обобщенные числа Шрёдера.....................................41
Глава 2. Перечисление плоских корневых деревьев.......................46
§2.1. Плоские корневые деревья......................................46
§ 2.2. Помеченные плоские корневые деревья Шредера..................47
2.2.1. Классификация по количеству всех вершин в первом слое........49
2.2.2. Классификация по количеству внутренних вершин................49
§ 2.3. Плоские непомеченные корневые деревья Каталаиа...............53
2.3.1. Классификация по количеству всех вершин а первом слое........55
2.3.2. Классификация по количеству внутренних вершин................57
2.3.3. Классификация по высоте......................................60
§ 2.4. Плоские корневые деревья Моцкииа с петлями...................64
2.4.1. Классификация по числу петель и ребер, выходящих из корня 66
2.4.3. Классификация по числу петель................................69
2.4.4. Юассификация по высоте.......................................69
Глава 3. Перечисление путей на решетках...............................71
§3.1. Пути Мак-Магона...............................................71
§3.2. Пути Моцкина..................................................72
§3.3. Пути Дика.....................................................77
§3.4. Числа Шредера /?„ и пути на плоскости.........................78
Заключение............................................................82
Список лнгера туры....................................................83
3
Введение
В настоящее время в связи с развитием кибернетики и близких к 11011 разделов науки, существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности.
Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигурации из элементов данного множества [1,2,7,8,10,34,35]. Конфигурации, построенные в соответствии с онредслснш>1ми правилами, называются обычно комбинаторными.
Настоящая диссертационная работа посвящена изучению комбинаторных чисел и полиномов, возникающих при решении перечислительных задач, т.е. задач, в которых необходимо определять число комбинаторных конфигураций данного класса или давать их классификацию, связанную с перечислением.
В работе разрабатываются комбинаторные методы перечисления плоских корневых деревьев и путей на решётках.
При решении указанных задач использованы комбинаторные полиномы — однородные полиномы Белла и Платонова, а также как известные комбинаторные числа, так и новые, введённые автором данной диссертационной работы.
Диссертация состоит из трёх глав, которые разбиты па 15 параграфов. ‘ В главе второй параграфы разбиваются на пункты.
Кратко охарактеризуем содержание отдельных глав диссертации.
В первой главе рассматриваются арифметические треугольники комбинаторного происхождения. Идеи построения и применения арифметических треугольников и пирамид, родственных широко известному
4
треугольнику Паскаля, высказывались многими авторами на протяжении ряда веков.
В 1665г. вышел в свет «Трактат об арифметическом треугольнике» Блеза Паскаля, посвящённый наиболее изящной численной схеме во всей математике - треугольнику Паскаля (см. [37]).
В книгах [4,17] изложены классические и новые арифметические, геометрические и комбинаторные свойства арифметических треугольников и пирамид Паскаля. В монографии [17], в частности, рассмотрены треугольники, построение которых связано с известными последовательностями одпопараметрических комбинаторных чисел: треугольники Люка, Фибоначчи, Каталана, Моцкина, Трнбоначчи (см* работы [5,39, 42, 46, 47, 50, 52, 53]) и др., а также треугольники, построенные из известных двупарамстрических комбинаторных чисел: Стирлинга первого п второго рода, Лаха, присоединённых чисел Стирлинга первого и второго рода п др. Элементы упомянутых выше арифметических треугольников определяются в соответствии с рекуррентными уравнениями и начальными условиями.
В данной диссертационной работе получила развитие идея МЛ. Платонова [30] распространения последовательности одпопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел.
Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств А - и /?—полиномов.
В параграфе 1.1 приводится описание общей схемы построения комбинаторных чисел класса отображений.
В параграфе 1.2 изучаются комбинаторные полиномы разбиений -однородные полиномы Белла и Платонова. Понятие «полином разбиения» -полином от нескольких переменных, определяемый с помощью суммы по
5
различным разбиениям его индекса - введено Беллом. Один из таких полиномов, связанный с производными от композиции функции, Риордаи назвал полиномом Белла. Различные множества полиномов разбиении изучаются в [ 12,17,18,28,31,32].
Однородные полиномы Белла А(п, к; %) имеют вид
«-/1*1
-I
g) = «!£ П S.'fcW'] . я,* - !> /<< п,
п,к 1-І
где g = (g|,#2>■••) - формальные переменные, а суммирование ведется по всем таким наборам _іи) неотрицательных чисел, что
/; + 2г2 +... + („-к + 1 )/•„.*,! = «, г, +г2+... + = к,
т.е. по всем разбиениям натурального числа п на к натуральных слагаемых.
Полиномы Платонова B(n,k;g), сопряженные с однородными полиномами Белла А(п, к; g)> имеют вид
в(»,Л;я)=(-1Г1((*-1)!гЛ‘ )■' В-1 )V,!(2/i-<:-/-| -ОДаф, Ш Г.
ht-lk.n-k i= I
п>2, 1<к<п-\,
где суммирование ведется по всем разбиениям натурального числа 2п-2к на п-к натуральных слагаемых. Дополнительно полагаем
B(n,n;g)=g;\ п> 1.
Переменные £/> і — 1 , участвующие в построении А(п, к; g) и 13(и, к: g), в частности, могут считаться совпадающими с последовательными
производными некоторой функции. Пусть = Если существует ряд
>-\ і!
= такой, что g(g(t)) = f, то для £ = (£,,g2-) м £ = (Si>#2—)
/!
имеет место утверждение.
Утверждение 1.2 [28]. Между производными взаимно-обратных функций, если все они существуют, выполняются соотношения
6
/?(/;,г; Я-) = Л(/і,г;£-), /? > І, І < /• < //.
В параграфе 1.3 излагается разработанная комбинаторная схема распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических чисел. Идея этой схемы основана на применении однородных /(-полиномов Белла и сопряжённых с ними //-полиномов Платонова. Использование известных свойств А- и В- полиномов (см., например, (17, 28, 29]), позволяет получить арифметические треугольники, связанные с заданной
\
последовательностью чисел, и распространить на все члены соответствующих нижних треугольных матриц перечислительную интерпретацию, первоначально установленную для элементов их первого столбца.
Получены новые комбинаторные объекты, названные обобщенными > числами, ряд свойств для которых устанавливается исходя из свойств А - и //-полиномов.
Опираясь на свойства А - и В - полиномов, изучены комбинаторные п аналитические свойства полученных чисел.
В параграфе 1.4 рассматриваются обобщенные триномиальные коэффициенты, которые получаются исходя из общей схемы построения комбинаторных чисел.
В параграфе 1.5 приведены основные понятия и некоторые свойства обобщенного треугольника Паскаля и обобщенной пирамиды Паскаля [4, 9, 17]. Показано, что полученные в работе новые комбинаторные числа, являются частными случаями элементов обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля.
В параграфе 1.6. вводятся и изучаются новые комбинаторные объекты - числа названные обобщенными числами Каталано, п числа Т\Л,
сопряженные с числами Рпк.
- Київ+380960830922