Содержание к диссертации
Введение
Глава 1. Комбинаторные числа и полиномы 18
1.1. Общая схема построения комбинаторных чисел класса отображений 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. Числа Шредера Rn и пути на плоскости 78
Заключение 82
Список литературы 83
- Комбинаторные полиномы разбиений
- Обобщения треугольника Паскаля
- Классификация по количеству всех вершин в первом слое
- Плоские корневые деревья Моцкина с петлями
Введение к работе
В настоящее время в связи с развитием кибернетики и близких к ней разделов науки, существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности.
Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1,2,7,8,10,34,35]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными.
Настоящая диссертационная работа посвящена изучению комбинаторных чисел и полиномов, возникающих при решении перечислительных задач, т.е. задач, в которых необходимо определять число комбинаторных конфигураций данного класса или давать их классификацию, связанную с перечислением.
В работе разрабатываются комбинаторные методы перечисления плоских корневых деревьев и путей на решётках.
При решении указанных задач использованы комбинаторные полиномы — однородные полиномы Белла и Платонова, а также как известные комбинаторные числа, так и новые, введённые автором данной диссертационной работы.
Диссертация состоит из трёх глав, которые разбиты на 15 параграфов. В главе второй параграфы разбиваются на пункты.
Кратко охарактеризуем содержание отдельных глав диссертации.
В первой главе рассматриваются арифметические треугольники комбинаторного происхождения. Идеи построения и применения арифметических треугольников и пирамид, родственных широко известному
треугольнику Паскаля, высказывались многими авторами на протяжении ряда веков.
В 1665г. вышел в свет «Трактат об арифметическом треугольнике» Блеза Паскаля, посвященный наиболее изящной численной схеме во всей математике - треугольнику Паскаля (см. [37]).
В книгах [4,17] изложены классические и новые арифметические, геометрические и комбинаторные свойства арифметических треугольников и пирамид Паскаля. В монографии [17], в частности, рассмотрены треугольники, построение которых связано с известными последовательностями одпопараметрических комбинаторных чисел: треугольники Люка, Фибоначчи, Каталана, Моцкина, Трибоначчи (см* работы [5,39, 42, 46, 47, 50, 52, 53]) и др., а также треугольники, построенные из известных двупараметрических комбинаторных чисел: Стирлинга первого и второго рода, Лаха, присоединённых чисел Стирлинга первого и второго рода и др. Элементы упомянутых выше арифметических треугольников определяются в соответствии с рекуррентными уравнениями и начальными условиями.
В данной диссертационной работе получила развитие идея М.Л. Платонова [30] распространения последовательности одпопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел.
Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств Л - и Я-полиномов.
В параграфе 1.1 приводится описание общей схемы построения комбинаторных чисел класса отображений.
В параграфе 1.2 изучаются комбинаторные полиномы разбиений -однородные полиномы Белла и Платонова. Понятие «полипом разбиения» -полином от нескольких переменных, определяемый с помощью суммы по
различным разбиениям его индекса - введено Беллом. Один из таких полипомов, связанный с производными от композиции функций, Риордан назвал полиномом Белла. Различные множества полиномов разбиений изучаются в [12,17,18,28,31,32].
Однородные полиномы Белла Л(п, к; g) имеют вид
A(nAg) = n\ZUg''[r№Y'] , п,к>\, к<п,
tt,к /=|
где g = (g\,g2i—) - формальные переменные, а суммирование ведется по всем таким наборам (г,,г2,...,г_к+1) неотрицательных чисел, что
г, + 2г2 +... + {п-к + 1)/;.,+1 = п, г, + г2 +... + гп_ш = к,
т.е. по всем разбиениям натурального числа п на к натуральных слагаемых.
Полиномы Платонова B(n,k;g), сопряженные с однородными полиномами Белла А(п, к; g), имеют вид
B{n,k;g) = {-\rk{{k-\)\g*-ky{ (-1)^1(2,2-^, -1)!ПаГ'Ь!0"!)Т >
2n-2kji-k ;=|
/7>2, \<к<п-\,
где суммирование ведется по всем разбиениям натурального числа 2п-2к на п-к натуральных слагаемых. Дополнительно полагаем
B(n,n;g) = g;", п>\.
Переменные "/>' — !, участвующие в построении А(п, к; g) и В(п, /с; g), в частности, могут считаться совпадающими с последовательными
» g t' производными некоторой функции. Пусть g(t) = jTd ——. Если существует ряд
/=i г!
— " g и' — —
g(") = Z,-T-, такой, что g(g(t)) = t, то для g = (g{,g2...) и g = (gl,g->,...)
ы\ Г.
имеет место утверждение.
Утверждение 1.2 [28]. Между производными взаимно-обратных функций, если вес они существуют, выполняются соотношения
В параграфе 1.3 излагается разработанная комбинаторная схема
распространения последовательности однопараметрических комбинаторных
чисел до матрицы, составленной из соответствующих двупараметрических
чисел. Идея этой схемы основана на применении однородных Л-полиномов
Белла и сопряжённых с ними /^-полиномов Платонова. Использование
известных свойств А- и В— полиномов (см., например, [17, 28, 29]), позволяет
получить арифметические треугольники, связанные с заданной s
последовательностью чисел, и распространить на все члены
соответствующих нижних треугольных матриц перечислительную интерпретацию, первоначально установленную для элементов их первого столбца.
Получены новые комбинаторные объекты, названные обобщенными
\ числами, ряд свойств для которых устанавливается исходя из свойств А — и
Я-полиномов.
Опираясь на свойства А - и В — полиномов, изучены комбинаторные и аналитические свойства полученных чисел.
В параграфе 1.4 рассматриваются обобщенные триномиальные коэффициенты, которые получаются исходя из общей схемы построения комбинаторных чисел.
В параграфе 1.5 приведены основные понятия и некоторые свойства обобщенного треугольника Паскаля и обобщенной пирамиды Паскаля [4, 9, 17]. Показано, что полученные в работе новые комбинаторные числа, являются частными случаями элементов обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля.
В параграфе 1.6. вводятся и изучаются новые комбинаторные объекты - числа Рпк, названные обобщенными числами Каталана, и числа l\lk, сопряженные с числами Р k.
Число неассоциативных произведений из п фиксированных, лиігейно упорядоченных сомножителей совпадает с Сп, где Сп — числа Каталана
(2пЛ
С ..=
п + \
, п > 0.
\п J
Числа Каталана достаточно хорошо изучены (см., например, [1,2,7,8,34,35,41-44,47-49,51,52,55,56]). Известно, что производящая функция смещенных чисел Каталана задается соотношением
u(t) = \-Ul-4t/>=±r„t\ Р,=1, Р„=С„_„ «>2.
Следовательно, обратная ей функция равна
t(u) = U — U
Пусть
Р = Р
1 п L п\
— A[n,l;u(t)]l=0 = —B[n,\;t(u)]lf^.
Р* = ,. =-А[пМи)]и=0 = -B[n9\;u(t)]t__u.
Распространяем указанные последовательности до матриц, полагая
к} /с'
pnk = — An,k;u(t)l=0= — B[n,k;t(u)]ll=0
т п\
~ ' /с'
рпк = — An,k\Kii)\t=() =^-B[n,k;u(t)l=0
Для чисел Рпк получено явное выражение
р.
к (1п-к-\Л
п—к
п>2\ \<к<п-\.
Теорема 1.1. Для чисел Рпк справедливы следующие соотношения:
P = P + P
1 nk L n,k + \ T l n-\,k-\ '
* nk ~ / J »-l./'
^л / , l пі >
* + l 2/1+2
к k + \
ГДе^>2, «>*-!, /?,=!, ,=/^=(^,, w>2.
Числа Ри/1, названные обобщенными числами Каталана, имеют следующую перечислительную шітерпретацшо:
Рпк - число сумм произведений, состоящих из к слагаемых,
содержащих в совокупности п фиксированных множителей, взятых из алгебры с неассоциативным умножением.
Числа Рпк, сопряженные с числами Pnk, имеют следующий явный вид:
(к п — к
^ =(-1Г*
V и связаны с числами Фибоначчи соотношением:
Y \р = F
/ . \г пк \ ' п .
к = I Они имеют следующую перечислительную интерпретацию:
"пк
- число представлений п в виде композиции к слагаемых, каждое
из которых или 1, или 2.
В параграфе 1.7 изучаются обобщенные числа Шредера Snl(. Обычные числа Шредера Sn и их интерпретация широко известны (см., например, [39, 45, 46, 50, 53, 56]). Для чисел Snfc приводятся рекуррентное соотношєепіє и
формулы, связывающие присоединенные числа Стирлинга второго рода и числа сопряжённые с обобщенными числами Шредера.
Результаты автора, изложенные в первой главе, опубликованы в работах [20, 22, 36]. Использованные в главе результаты принадлежат лично автору.
Вторая глава посвящена приложениям изучаемых комбинаторных объектов при исследовании некоторых свойств перечисления определённых классов плоских корневых деревьев. С точки зрения классической теории графов деревья - малопривлекательный объект для теоретических исследований; в монографиях по теории графов (см., например, [3, 11, 25, 38]) им редко отводится больше одной главы, однако совсем иное отношение к деревьям в прикладной теории графов. Они играют важную роль в программировании, теории информационных систем, теоретической физике, химии, могут быть использованы в качестве модели описания структур данных, встречаются в биологических задачах, относящимся к деревьям эволюции (см., например, работы [6, 11, 13]).
Для изучения деревьев широко используются самые различные методы. Так метод ветвящихся случайных процессов применяется при изучении графов, являющихся деревьями с помеченными вершинами [15, 16], и других видов деревьев [26, 27]. В монографии [13] предложен новый метод классификации помеченных графов (древесная классификация) и основанный на ней новый метод исследования степенных рядов.
Автором данной диссертации в работах [20, 21, 22] предложен метод классификации плоских корневых деревьев по разным признакам, в качестве последних рассмотрены:
а) степень корня (количество всех вершин в первом слое);
б) количество внутренних вершин;
в) высота.
В данной работе представлена выборка наиболее известных, на наш взгляд, к настоящему моменту числовых последовательностей, связанных с плоскими корневыми деревьями. Надеемся, что она достаточно представительна т.к. отражает три основных типа плоских корневых деревьев: помеченные (последовательность Шредера), с петлями (последовательность Моцкина) и непомеченные (последовательность Каталана).
В соответствии с предложенной классификацией получены новые комбинаторные числа, исследованы их свойства и указаны перечислительные интерпретации.
В параграфе 2.1 приведены некоторые основные понятия теории графов, используемые в работе.
В параграфе 2.2 рассмотрены плоские помеченные корневые деревья Шредера D.
Каждому шредериану CgS(N), состоящему из к блоков, ставится в
соответствие помеченное корневое дерево D с п висячими вершинами, построенное по определенному правилу.
На основе предложенной схемы получены новые комбинаторные объекты:
1) обобщенные числа Шредера Snk, где Snk - число корневых деревьев
D, содержащих ровно к вершин в первом слое;
расщепленные числа Шредера второго рода Кпт, где Кшп - число деревьев D с т внутренними вершинами;
расцепленные числа Шредера первого рода Нnh, где Нnh - число деревьев D высоты h.
Теорема 2.1. Для чисел Кпт справедливо рекуррентное соотношение:
К„о = U К„т = ПРИ пг + \>п,
где п>2, 1 < т < п.
Числа Кпт связаны с числами S„ соотношением:
п-2
5>2Х„ п>2
т=0
Теорема 2.2. Для чисел НпХ справедливо следующее рекуррентное соотношение:
"-.,=. Нп+2"1-п-3, п>2.
>-А1)
Из перечисленного смысла чисел Hnh и Sn, следует:
Л = 0
Установлена связь чисел Кпт с присоединенными числами Стирлипга
второго рода и с числами Эйлера и Белла.
В параграфе 2.3 рассмотрена классификация плоских непомеченных корневых деревьев Каталана Zen ребрами.
В соответствии с классификацией получены числа C(n,N), где C(n,N) -число деревьев Z, имеющих п ребер среди которых tV выходящих из корня.
Теорема 2.3. Для чисел Каталана Сп имеют место следующие разложения:
С„ = D(n, т) = X d(n, N, т), п > 2,
m=0 m=0/V = l
п-\ п-2
и, кроме того,
n-m-N
d(n,N,m) = d(n-l,N-l,m) + ^Td(n-1,N+ і,т — І), т > 1.
Здесь D(n,m) -расщепленные числа Каталана второго рода, которые подсчитывают деревья Z с т внутренними вершинами; d(n,N,m) - число
деревьев, имеющих п ребер, среди которых N выходящих из корня, и т внутренних вершин.
Пусть h(n,N,k) - число деревьев Z высоты к, имеющих п ребер, среди
которых N выходящих из корня и Н(п,к) — число деревьев Z, имеющих /7 ребер и высоту к.
Теорема 2.4. Для чисел КаталанаСи имеют место следующие разложения:
С„ =ХН(п,к) = ^^К'г^,к), „>/,
A=l k=l N = [
п—\ п-2
к=\ Ы\
и, кроме того,
п-к
/7(и,1Д) = ^Л(и-1,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 рассматриваются некоторые вопросы перечисления путей Моцкгша.
Пусть u = (i,j)GZ , и u0,iti,...,iil - такая последовательность точек из
Z , что:
1) н0=(0,у0);
2)и4+|=и,+(1Л), , є {-1,0,1}, 0
3) alt{uk ) — jk - высота точки u, ali(uk) > 0, 0 < k < I.
Тогда uQ ... и, называется путем с началом и0 и концом и, и
обозначается у0 . Высотой пути /0 называется
maxalt{iik), 0<к<1.
Если г є {-1, 0, і}, то (г), называется шагом на высоте j, который мы
назовем подъемом, уровнем или спадом, если г равно 1, 0 или -1 соответственно.
Пусть Иі - множество всех путей S, у которых alt(u0) - alt (и,) = і и
alt(uk)>i, О <к<1 для каждого ukeS. Множество //0 будем называть
мноэ/сеством путей Моцкина.
Рассматриваем бесконечную нижнюю треугольную матрицу
М = Щ,Д 0
Теорема 3.1. Для чисел тпк, 0 < к < п, п>0 справедливо
соотношение:
п-к + 2 О,
к,
п- к
У 2 )
, її-к = 0(mocl2), п — к = 1(шос12).
v/c,/y
п\
к\1\(п-к-1)\
- триномиальные коэффициенты.
Для чисел тпк получено следующее рекуррентное соотношение:
т , =—т . . ., п >к, к>\
п,к j ii~\,k-\ " "
к с начальным условием т() 0 = 1.
Числа Каталана Сп, Моцкина Мп и Шредера Rn могут быть заданы следующим образом:
"(2n-i
1%-Чп
с„
*.=z
1 (2п\
С =
i=0
n + \\n Теорема 3.2. Имеют место следующие утверждения:
С.„ «>0.
m . = M ;
n,k її'
1/2)
A=0 /2
где C,; - числа Каталана, Mn - числа Моцкина и Rn - числа Шредера.
Введены в рассмотрение числа l(n,k,h), перечисляющие пути Моцкина длины п, высоты h с к уровнями.
Для чисел l(n,k,h) доказан ряд утверждений. Теорема 3.3. Для чисел l{n,k,h) справедливы следующие утверждения:
^1(п,к,И) = тпк, /?>0;
h=,i
п И к:=0//=0
/;=()
%ГЛ
Y^l{n-kXh) = Rn/.
Л=0А=0 /2
В параграфе 3.3 рассмотрены пути Дика и пути Моцкина с весами. Устанавлено, что обобщённые числа Каталана C(n,N) перечисляют пути Дика, состоящие из 2п шагов N из которых есть подьёмы, выходящие из начала координат.
В параграфе 3.4 изучаются числа Шредера R„, рассмотренные в [45, 49, 50, 53, 56], и пути на плоскости. Введены в рассмотрение числа Т„к , для которых установлена перечислительная интерпретация и доказано следующее утверждение.
Утверждение 3.2. Числа Тпк удовлетворяют рекуррентному соотношению:
Tni<—Tn.] ^.1+37,^11+27,,.1^+1,
Tj/=1, T„i=Sn./, n>2.
Результаты, изложенные в третьей главе, опубликованы в работе [23]. Использованные в главе результаты из указанной статьи получены в нераздельном соавторстве с О.В. Кузьминым. Формулировки и доказательства теорем, приведенные в работе, получены лично автором.
Материалы, представленные в данной диссертации, использовались при чтении спецкурсов в институте математики и экономики Иркутского государственного университета.
Основными результатами диссертации являются:
1. Разработка комбинаторной схемы распространения
последовательности однопараметрических комбинаторных чисел до
матрицы, составленной из соответствующих двупараметрических
комбинаторных чисел, изучение комбинаторных и аналитических свойств
полученных чисел.
2. Классификация плоских корневых деревьев: введены новые
комбинаторные числа, исследованы их свойства и указаны перечислительные
интерпретации; получены соотношения, связывающие введенные
комбинаторные числа с известными комбинаторными числами.
3. Перечисление путей на целочисленной решётке: построен треугольник чисел, являющихся разложениями чисел Моцкина, Каталана и Шредера.
По результатам, изложенным в диссертации, имеется 6 публикаций.
Результаты докладывались на Всесоюзных и международных конференциях по дискретной математике (Третья конференция молодых учёных ИГУ, Иркутск, 1985; конференция «Математика и ее приложения», посвященная памяти профессора А.И. Кокорина и 275-летию РАН, Иркутск, 1999; Восточно-Сибирская зональная межвузовская конференция по
математике и проблемам ее преподавания в вузе, Иркутск, 1999; XII Байкальская международная конференция «Методы оптимизации и их приложения», Иркутск, Байкал, 2001; XIII Международная конференция «Математика в вузе», Псков, 2001.)
Были сделаны доклады на семинарах ФПК МГУ (г. Москва), кафедры математической статистики и теории вероятностей ИГУ.
В диссертации нумерация формул, утверждений, теорем, таблиц идет по главам. Список литературы приводится в алфавитном порядке.
Комбинаторные полиномы разбиений
Матрица весов, которая определяет весовую функцию p(f) на R"t, может состоять не только из чисел, но и из функций, являющихся элементами некоторого кольца. Результаты построений, сделанных на базе такой матрицы, по структуре совпадая с комбинаторными числами, фактически будут комбинаторными функциями, в частности — полиномами. Рассмотрим две разновидности комбинаторных полиномов [28], свойства которых будем систематически использовать далее. Считая допустимыми как положительные, так и отрицательные значения, зададим элементы матрицы весов следующим образом: где gi - параметры, в общем случае не подлежащие определению. Величины (1.5) будем называть А — полиномами (однородными полиномами Белла). Заметим, что в (1.5) сумма берется по всем разбиениям п на к слагаемых, т.е. по всем таким наборам {rx,r2,...,rn_k+x) неотрицательных целых чисел, что Зададим элементы матрицы весов с изменением при /—1: где п = 2,со, к = І,/?-1,и суммирование осуществляется по всем разбиениям в которых число частей Дополнительно полагаем Функции, определяемые соотношением (1.6) есть Z? - полиномы; в статье [18] они названы полиломами Платонова, хотя, строго говоря, по переменной g, они полиномами не являются. Переменные gi,i 1, участвующие в построении A(n,k;g) и B(n,k;g), в частности, могут считаться совпадающими с последовательными производными некоторой функции g(t). Очевидно, А- и Л-полиномы суть нормированные комбинаторные функции типа разбиений. Для однородных полиномов Белла A(n,k;g) известны следующие экспоненциальные производные функции (см., например, [32, стр.179]): (см., например, [33,стр. 57]). Экспоненциальные производящие функции полипомов Платонова B(n,k;g) имеют вид: (см., например, [31, стр. 75]). Покажем аналитическую и алгебраическую двойственность комбинаторных А- и В - полиномов. Формула Бруно выражает производные любого натурального порядка сложной функции F(t) = f[g(t)]. Следуя [28], будем называть f(u) внешней функцией, g(t) - внутренней функцией. Пусть В области, где все участвующие производные существуют, выполняются соотношения, носящие название формулы Бруно: Если считать, что параметры g,,/ l, участвовавшие в построении А — и 5-полиномов, совпадают с употребляемыми сейчас производными аналитической функции, имеющими те же обозначения gt=—rg(t), то формулу Бруно (1.7) можно записать следующим образом (см., например, [28, стр. 66]): Заметим, что в этом случае В терминах рассматриваемых полиномов разбиений разрешение формулы Бруно (1.7) относительно производных внутренней функции и внешней функции имеет, соответственно, следующий вид [28]: Л- и і?-полиномьі могут рассматриваться как элементы взаимно-обратных матриц. Утверждение 1.1 [28]. При любых натуральных к и г п в области аналитичности функции g(t) справедливы формулы Содержание утверждения 1.1 эквивалентно тому, что бесконечные нижние треугольные матрицы И являются двусторонними взаимно-обратными, в этом заключается алгебраическая двойственность А — и В — полиномов.
Тот факт, что матрицы вида (1.13) и (1.14) являются двусторонними взаимно-обратными позволяет записать шесть фаз ротации, описывающих соотношения между А — \\ В — полиномами, которые равносильны матричным равенствам. Если Специальный интерес представляет случай, когда g\.g(j)\ = t, т-е функции g(t) и g(u) взаимно-обратны. Утверждение 1.2 [28]. Между производными взаимно-обратных функций, если все они существуют, выполняются соотношения Доказательство. В рассматриваемом случае F(t) = t, Fn=Sin, п \. При этих условиях A(k,r;F j) = 8кг и из формулы которая соответствует матричному равенству Aj- =BgAF, непосредственно следует доказываемое утверждение. Следствие 1.1. целого ряда перечислительных задач. Задача распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел, была предложена М.Л. Платоновым [30]. В общем случае схема ее решения имеет следующий вид. 1. Любую функцию g(t), разложимую в ряд Маклорена, можно считать экспоненциальной производящей функцией для последовательности gn, п 1, числовых значений ее производных в точке t = 0, g-, Ф 0. Из класса таких функций предпочтительно выбираем те, для которых последовательность , имеет комбинаторную интерпретацию. Производящая функция g(t) определяет последовательность чисел gn = А[п, 1; g(t)] /=0= В[п, 1; g(u)] u=0, п \, (\.\5) где g(u) - функция обратная к g(t) = и. 2. Обозначаем g„\ — gn и присваиваем функции g(t) роль производящей функции бесконечной нижней треугольной матрицы \gnk\ по правилу: 3. На все элементы матрицы -A =g", естественно продолжается перечислительная интерпретация, первоначально устаЕЮвленная для
Обобщения треугольника Паскаля
Следуя схеме, описанной в 1.3, введем в рассмотрение числа осуществляющие перечисления сумм неассоциативных произведений. Пусть даны п линейно упорядоченных элементов алгебры с неассоциативным умножением. Без нарушения линейного порядка они разбиваются па слагаемых произведений. разбиений 2-J ir п, 2-j1" и различных вариантов расстановки скобок в каждом слагаемом произведении? При к=\ ответ известен. Для каждого п это будет - п-е число Каталана — число неассоциативных произведений из п фиксированных, линейно упорядоченных сомножителей (см., например, [34]). Известно, что (1.23) есть производящая фун Рассмотрим равенство где ип{0) - n-ая производная производящей функции u(t), подсчитанная в точке (=0. Учитывая соотношение (1.23), имеем полагая t=0 и проводя необходимые преобразования, получим: После упрощения, получим Числа rnk в работе [36] названы обобщенными числами Каталаиа. Дополнительно полагая Ри=\, можно записать бесконечную нижнюю треугольную матрицу, составленную из чисел P„k . Доказательство. Рекуррентная формула (1.29) следует из соотношения (1.28) и известных свойств биномиальных коэффициентов. Соотношение (1.30) может быть получено последовательными итерациями формулы (1.29). Равенство (1.31) следует из (1.30) при к=1. Докажем соотношение (1.32). Для полиномов Платонова В(п,к) известно Из последней формулы, с учетом (1.26), имеем равенство (1.32). Теорема доказана. Числа Р„ь имеют следующую перечислительную интерпретацию: i„k - число сумм произведений, состоящих из к слагаемых, содержащих в совокупности п фиксированных множителей, взятых из алгебры с неассоциативным умножением. Отметим, что числа /(п,к)у связанные с изучаемыми числами ,& соотношением P„k =f(n,n-k), приведены в заметке [43]. Они же, обозначаемые N(n,k), и соответствующий треугольник, рассматривались в статье [55] (см. также работу [50]). Учитывая соотношение (1.27) введем в рассмотрение числа Рпк пк\ число представлений п в виде композиции к слагаемых, каждое из которых или 1, или 2. Действительно, пусть Тп к - число представлений п в виде композиции к слагаемых, каждое из которых единица или двойка. Если п - натуральное число, то п = к+(п-к), где каждое слагаемое — единица. Следовательно, для представления п в виде композиции к слагаемых требуемого вида достаточно заменить n-k единиц в сумме к=1+1+1...+1 на двойки. Апоскольку данную операцию можно произвести ( п_к ) способами, то имеем Т пЛ ( к_, ) . Учитывая Г „гк= Р п к , получим требуемое. Из Непосредственно из соотношения (1.11) следует справедливость равенства где 5nm - дельта Кронекера.
Числа Р„к связаны с числами Fnk (см. [36]) равенством п Последнее равенство следует из формулы (1.34) и известных свойств биномиальных коэффициентов. Для чисел Шредера S„ известна следующая интерпретация [39]. Пусть X - множество, содержащее п 1 различных элементов, и Вк(Х) множество кция смещешіьіх чисел Каталана, которые обозначим Р„=С„_„п 2, тогда где t(u) = и-и функция, обратная относительно подстановки в алгебре степенных рядов к производящей функции чисел Каталана. Рассмотрим равенство где ип{0) - n-ая производная производящей функции u(t), подсчитанная в точке (=0. Учитывая соотношение (1.23), имеем полагая t=0 и проводя необходимые преобразования, получим: После упрощения, получим Числа rnk в работе [36] названы обобщенными числами Каталаиа. Дополнительно полагая Ри=\, можно записать бесконечную нижнюю треугольную матрицу, составленную из чисел P„k . Доказательство. Рекуррентная формула (1.29) следует из соотношения (1.28) и известных свойств биномиальных коэффициентов. Соотношение (1.30) может быть получено последовательными итерациями формулы (1.29). Равенство (1.31) следует из (1.30) при к=1. Докажем соотношение (1.32). Для полиномов Платонова В(п,к) известно Из последней формулы, с учетом (1.26), имеем равенство (1.32). Теорема доказана. Числа Р„ь имеют следующую перечислительную интерпретацию: i„k - число сумм произведений, состоящих из к слагаемых, содержащих в совокупности п фиксированных множителей, взятых из алгебры с неассоциативным умножением. Отметим, что числа /(п,к)у связанные с изучаемыми числами ,& соотношением P„k =f(n,n-k), приведены в заметке [43]. Они же, обозначаемые N(n,k), и соответствующий треугольник, рассматривались в статье [55] (см. также работу [50]). Учитывая соотношение (1.27) введем в рассмотрение числа Рпк пк\ число представлений п в виде композиции к слагаемых, каждое из которых или 1, или 2. Действительно, пусть Тп к - число представлений п в виде композиции к слагаемых, каждое из которых единица или двойка. Если п - натуральное число, то п = к+(п-к), где каждое слагаемое — единица. Следовательно, для представления п в виде композиции к слагаемых требуемого вида достаточно заменить n-k единиц в сумме к=1+1+1...+1 на двойки. Апоскольку данную операцию можно произвести ( п_к ) способами, то имеем Т пЛ ( к_, ) . Учитывая Г „гк= Р п к , получим требуемое. Из Непосредственно из соотношения (1.11) следует справедливость равенства где 5nm - дельта Кронекера. Числа Р„к связаны с числами Fnk (см. [36]) равенством п Последнее равенство следует из формулы (1.34) и известных свойств биномиальных коэффициентов. Для чисел Шредера S„ известна следующая интерпретация [39]. Пусть X - множество, содержащее п 1 различных элементов, и Вк(Х) множество всех его к — подмножеств.
Классификация по количеству всех вершин в первом слое
Пусть Кпт - число корневых деревьев Шредера Den висячими вершинами, среди которых ровно т — внутренние. Теорема 2.1. Для чисел Кпт справедливо рекуррентное соотношение: Доказательство. Очевидно, что Кп0 = 1 и Кпт=0 при т + \ п. Корневое Шредера Den висячими и т внутренними вершинами может быть получено одним из двух указанных ниже способов. Во-первых, из дерева Шредера D с п-1 висячими и т внутренними вершинами, добавлением висячей вершины с меткой п к одной из т внутренних вершин или к корню, при этом ранее имеющиеся пометки висячих вершин не меняются. Число таких деревьев равно (т + l)Kn_i т. Во-вторых, из дерева Шредера D с п-1 висячими и т-1 внутренними вершинами: или заменой одной из п-1 висячих вершин на т-ю ВЕіутреншою с выходящими из нее двумя ребрами, при этом одна из двух висячих вершин получает метку п, а другая сохраняет метку замененной висячей вершины; или заменой корня на внутреннюю вершину с выходящим из нее ребром, висячая вершина которого - корень, доба присоединенные числа Стирлинга второго рода b(n,k) удовлетворяют следующему рекуррентному соотношению: Из соотношений (2.1) и (2.2) следует, что Для чисел Шредера Sn известно соотношение: Из формул (2.3) и (2.4) получаем С учетом соотношения (2.5) числа Кпт названы в [22] расщепленными числами Шредера второго рода. Первые значения чисел К для 2 п 8 приведены в таблице 2.1. Данное представление позволяет интерпретировать числа А(п,2) как число всех помеченных плоских корневых деревьев Шредера D, содержащих п висячих вершин и не более двух внутренних вершин в каждом дереве. Пусть число Hnh определяет число деревьев Шредера D с п висячими вершинами по параметру h - высоте (максимальному количеству внутренних вершин на ветке). Теорема 2.2. Для чисел Нп1 справедливо следующее рекуррентное соотношение: Доказательство. Если дерево Шредера D имеет высоту 1, то п— множество его висячих вершин может быть разбито на следующие подмножества: одно подмножество составят висячие вершины, расположенные в первое слое, каждое из остальных подмножеств составят вершины, выходящие из одной и той же внутренней вершины. Поскольку из каждой внутренней вершины дерева D исходит не менее двух ветвей, задача сводится к нахождению числа всех разбиений п - множества на подмножества, содержащие не менее 2 и не более п-l элементов. Используя известную интерпретацию чисел Стирлинга второго рода Snk как числа всех разбиений п-множества N точно на к непустых блоков, получаем соотношение: которое с учетом (2.8) дает соотношение (2.6). Теорема доказана. Из перечисленного смысла чисел Hnh и Sn, следует Ввиду (2.9) числа Нnh названы в [22] расщепленными числами Шредера первого рода. Первые значения чисел Н h для 2 п 8 приведены в таблице 2.2. Пусть имеется п сложенных пополам одинаковых листов бумаги (будем вляя к новому корню ребро, висячая вершина которого имеет метку п, при этом ранее имеющиеся пометки висячих вершин также не меняются. Число таких деревьев равно (п + т-1)Кп_1т_г
Поскольку число деревьев, полученных первым и вторым способом, в сумме дают числа Кпт, то имеем соотношение (2.1). Теорема доказана. Известно (см., например [31]), что присоединенные числа Стирлинга второго рода b(n,k) удовлетворяют следующему рекуррентному соотношению: Из соотношений (2.1) и (2.2) следует, что Для чисел Шредера Sn известно соотношение: Из формул (2.3) и (2.4) получаем С учетом соотношения (2.5) числа Кпт названы в [22] расщепленными числами Шредера второго рода. Первые значения чисел К для 2 п 8 приведены в таблице 2.1. Данное представление позволяет интерпретировать числа А(п,2) как число всех помеченных плоских корневых деревьев Шредера D, содержащих п висячих вершин и не более двух внутренних вершин в каждом дереве. Пусть число Hnh определяет число деревьев Шредера D с п висячими вершинами по параметру h - высоте (максимальному количеству внутренних вершин на ветке). Теорема 2.2. Для чисел Нп1 справедливо следующее рекуррентное соотношение: Доказательство. Если дерево Шредера D имеет высоту 1, то п— множество его висячих вершин может быть разбито на следующие подмножества: одно подмножество составят висячие вершины, расположенные в первое слое, каждое из остальных подмножеств составят вершины, выходящие из одной и той же внутренней вершины. Поскольку из каждой внутренней вершины дерева D исходит не менее двух ветвей, задача сводится к нахождению числа всех разбиений п - множества на подмножества, содержащие не менее 2 и не более п-l элементов. Используя известную интерпретацию чисел Стирлинга второго рода Snk как числа всех разбиений п-множества N точно на к непустых блоков, получаем соотношение: которое с учетом (2.8) дает соотношение (2.6). Теорема доказана. Из перечисленного смысла чисел Hnh и Sn, следует Ввиду (2.9) числа Нnh названы в [22] расщепленными числами Шредера первого рода. Первые значения чисел Н h для 2 п 8 приведены в таблице 2.2. Пусть имеется п сложенных пополам одинаковых листов бумаги (будем называть их папками). Ориентируем все папки в одну сторону и начнем укладывать их. Каждую последующую папку можно либо вложить в одну из предыдущих, либо приложить к ним. Так, вторую папку можно либо вложить в первую, либо приложить к ней. Для трех папок получаем 5 различных конфигураций. В общем случае количество возможных конфигураций К, возникающих при укладывании п папок совпадает с п-м числом Каталана Сп (см., например, [44]).
Плоские корневые деревья Моцкина с петлями
Деревья Моцкина fM„ могут быть классифицированы по различным признакам. В качестве последних рассмотрим: а) число петель и ребер, выходящих из корня; б) число ребер; в) число петель; г) высота. Пусть r(n,M,k) - число п - деревьев Моцкина 5 /„, у каждого из которых к ребер и N- число ребер и петель, выходящих из корня. Значения чисел r(n,N,k) для 1 п 9, N п приведены в таблице 2.6. П соотношений (2.33) и ввиду которого числа нгпк названы в [21] расщепленными числами Моцина второго рода. С учетом формулы (3.5) получим Пусть тп1 - число п —деревьев Мп высоты 1с/ петлями. Имеет место следующее утверждение. Утверждение 2.1. Числа тп1 удовлетворяют следующему рекуррентному соотношению Доказательство. Каждое из п — деревьев высоты 1 с / петлями может быть получено либо добавлением ребра к (п-2) - дереву 9А.п высоты 1 с / петлями, либо добавлением петли к (п-І)-дереву Мп высоты 1 с /-/ петлями. Поскольку число деревьев первого и второго типа равно соответственно тп_2/ и /»„_,м, имеем равенство (2.35). Непосредственно из (2.35) и равенства /н,, = 1 следует, что Пусть mnh - число п — деревьев Моцкина СМп высоты h. Из перечислительного смысла mnh и Мп следует равенство ввиду которого mnh названы в [21] расщепленными числами Моцкина первого рода. Значения чисел mnh для 1 п 8 приведены в таблице 2.8 Из сопоставления соотношения (2.36) и известной рекуррентной формулы для чисел Фибоначчи (1.17) получим, что /7ї„, = Fn, что позволяет интерпретировать числа Фибоначчи Fn как число п — деревьев Моцкина !М„ высоты один. Пусть v0, ..., vn— такая последовательность точек из Z , что: 1). Тогда vo, ..., vn называем путем без уровней с началом v() и концом vn\\ обозначаем v= v0 ... vn j0. Пусть с //ц — множество всех путей v, у которых alt(v()) = /, alt(v„) =j и і alt(p) j для \fp є v. Множество nY/i j будем называть множеством путей Мак-Магона. (") Интересна следующая геометрическая интерпретация чисел \kJ (см., например, [17]). Пусть дана прямоугольная усть M{n,N) - число n - деревьев Моцкина, у которых vV — число ребер и петель, выходящих из корня. Значения чисел M(n,N) приведены в таблице 2.7, дополнительно полагаем М(\,\) = 1. Числа M(n,N) называем обобіне/шьши числами Моцкииа. Из соотношений (2.30) и (2.31) следует Пусть тпк - число п - деревьев Моцкина 5М,7 с к ребрами. Из указанного соответствия между элементами множества всех деревьев Моцкина 5W„ и множества путей Моцкина 8 длины п следует равенство из которого с учетом формул (3.1) и (3.2) получаем Из последнего соотношения в частности имеем Ш2п,п = С,г Очевидно, что Сопоставление соотношений (2.33) и ввиду которого числа нгпк названы в [21] расщепленными числами
Моцина второго рода. С учетом формулы (3.5) получим Пусть тп1 - число п —деревьев Мп высоты 1с/ петлями. Имеет место следующее утверждение. Утверждение 2.1. Числа тп1 удовлетворяют следующему рекуррентному соотношению Доказательство. Каждое из п — деревьев высоты 1 с / петлями может быть получено либо добавлением ребра к (п-2) - дереву 9А.п высоты 1 с / петлями, либо добавлением петли к (п-І)-дереву Мп высоты 1 с /-/ петлями. Поскольку число деревьев первого и второго типа равно соответственно тп_2/ и /»„_,м, имеем равенство (2.35). Непосредственно из (2.35) и равенства /н,, = 1 следует, что Пусть mnh - число п — деревьев Моцкина СМп высоты h. Из перечислительного смысла mnh и Мп следует равенство ввиду которого mnh названы в [21] расщепленными числами Моцкина первого рода. Значения чисел mnh для 1 п 8 приведены в таблице 2.8 Из сопоставления соотношения (2.36) и известной рекуррентной формулы для чисел Фибоначчи (1.17) получим, что /7ї„, = Fn, что позволяет интерпретировать числа Фибоначчи Fn как число п — деревьев Моцкина !М„ высоты один. Пусть v0, ..., vn— такая последовательность точек из Z , что: 1). Тогда vo, ..., vn называем путем без уровней с началом v() и концом vn\\ обозначаем v= v0 ... vn j0. Пусть с //ц — множество всех путей v, у которых alt(v()) = /, alt(v„) =j и і alt(p) j для \fp є v. Множество nY/i j будем называть множеством путей Мак-Магона. (") Интересна следующая геометрическая интерпретация чисел \kJ (см., например, [17]). Пусть дана прямоугольная сетка квадратов с размерами п и к (шахматный город, состоящий из п х к прямоугольных кварталов, разделенных А:-1 горизонтальными и п-\ вертикальными улицами). Тогда: - число различных кратчайших на этой сетке путей Мак-Магона, ведущих из левого верхнего угла А(0; к) в правый нижний угол В(»; 0). Для обобщенных чисел Эйлера а(п, к; I) известна следующая перечислительная интерпретация [17]. В прямоугольнике с к + 1 столбцами ип — к — /+ 1 строками рассматриваем все у1Г ] путей Мак-Магона из левого верхнего угла в правый нижний угол. В каждом таком пути S пометим меткой / горизонтальный шаг в і-їі строке и меткойу вертикальный шаг ву -м столбце. Вес пути S считаем равным произведению (п — 1) таких меток, соответствующих шагам в пути S. Тогда сумма весов всех путей в прямоугольнике. При / = 1 из приведенной интерпретации а{п, к; 1) , считая шаг вправо спадом, получаем известную интерпретацию чисел Эйлера А{п, к). В [17] множество fl = -/ ,, частично упорядочивается условием доминирования: путь v є п// доминирует над путем v1 є //, если v лежит целиком между v и путем вдоль координатных осей. Пусть w(v) — количество путей, доминирующих над v, тогда (см., например, [17])
