Обобщенные пирамиды Паскаля и их приложения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Обобщенные пирамиды Паскаля

1.1 Треугольник Паскаля и его обобщения.

1.1.1 Биномиальные коэффициенты и треугольник Паскаля

1.1.2 Другие арифметические треугольники.

1.1.3 Обобщенный треугольник Паскаля.

1.1.4 Частные случаи.

1.1.5 Перечислительные интерпретации

1.2 Пирамида Паскаля и ее обобщения

1.2.1 Триномиальные коэффициенты и пирамида Паскаля

1.2.2 Обобщенная пирамида Паскаля.

1.2.3 Частные случаи.

1.2.4 Перечислительные интерпретации

2 А- и В-пирамиды

2.1 А- и В-треугольники.

2.1.1 Обобщенные числа Стирлинга.

2.1.2 Производящие функции.

2.1.3 Обобщенные числа Фибоначчи.

2.1.4 Частные случаи.

2.1.5 Перечислительные интерпретации

2.2 А- и В-пирамиды.

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

2.2.2 Производящие функции.

2.2.3 Рекуррентные соотношения

2.2.4 Перечислительные интерпретации

2.3 Обобщенные числа Трибоначчи.

2.3.1 Построение.

2.3.2 Рекуррентные соотношения

2.3.3 Частные случаи.

2.4 Взаимные преобразования комбинаторных чисел

2.4.1 Обобщенные числа Стирлинга и Фибоначчи

2.4.2 Обобщенные триномиальные коэффициенты и обобщенные числа Трибоначчи.

3 Комбинаторные полиномы разбиений

3.1 Однородные полиномы Белла и Платонова

3.1.1 Введение.

3.1.2 Рекуррентные соотношения

3.1.3 Частные случаи.

3.1.4 Связь с симметрическими функциями.

3.1.5 Интерпретации.

3.2 Полиномы Тушара и Р-полиномы.

3.2.1 Введение.

3.2.2 Рекуррентные соотношения

3.2.3 Частные случаи.

3.2.4 Интерпретации.

3.3 Обобщенные А- и В-полиномы.

3.3.1 Введение

3.3.2 Рекуррентные соотношения

3.3.3 Частные случаи.

3.3.4 Перечислительные интерпретации

3.4 Взаимные преобразования полиномов.

3.4.1 Однородные полиномы Белла и Платонова

3.4.2 Полиномы Платонова и обобщенные В-полиномы

3.4.3 Т-полиномы Тушара и Р-полиномы.

4.1.2 Пути Моцкина.164

4.1.3 Пути Мак-Магона.167

4.2 Плоские корневые деревья .168

4.2.1 Помеченные корневые деревья.169

4.2.2 Непомеченные корневые деревья.173

4.3 Случайные блуждания.183

4.3.1 Случайные блуждания на плоскости.183

4.3.2 Процессы рождения и гибели.188

4.4 Дискретные процессы восстановления.189

4.4.1 Введение .190

4.4.2 Простой процесс восстановления.192

4.4.3 Обобщения простого процесса восстановления . . 195

4.4.4 Процессы восстановления со случайным временем 202

4.4.5 Интерпретации.208

Заключение 212

Литература 213

Введение

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

По мере развития комбинаторных методов дискретной математики возникали различные способы классификации и представления материала. По нашему мнению, это еще в большей степени касается области перечислительных задач комбинаторного анализа, где существуют универсальные подходы Мак-Магона, Редфилда-Пойа, Сачкова, Платонова, Рота [14, 71, 76, 79, 202]. В данной диссертационной работе мы ограничиваемся рассмотрением круга вопросов, связанных с применением более частной схемы — обобщенной пирамиды Паскаля.

Среди множества различных чисел комбинаторного происхождения самыми работоспособными в теоретических исследованиях и различного рода приложениях, вне всякого сомнения, являются биномиальные коэффициенты = щ^г^ут, п > 0, 0 < к < п, которые при каждом фиксированном п образуют (п+1)-ю строку таблицы, называемой треугольником Паскаля. Числа удовлетворяют рекуррентному соотношению (правилу Паскаля) с граничными условиями = 1, п > 0, = 0, если тгп{п, к,п — к) < 0. Правило Паскаля является определяющим при построении треугольника Паскаля.

В последние десятилетия расширился круг исследований как самого треугольника Паскаля, так и его плоских и пространственных аналогов и обобщений. Имеется ряд научных и методических публикаций по этой проблематике, большей частью зарубежных математиков, однако среди них только четыре книги. Это монография Бондаренко [4], два популярных издания [89, 168] и монография автора данной работы [56].

Идеи построения арифметических треугольников комбинаторного происхождения, родственных треугольнику Паскаля, и их приложений высказывались многими авторами (например, [4, 86, 89, 114, 160, 168, 191, 216, 237]), причем в некоторых работах, естественно, полученные результаты повторяются. Пирамиды и гиперпирамиды Паскаля открываются и переоткрываются, строятся и используются, в частности, в работах [103, 105, 107, 114, 150, 160, 172, 186, 200, 204, 210, 216, 226, 229, 230, 232, 236]. В последнее время возродился интерес к арифметическим, геометрическим и комбинаторным свойствам пирамид, обобщающих пирамиду Паскаля. Можно отметить [116, 160, 216, 232], а также книги [4, 56], в которых, в частности, имеется ряд библиографических ссылок.

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

Диссертация состоит из четырех глав, которые разбиты на 14 параграфов. Параграфы разбиваются на пункты.

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

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

В параграфе 1.1 приведен ряд основных свойств широко известного треугольника Паскаля и родственных ему арифметических треугольников Стирлинга, JTaxa, Эйлера, Каталана и других. Приведено понятие, некоторые свойства и приложения [12, 14, 69] обобщенного треугольника Паскаля — треугольной таблицы, элементы которой удовлетворяют соотношениям:

V(n, к) = an>k^V(n - 1,к - 1) + Pn,kV(n - 1 ,к) (1.36) с граничными условиями F(0,0) = VQ,V(n,k) = 0, если min(n,k,n — к) < 0 и которая служит плоским обобщением указанных выше комбинаторных объектов.

Рассматриваются суммы элементов, расположенных на диагоналях обычного и обобщенного треугольника Паскаля. В частных случаях получены соотношения для ряда хорошо известных комбинаторных чисел и их некоторых обобщений, ранее изучавшихся в [13, 14, 69, 71, 116,118, 204, 206, 216, 233, 243].

В параграфе 1.2 приводятся основные свойства пирамиды Паскаля и строится ее обобщение — обобщенная пирамида Паскаля (V-пирамида) — трехгранный пирамидальный массив, элементы которого удовлетворяют следующим рекуррентным соотношениям [48, 45]: V(n, к, /) = аП)к-1,iV(n - 1, к - 1, /)+ n,k,i-\V{n - 1, к, I - 1) + 7n,k,iV(n - 1, M) (1-56) с граничными условиями V(0,0, 0) = Vo, V(n, к, I) = 0, если min(n, к, /,п - к -I) <0.

Все элементы с фиксированным индексом п, к или I составляют п-слой, левый к-сегмент, и правый 1-сегмент, V-пирамиды соответственно. Элементы с фиксированными к и /, составляют (к,1)-столбец, а с фиксированными п и к — (п, к)-диагоналъ V-пирамиды. При к = 0, / = 0 и к + 1 = п получаем, соответственно, правую, левую и заднюю грани обобщенной пирамиды Паскаля, каждая из которых является обобщенным треугольником Паскаля.

Рассмотрены элементы, расположенные на плоских сечениях обычной и обобщенной пирамид Паскаля. В частных случаях получены соотношения и интерпретации для ряда хорошо известных комбинаторных чисел и их некоторых обобщений, ранее изучавшихся в [11, 76, 97, 100, 101, 105, 121, 140, 152, 154, 159, 199, 203, 204, 205, 216, 219, 227, 230, 245, 246, 247].

Результаты автора, изложенные в первой главе, опубликованы в работах [45, 48, 54, 55, 58, 59, 56].

Вторая глава посвящена построению и исследованию важных двух частных случаев обобщенного треугольника Паскаля, так называемых А- и B-треугольников, образованных обобщенными числами Стерлинга второго А1 и первого рода В^, соответственно, и двух частных случаев обобщенной пирамиды Паскаля — А- и В-пирамид, состоящих из обобщенных триномиальных коэффициентов второго и первого рода B^i соответственно.

При помощи суммирования элементов, расположенных на восходящих диагоналях В- и А-треугольников, строятся и исследуются два новых обобщения чисел Фибоначчи Т\(п) и Тч(п).

Построены соответствия и получены алгоритмы взаимных преобразований обобщенных чисел Стирлинга А1 и и обобщенных триномиальных коэффициентов и { соответственно.

В параграфе 2.1 приведены известные и новые свойства двух важных частных случаев обобщенного треугольника Паскаля — А- и В-треугольников.

Интерес к классической теории симметрических функций, с успехом разрабатываемой еще Мак-Магоном [202], в последнее время возродился с новой силой, в основном в связи с приложениями к комбинаторике, алгебраической геометрии и теории представлений. Многие из этих приложений отражены в книге Макдональда [65].

Имеется большое количество различных обобщений чисел Стирлинга (например, [3, 137, 181]. Элементарные и полные симметрические функции в математике известны давно. Рассмотрение их как обобщенных чисел Стирлинга впервые встречается у Платонова и Таубе-ра [68, 241]. Систематическое описание основных свойств обобщенных чисел Стирлинга дано в [71, §4]. Некоторые свойства пар обратимых соотношений типа Стирлинга изучались в работах [179, 180, 198].

Если Vo = 1? то при an>k = 1,j3n,k — Цп-ъ п>1, 0<к<п имеем V(n,k) = В% и из (1.36) следует рекуррентная формула

5п nil-1 I ,, Т)П-1 для обобщенных чисел Стирлинга первого рода. При а>п^ = 1, = имеем V(n, к) = а из (1.36) рекуррентную формулу

А-к — Ак-1 + ^к^к 1 определяющую обобщенные числа Стирлинга второго рода. Треугольники, составленные из чисел В1 и называем В- и А-треуголъником, соответственно.

В ряде работ (например, [184, 212, 213]) строятся различные обобщения чисел Фибоначчи, получены явные формулы их представления в виде суммы полиномиальных коэффициентов.

В данном параграфе вводятся и исследуются суммы элементов, расположенных на восходящих диагоналях В- и А-треугольника: п/2] [п/2]

Нп) = £ впт-т, Ып) = Е ш=0 т=0 названные обобщенными числами Фибоначчи первого и второго рода соответственно [53].

Пусть 9п,к{р) — произведения по п — к сомножителей из множества • •}• Введем операторы и ф^, удовлетворяющие соотношениям: п.АгМ = /"п/п.ЛгМ, Ф^/п.йМ = 1*к1п,к(у) и условиям линейности: а/п^М + ЪдтМ) = /„,*(//) + Ь 9т,М,

Ф+ Ь9т,М) =а®Ц 1п,к{р) + Ь®ц 9т,М, где а и 6 — произвольные постоянные, не зависящие от

Теорема 2.1. Обобщенные числа Фибоначчи Т\(п) и ^(п), п > 2, удовлетворяют, рекуррентным соотношениям:

Я(п) = (8)^1 (п - 1) + ^(п - 2), - 1) + - 2) с начальными условиями ^(0) = (0) = 1, ^1(1) — -^о,' ^2(1) — ^о

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

В параграфе 2.2 рассматриваются важные частные случаи обобщенной пирамиды Паскаля — А- и В-пирамиды, в каждом сечении которых расположены обобщенные триномиальные коэффициенты второго рода и первого рода В^ соответственно.

Если Ц> = 1, то при ащк,1 = ап-\,Рп,к,1 = Рп-иУп,к,1 = 7п-ъ п > 1, 0 < к +1 < п, имеем У(п, к,1) = и из соотношения (1.56) следует рекуррентная формула щ,1 — ^п-хЩ!^ + + 1п-\В^71, 9 определяющая обобщенные триномиальные коэффициенты первого рода; для an}k,i = ak,Pn,k,i = (3k,"fn,k,i = 7Ь п > 1, 0 < к + I < п, получим V(n,kJ) = а из (1.56) следует рекуррентная формула

AnkJ = AJZÎf/ + + IkAkH1, для обобщенных триномиальных коэффициентов второго рода [22]. Пирамиды, составленные из чисел и Aj^, называем В- и А-пирамидой соответственно.

Приводится ряд свойств и приложений обобщенных триномиальных коэффициентов Ак1 и { и соответствующих им пирамид, полученных в работах автора [22, 26, 33, 45].

В частности, найдены производящие функции и представление чисел Вк1 и Afri в форме, тесно связанной с построениями, названными в книге [71] комбинаторными числами. оо оо

Обозначим Ak{y,z) = Ak(y,z]a,[3^) = J2 Е к > О,

1=0 п=к+1 п п—к

Въ{х,у)=Вп(х,у;а,/3,у) = Е Е п>1. к=О 1=0

Теорема 2.2. Справедливы следующие утверждения:

1. Производящая функция элементов, составляющих правый к-сегмент А-пирамиды, имеет вид:

Ak(y,z) = zk Дог,- П(1 - Piyz--Yiz)-\ к>0. j=О i=О

2. Производящая функция элементов, образующих п-слой В-пира-миды, имеет вид:

71-1

Вй(х, у) = П + Piy + 7i)i П>1. г=0

Получен ряд рекуррентных формул для чисел Bkl и Akl. д д

Обозначим Qxy = J2 , Qz = Е • г>0 г>0

Теорема 2.3. Д/гя" B%j и А% h построенных на базах а, ¡3 и у, имеют место следующие соотношения: kBnkJ = Qap(Bï-w) = ю

IBh = Qi{Bt+ = Q^V) = n - fe - = gi(5jf+1>/) = QK^V) = QWlh n + l)All = Qß(Ank£1) = Q7(A$1), kAnk>l = Qaa(Anktl), lAnktl = Qß7(Al^) = , n-k-l)All = Q}(All+1)=Qlf(All), n>0,0<k<n,0<l<n-k.

Как следствия, получены новые соотношения для элементарных и полных симметрических функций (см. [26, 33]).

Из статьи, написанной в соавторстве с H.A. Колокольниковой, в параграфе 2.2 использованы только результаты, полученные лично автором.

Параграф 2.3 посвящен построению и изучению двух новых обобщений чисел Трибоначчи.

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

В данном параграфе изучаются суммы элементов на некоторых плоских сечениях В- и А-пирамиды: n/2] [n/3] nm2r [n/2] [п/3] пт2г

7l(n) = J2 12 Bn-2rn-Zr,ri ^2(П) — XI 2^зГ;Г.

77г=0 г=0 т=0 г=0 названные обобщенными числами Трибоначчи первого и второго рода соответственно.

Для изучаемых чисел получены новые рекуррентные формулы [53]. Теорема 2.4. Обобщенные числа Трибоначчи Т\{п) и Tiin), п > 3, удовлетворяют рекуррентным соотношениям:

Ti(n) = ®aTi{n - 1) + (g)TTi(n - 2) + ®ßTi{n - 3), ад = ФаТ2(п -1) + ет7Цп - 2) + е^г2(п - з) с начальными условиями 7^(0) = 71(0) = 1,72(1) = А\ 0,7^(2) = +

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

В параграфе 2.4 изучаются некоторые вопросы преобразований одних изучаемых комбинаторных объектов в другие.

Задачи алгоритмического характера на дискретных конечных математических структурах встречаются на практике постоянно [20, 75, 83]. Можно выделить два класса прикладных задач: создание алгоритмов и программ с преобладанием вычислений комбинаторного характера и алгоритмов, осуществляющих конструктивное перечисление комбинаторных объектов заданного класса. В последнем случае используется либо исчерпывающий последовательный перебор, либо его некоторые модификации, позволяющие ограничить объем перебора. Предлагаемый автором в работах [30, 32, 35] метод состоит в нахождении и использовании изоморфного преобразования элементов известного множества комбинаторных объектов в элементы искомого множества.

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

Пусть даны множества = {ао, а\,., ап-1} и]Уй = {0,1,., п — 1}. Обозначим Ва(п, к) — множество всех ^-сочетаний без повторений из ап, Аа(п,к) — множество всех /¿-сочетаний с повторениями элементов из ац. Множества 7п, Вр(п, к), В1(п, к), Ар(п, к) и А7(п, к) определим аналогично. Через |Х| обозначим число элементов множества X. Считаем для определенности, что |5а(п,0)| = |Аа(п,0)| = 1, п > 0, \Ва(п, к) | = | Аа(п, к) | = 0, если шт(гг, к,1,п — к — I) <0.

Пусть — множество всех векторов з = («о, «¿-1), где Е ац. Введем преобразования, действующие на множестве Обозначим: сра — преобразование, упорядочивающее координаты вектора я £ по принципу неубывания их номеров в множестве а^; фа — преобразование, увеличивающее номер каждого элемента, служащего ]-тк <]< к — I) координатой вектора фа^к), на величину то есть, если Sj = то фа(зу) = а^; фа — преобразование, уменьшающее номер каждого элемента, служащего й {0 < j < к — 1) координатой вектора в £ = Фа{Зк)-> на величину то есть, если = аг-, то = а^.

Теорема 2.5. Пусть В% и построены из элементов множества ап, тогда: иа{А1) = ВЪ Соа(Впк) =Апк, п > 1, 0 < к < п - 1, где иа = фа о сра, ша = фа о (ра.

Следствие 2.6. В условиях теоремы 2.5 справедливы соотношения: п)) = й>а(Ъ(п)) = П > 1.

На основании теоремы 2.5 построены алгоритм 2.1 преобразования А7], в В^ и алгоритм 2.2 преобразования в А^, которые, на основании следствия 2.6, могут служить алгоритмами преобразования Т^п) в Т\{п) и ему обратным.

Пусть Тп — множество всех векторов £ = (¿о, ¿ъ ■ • • ? ¿п-1)? У которых к из п координат в совокупности являются элементом множества Аа(п, / — множества I), ж п — к — 1 — множества А7(п,п — к — 1). Если г € Тп, тогда 1р = : tj £ /?«}, /т = О' : Е ъ}

Введем преобразования, действующие на множестве Тп. Пусть: и>р7 и шр7 — преобразования, аналогичные преобразованиям иа и ша соответственно, но действующие (не различая их) на элементах Д,- и 7?; одновременно без учета расположения аг-; та — преобразование, меняющее номера всех аг- на составляющие в совокупности множество А^ — — /7. га — преобразование, меняющее номера всех а^ на составляющие в совокупности множество с^.

Теорема 2.6. Пусть В^ и / построены из элементов множеств ай, и Уп, тогда:

Х(4Ы = ^ *№"/) = ^ п > 1, 0 < * < п, 0 < 7 < п

2б9е Х = Та° Х = Та° йр7.

Следствие 2.7. В условиях теоремы 2.6 справедливы соотношения: х(Г2(п)) - 71(п), х(7!(п)) = Т2(п), п > 1.

На основании теоремы 2.6 построены алгоритм 2.3 преобразования А^вБ^и алгоритм 2.4 преобразования В^в А7^ которые, на основании следствия 2.7, могут служить алгоритмами преобразования 72(п) в Т\(п) и ему обратным.

Показано, что данные алгоритмы могут быть использованы при решении некоторых задач теории кодирования [96].

Результаты, изложенные во второй главе, опубликованы в работах [22, 30, 32, 33, 45, 53, 58, 56]

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

С симметрическими функциями тесно связан весьма представительный класс функций, которые называют полиномами разбиений. Понятие "полином разбиения" — полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса — введено Беллом в [108]. Один из таких полиномов Yn(f;yi,. ,уп), связанный с производными от композиции функций, Риордан в книге [76, с. 46] назвал полиномом Белла. Известно большое количество работ, в которых изучаются различные полиномы разбиений и их коээфициенты, рассмотрены частные случаи и приложения (например, [19, 93, 127, 128, 135, 146, 155, 157, 176, 178, 185, 193, 238, 244, 250, 251]). В частности, в [193], строится q-обобщение разложения Бюрмана-Лагранжа. При этом метод Егорычева [16] используется при построении q-обобщения обратимых соотношений Риордана [77].

Нами изучаются некоторые из таких полиномов: однородные полиномы Белла АПук{х) и сопряженые с ними полиномы Платонова Вп^(х), обобщающие их полиномы А^(х) и В^(х), а также полиномы Туша-ра Сп^{х,у) и Тп^(х,у) и вводятся новые, сопряженные с последними, так называемые Р-полиномы Рп,к{х,у).

Построены соответствия и получены алгоритмы взаимных преобразований однородных полиномов Белла и Платонова, полиномов Платонова и обобщенных B-полиномов, а также полиномов Тушара и Р-полиномов.

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

В параграфе 3.1 изучаются однородные полиномы Белла Ап^(х) и Платонова Вп^(х).

Ряд свойств коэффициентов п-го полинома Белла — однородных или частичных полиномов Белла Ап^{х) и сопряженных с ними полиномов

Вп,к(х) (см. [70], [71, с. 70]), названных автором в [27] полиномами Платонова, приведен, в частности, в [73, 42].

Однородные полиномы Белла Ап^(д) имеют вид п-к+1

АпМ = п\Т, П д?[гтгГ\ п,к > 1,к < щ п,к г=1 где = (<7ь <7г> ■ ■ ■) — формальные переменные, а суммирование ведется по всем таким наборам (г!,г2,., 1) неотрицательных чисел, что гг + 2г2 + . • • + (п - к + 1)гп*.+1 = п, гх + г2 + . + = к, то есть по всем разбиениям натурального п на к натуральных слагаемых. Полиномы Платонова ВП!к(д) имеют вид

ВпМ = - 1 У-91п~кУ1 £ (-1)Г1п!(2п -к-п- 1)!х

2п—2к,п—к п-к+1

X П д?[гтгГ\п>2, 1<к<п-1, i=l где суммирование ведется по всем разбиениям натурального числа 2го — 2к на п—к натуральных слагаемых. Дополнительно полагаем Вп>п{д) = 1.

Переменные д^ г > 1, участвующие в построении Ап^(д) и Вп^(д), в частности, могут считаться совпадающими с последовательными производными некоторой функции.

Пусть д(£) = Если существует функция д(и) =

Ьи1/г\ такая, что д(д^)) = то для д = (ди д2, .) и д = (<?ь <72, • • •) имеет место соотношение ^„¿(¡у), щк > 1, к < п.

Для однородных полиномов Белла Ап^(д) и полиномов Платонова Вщк(д) известны следующие производящие функции: со оо Ащк{д)Г/п\ = [<7«ГМ £ Вп,к(д)ип/п\ = [$(*)]*/*!.

Для полиномов Платонова ВПук(д) доказана Теорема 3.1. Для п > 1 справедливы соотношения: - • М > 1,Л; +г < п + 1. од\ \ г

Выводятся различного рода рекуррентные формулы для полиномов Ап>к(д) и Вп>к(д). Как следствия получены новые соотношения для чисел Стирлинга, Лаха, Шредера, элементарных и полных симметрических функций. Обсуждаются новые и частично известные перечислительные интерпретации (перечисление с весами) и приложения, в том числе при расчете некоторых характеристик монотонно неубывающих потоков частиц, однородных в каждом поколении [37, 42, 25].

Описание монотонно неубывающих потоков частиц, однородных в каждом поколении, получено в нераздельном соавторстве с М.Л. Платоновым.

В параграфе 3.2 изучаются две разновидности полиномов Тушара и вводятся новые Р-полиномы, составляющие с Т-полиномами Тушара квазиортогональную систему.

Тушар в [248], в связи с изучением некоторых циклических подстановок, ввел ряд обобщений полиномов Белла. Для одного из них, полиномов Тп^(х,у), которые будем называть Т-полинамами Тушара, Хризафиноу [129] получил экспоненциальные производящие функции и рекуррентные соотношения. Хараламбидес и Хризафиноу [130] при определении некоторых вероятностей в задаче флуктуации случайных блужданий использовали свойства ряда частных случаев полиномов Тщк(х,у) и ввели полиномы у), которые будем называть С-полипомами Тушара.

Т-полиномы Тушара Тп>к(х,у) = Т(х 1,. .;у 1,.) для п > 1, 0 < к < п имеют вид п

Тп,к(х,у) =п!ЕП х^(кМЩк+гТ\ ¿=1 где х = (х\,х2, • • •), у = (у1,у2, • • •) — формальные переменные, а суммирование ведется по всем таким наборам ., кп; ., тп) целых неотрицательных чисел, что £"=1 Ь = к, £"=1 i{ki + гг) = п. Дополнительно полагают То$(х,у) = 1.

Пусть х{г) — х$Ч%\, у{1) = £гъ1 у41/г\. Для полиномов Тп>к(х, у) известны экспоненциальные производящие функции:

00 оо оо тп,к(х,у)гп/п\ = (х(г))кеМ/к\, £ £ Тп,к(х,у)ик/п\ = п=к к—0п=к

Пусть о, — х2д/дх1 + хзд/дх2 + . + У2д/ду\ + у^д/ду2 + . .

Теорема 3.2. Для те > 1 справедливы соотношения:

ТПгк(х,у) = ххТп1^1{х,у) + (ух + 0)Тп^к(х,у), к > 1,п > к - 1,

5 /те^

-Тщк{х,у) = . к, г > 1, п - г > к - 1. о »г,к I > г/ у I . г

5 (тъ

-ТП;к(х,у) = . \Тп^к(х,у), к > 0, г > 1, те - г > к. г\ и,к V 7 ) \ •

V г

В [51] введены новые комбинаторные полиномы разбиений, так называемые Р-полиномы, которые могут быть заданы следующей производящей функцией: !М!е-»<г<»», к > о.

Для Р-полиномов получены соотношение, связывающее их с А- и В-полиномами:

РпЛ^У) = £

К) р=о и явная формула: х(2п-к-к,- 1)! (± т + П х^у?(кМткг+гТ\ г=1 / г=1 где п>1,1<&<п, а суммирование ведется по всем к{ > 0, 1 < г < 2те — таким, что = п - к, Т%=12к КЬ + = 2п ~ 2к

Дополнительно полагаем РП!П(х,у) = Ж1га, те > 1.

Показано, что Р-полиномы являются обобщениями полиномов Платонова и верна

Теорема 3.3. Для п, к, г > 1 справедливы соотношения: х\Рп,к{х, у) = Рп-\,к-\{х, У) + {Я~ У\)Рп-1,к{х, у), к < те, д -РП)к(х, у) = - Г + г]РП)Л+|-(ж,у), те -г > к - 1, о К \ ™ ) 3 / 1

ОУ1 \ г д Рп,к(х,у) = - \ + г) (Р„,*+*(ж,г/) - 1РПгк+г(х,у)) , те - г > к - 1,

-V Т1.К V ~ 5 I I оХг \ г где

РпЛ^у) = £ Ц1)впЛ*Ш-1)р^-ЬАУ)з=к 3 \К) р=о

Установлена алгебраическая и аналитическая сопряженность Р- и Т-полиномов.

Теорема 3.4. Имеют место следующие равенства: п г=к п

X) РпЛХ1У)Тьк(Х>У) = П > 1, 1 < к < П.

Теорема 3.5. Полиномы Тушара и Р-полиномы удовлетворяют соотношениям:

Тп,к{х,у) = РП]к(х,у), где функции х{{) и х(и) — взаимно-обратные, а у (и) = —у(х(и)).

С-полиномы Тушара СПук(х, у) = Сп^(х ь • • ■'■¡'У ь ■ • ■) можно задать при помощи соотношения

Сп,к(х,у) = 1™\Ск(х)Сп„к(у), 0 < к < те, п > 1, где Сп(£) = ., 1п) — цикловой индикатор симметрической группы. к д Обозначим Т>г(к) — Х^Ш^т-. 1

Теорема 3.6. С-полиномы удовлетворяют соотношениям: д (п\

Сп,к(х,у) = ( А (г - 1 )\Сп-г,к-{(х,у),к,( > 1,п > к, д (п\

-Сщк(х,у) = . (г - 2/), А: > 0, г > 1, те > к + г; г-ч /¿,ЛГ I 5 г/ / I •

А-1 п!

СП)к(х,у) = X) 77-:—-ттЖг-+1Спг-1^г-1(а;,г/). г=0 к(п-1- 1)!'

П — ¿ — 1 12!

Сщк(х,у) = £ 7-ттт^—:—-~у^1Сп^1,к(х,у), п,к >1; г=о {п — к)[п — г — 1)1

Сп,к{х, у) = (Ж1 + Т>х(к - 1))С„1)А1(ж, г/) + (2/1 + Т>у(п - к))Сп^ 1>А.(ж, у). к>1,п>к + 1.

В частных случаях получены новые соотношения для чисел Стир-линга и Лаха. Обсуждаются некоторые перечислительные интерпретации и приложения С-полиномов Тушара при описании одноканальной системы массового обслуживания (см. [46, 51, 57]).

Результаты параграфа 3.2 получены в нераздельном соавторстве с О.В. Леоновой.

В параграфе 3.3 исследуются обобщенные А- и В-полиномы.

Обобщенными А- и В-полиномами соответственно в [18] названы обобщения однородных полиномов Белла Ап^(х), которые имеются, например, в [136, с. 147], [174] и обобщения полиномов Платонова Вп>к(х), введеные в [81]. Ряд свойств обобщенных А- и В-полиномов установлен в [18, 81, 136, 174]. В статье [82] с помощью метода, предложенного в [169], строится множество полиномов, квазиортогональных к обобщенным В-полиномам.

Обобщенные А-полиномы А^(д) для фиксированного целого неотрицательного т могут быть определены как коэффициенты в суммах

1(£ £ к\ \г=т+1 / п=к{т+1) где дт+1 ф 0, к > 1.

Обобщенные В-полиномы В^ (д) для фиксированного натурального т задаются соотношениями: п—к где

9® t=0 Е дт ф 0, п > 1, 1 < к < г=га

П.

Известно [81], что 4%) - Ащк(д), В%) = Вп,к(д). Для обобщенных В-полиномов доказаны следующие теоремы. Теорема 3.7. Для натуральных п, к и г, таких, что г, к < п, т < г < п — к + т справедливы соотношения

9) = ~ т(п+ т - + ] ^^мМ

19

Теорема 3.8. Для к > 2, п> к — 1 справедливы соотношения: и »-*+"• /АЛ-« —1\ И , , ш(п + га — 1)! ( г

Для указанных полиномов выводятся различного рода рекуррентные формулы. Как следствия получены новые соотношения для обычных и г-присоединенных чисел Стирлинга, Лаха и ряда других известных комбинаторных чисел. Обсуждаются новые и известные перечислительные интерпретации и приложения [36, 40, 44, 56].

В параграфе 3.4 продолжено рассмотрение некоторых алгоритмических задач на дискретных конечных математических структурах. Построены соответствия и получены алгоритмы взаимных преобразований однородных полиномов Белла и Платонова, полиномов Платонова и обобщенных В-полиномов, а также Т-полиномов Тушара и Р-полиномов [35, 51].

В теореме 3.9 установлено соответствие, позволившее построить алгоритм 3.1 преобразования А<2П-2к,п-к(д) в Вп^{д) и ему обратный алгоритм 3.2 преобразования Вщк(д) в А2п-2к,п-к(д)

На основании теоремы 3.10, в которой установлено соответствие между слагаемыми в составе полиномов Вп^(д) и построен алгоритм 3.3 преобразования Вп^(д) в В^(д) при т > 1.

В статье Селиванова [81] приводится алгоритм получения полиномов В^(д), включающий пять этапов вычислений. При этом на отдельных этапах приходится вычислять еще и полиномы В^(п,к]д). Если известен явный вид полиномов А2П-2к,п-к{д)^ то последовательное применение алгоритмов 3.1 и 3.3 дает новый алгоритм построения полиномов В^к (<?)> более экономичный, чем полученный Селивановым.

В теореме 3.11 установлено соответствие, позволившее построить алгоритм 3.4, преобразующий полином Т2п-2к,п-к{х:у) в полином Рщк{х,у) и ему обратным алгоритм 3.5 преобразования Рп^(х,у) в

Т2п-2куп-к(х,у).

Теорема 3.11 и алгоритмы 3.4, 3.5 получены в нераздельном соавторстве с О.В.Леоновой.

Результаты, изложенные в третьей главе, опубликованы в работах [25, 35, 40, 42, 44, 46, 51, 57, 60, 61, 62, 56].

Четвертая глава посвящена приложениям изучаемых комбинаторных объектов при исследовании некоторых свойств конечных графов (параграфы 4.1 и 4.2) и построении моделей дискретных случайных процессов (параграфы 4.3 и 4.4).

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

В работах [194, 195, 201, 225] путем подсчета решетчатых путей на плоскости при некоторых ограничениях получен ряд комбинаторных тождеств. Решетчатые пути в двумерных и многомерных решетках и на некоторых специальных графах изучаются в частности в [106, 112, 183, 190]. Взвешенные пути в двумерных и многомерных решетках и их комбинаторные приложения изучаются в [9, 196, 115, 120].

В работах [9, 165, 255] для построения общей схемы перечисления помеченных путей на плоской целочисленной решетке используется аппарат функциональных цепных дробей.

Семейства чисел Каталана, Моцкина, Фибоначчи, Шредера, их свойства и некоторые обобщения, связанные в частности с путями на решетках, рассматриваются в [86, 131, 132, 142, 166, 187, 208, 209, 211, 222, 223, 228, 237, 239].

В данном параграфе рассматриваются некоторые вопросы перечисления путей Мак-Магона и Моцкина — траекторий на целочисленной решетке плоскости с ограничениями на приращение координат при переходе от одной точки к следующей.

Пусть и = (г, j) Е Z2. Тогда,;' называется высотой точки и и обозначается j = alt(u). Пусть щ,. — такая последовательность точек из Z2, что:

1) Щ = (0, jo);

2) ujfc+i = и* + (1,сгА), ак Е {-1,0,1}, 0 < к < /;

3) alt(u¿) > 0, 0 < к < I.

Тогда щ . щ называется пут,ем с началом щ и концом щ и обозначается (сг0. cr/i)¿0. Высотой пути (сг0 . 0"/-i)jo называется maxalt(w¿). Если г Е {—1,0,1), то (г),- называется шагом на высоте 0<k<l J j, который мы будем считать спадом, уровнем или подъемом, если г равно —1,0 или 1 соответственно. Если р = (р\. p¡)j, а а = (а\. ак)г оканчивается на высоте j, то ир = (eri. сг^ . pi)i.

Пусть — множество всех путей <т, у которых alt(wo) = alt(w/) = г и alt (р) > г для Vp G <т- Множество "Но будем называть множеством путей Моцкина.

Рассматриваем бесконечную нижнюю треугольную матрицу M = Н^и^Н, 0 < к < те, п > 0, где — число путей (сг0 . ап) G "Но с А; уровнями. Показано [56], что: т = {= 0, п-к = 1 (mod2), = -7-т( и„=Е№йп = Е . ]спг-, п>о. г=0 V где — триномиальные коэффициенты.

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

2 те - гл -I I 17---^* 1 О ' / ~ ' '--" ' I + г=0 \2г/ г=0 \ г

Теорема 4.1. Справедливы следующие утверждения:

1. Число путей (<7о.сг2п) £ ^е имеющих уровней, связано с числами Каталана Сп равенством т^п^ — Сп.

2. Количество путей (о"о . оп) £ Но связано с числами Моцкина Мп соотношением тп,к — Мп.

3. Число путей (о"о. 6 "Но с к уровнями связано с числами Шредера Нп соотношением Е^о^ тп-к,к — Йп/2

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

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

Корневые деревья изучаются в книгах [9, 15, 91] и др. Числа Каталана, Моцкина, Шредера и их некоторые обобщения рассматриваются, в связи с перечислением деревьев, в частности, в [134, 222, 141, 142, 144, 145, 162, 166, 189, 209, 221, 254].

В данном параграфе обсуждаются некоторые подходы к перечислению плоских корневых деревьев, обладающих определенными свойствами, причем их перечисление облегчается привлечением известных чисел Каталана и Шредера и новых, связанных с ними, комбинаторных чисел. Для рассматриваемых чисел выводятся рекуррентные формулы и соотношения, связывающие их с обычными и присоединенными числами Стирлинга второго рода, а также числами Белла, Каталана, Эйлера, Моцкина и др. [47, 52].

В утверждениях 4-1, 4-2 для числа Шредера £п и их обобщений, а также для введенных автором расщепленных чисел Шредера первого и второго рода, возникающих при перечислении некоторых классов помеченных корневых деревьев, выводятся рекуррентные формулы и соотношения, связывающие их с обычными и присоединенными числами Стирлинга второго рода и числами Эйлера и Белла.

Обычные и обобщенные числа Каталана, а также введенные автором расщепленные числа Каталана первого и второго рода, возникающие при перечислении некоторых классов непомеченных корневых деревьев, изучаются в утверждениях 4-3~4-5 и теореме 4.2. Для рассматриваемых чисел выводятся рекуррентные формулы и соотношения, связывающие их с числами Стирлинга второго рода.

Использованные в параграфе 4.2 формулировки и доказательства результатов из статей, написанных в соавторстве с Т.Г.Тюрневой, получены лично автором. Предварительные расчеты и таблицы 4.2-4.9 принадлежат Т.Г.Тюрневой.

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

Схемам, связанным с суммированием случайных величин и случайными блужданиями, посвящено огромное количество работ. Ограничимся ссылками только на две, давно ставшие классическими, монографии Спицера и Феллера [85, 90]. Отдельные случаи применения комбинаторных чисел и полиномов при описании случайных процессов встречались и ранее, достаточно упомянуть книгу Такача [87]. Близкое к обсуждаемому описание неоднородных случайных блужданий на прямой и процессов "чистого размножения" имеется в книге Платонова [71, §12].

Обобщения схемы Бернулли на случаи, когда вероятности успеха и неуспеха в отдельных испытаниях способны меняться после каждого испытания (А-схема) или после очередного успеха (В-схема) изучались в работах [14, 71].

Свойства элементов В- и А-треугольников и В- и А-пирамид существенно используются при описании распределений вероятностей неоднородных случайных блужданий по целым неотрицательным точкам прямой и первого квадранта плоскости, соответственно. Результаты интерпретируются в терминах процессов рождения и гибели [22, 26, 33].

Пусть частица из точки с координатами (к, /), которой она достигает за п шагов после выхода из начала координат, с вероятностью а(п, к, I) перемещается за один шаг в точку с координатами (к + 1, /), с вероятностью /3(п, к,1) — в точку с координатами (к, I + 1) и с вероятностью у(n,k,l) = 1 — а(п, к J) — /3(п, к, I) остается в точке с координатами (к,1) Обозначим и т]п — координаты частицы через п шагов после начала процесса.

Теорема 4.3. Справедливы следующие утверждения:

1. Если а(п, к, /) = ап, /3(п, к, I) — (Зп, 7(п, к, /) = уп, и B^j строятся на базах а, /3 и у, то

P(tn = k:r]n=l)=Blhn> 1.

2. Если а(п, к, I) = Р(п, к, I) = (Зк, 7(п, к,1) = уи Ah строятся на базах а, (3 и у, то

P(tn = k,rin=l)=Alhn> 1.

Получены также утверждения относительно некоторых числовых характеристик рассматриваемых случайных процессов (теоремы 4.4 и 4.5).

В теореме 4.6 при помощи чисел B%j и А\ j сформулированы утверждения относительно процессов рождения и гибели, развивающихся в стохастически неоднородных условиях.

Из статьи, написанной в соавторстве с Н.А. Колокольниковой, в параграфе 4.3 использованы только результаты, полученные лично автором.

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

Основные положения теории восстановления можно найти в монографии Кокса и Смита [21] (см. также [90]). Достаточно подробный обзор литературы по теории восстановления сделан в статье Севастьянова [80]. Методы теории восстановления находят широкое применение в различных областях науки и техники (например, [21, 74, 5]).

При помощи однородных полиномов Белла определяются распределения ряда ведущих характеристик простого дискретного процесса восстановления. Под последним понимается последовательность сумм

Со = о, а = а+6 +••• + 6, к>1 одинаково распределенных дискретных случайных величин с производящей функцией распределения д(¿) = дп^п? 9г ф 0.

Для любого к > 1 величину (к называют моментом к-го восстановления. При фиксированном t > 0 случайная величина ц = тах(к : (к < называется числом восстановлений до момента I.

При фиксированном / > 0, величины оц и определяемые равенствами

Щ — Сщ+1 А — ^ — называются соответственно перескоком и недоскоком относительно момента времени 1

Величина Н({) = Мип, где М — оператор математического ожидания, называется функцией восстановления.

Пусть дп = п\дп, п > 1. Возьмем нижние треугольные матрицы Ад = НА^)!!, п > 0, 0 < к < п, Ап>0(д) = 6п>0, А0,к{д) = ¿о,ь Ь = 1п,к = п > 1п,к — 0, п < к и диагональную матрицу С с элементами сП)П = п\, п > 0.

Теорема 4.7. Справедливы следующие утверждения:

1. Каждый к-й столбец матрицы 5 = С~1АдС выражает распределение случайной величины (к;

2. Каждая п-я строка матрицы N = Ь~1ЗЬ выражает распределение случайной величины

Найдены выражения величины Н{п) и распределений случайных величин ап и (Зп, если известно распределение случайной величины

Теорема 4.8. Справедливы следующие соотношения: п—1 гг—1

1- Н(п) = Е Е ВД-Ч-,*®, п > 2; к=1г—к

2. Р((Зп = з) = £ к\[{п - зЩ~1АпЧ:к{д) "£ [кЩ~1 А^к(д)~ к=1

-{к + ЩИУ'А^д)} , п > 1, 0 < з < п - 1; п+.? п—1

3. Р{ап=з) = £ ф + ЛГ1^,Е [(А - 1)!(г'!)1х к=1 г=Аг—1

Ряд авторов изучают различные обобщения простого процесса восстановления [21, 90, 110, 196]. В данном параграфе рассматриваются дискретные модели некоторых из них: процессы восстановления с запаздыванием, т-обобщенные, альтернирующие, с большим числом состояний, со случайным временем. Причем, при исследовании дискретных процессов восстановления со случайным временем (теоремы 4.9 и 4.10) существенно используются свойства как полиномов разбиений, так и элементов В- и А-треугольников.

В условиях конкретных задач искомыми являются не обязательно найденные элементы сложных распределений. Может оказаться, что доказанные соотношения требуется разрешить относительно различных величин, находящихся под знаком суммы. Предложенный подход позволяет, используя соотношения между матрицами, установленные в теоремах 4.7-4.10, получить ряд таких формул.

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

Результаты, изложенные в четвертой главе, опубликованы в работах [22, 24, 28, 29, 34, 38, 39, 41, 33, 47, 52], [14, гл.6] и [56, пар.7.2].

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

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

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

2. Введены новые комбинаторные объекты при помощи построения обобщенных пирамид Паскаля: обобщенные триномиальные коэффициенты первого и второго рода, обобщенные числа Фибоначчи и Трибо-наччи первого и второго рода, расщепленные числа Каталана и Шредера первого и второго рода, Р-полиномы разбиений. Найдены производящие функции, рекуррентные формулы и их явные представления. Найдены соотношения, связывающие введенные комбинаторные числа и полиномы с известными. Получены условия алгебраической и аналитической сопряженности Р-полиномов и Т-полиномов Тушара.

3. Разработан подход, основанный на выявлении связей между элементами одного или нескольких сечений обобщенной пирамиды Паскаля. С помощью данного подхода найден ряд соотношений для широко известных комбинаторных чисел и полиномов. Получены различные рекуррентные формулы для полиномов разбиений (Белла, Платонова, Селиванова, Тушара и др.), для элементарных и полных симметрических функций и комбинаторных чисел (Стирлинга, Лаха, Каталана, Шредера и др.), а также их обобщений. Построены алгоритмы взаимных преобразований изучаемых полиномов с линейной трудоемкостью.

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

По результатам, изложенным в диссертации, имеется 40 публикаций [14, гл.б], [22], [24]—[42], [44]—[62]. Результаты докладывались на Всесоюзных и международных конференциях по алгебре, дискретной математике, теоретической кибернетике, в том числе было сделано несколько пленарных докладов (VII Всесоюзная конференция "Проблемы теоретической кибернетики", Иркутск, 1985; II Всесоюзный семинар "Дискретная математика и ее приложения", Москва, 1988; совещание по дирижаблестроению в СССР, Москва, 1988; XXIII чтения К.Э.Циолковского, Калуга, 1988; III Сибирская школа по алгебре и анализу, Иркутск, 1989; V Всесоюзная школа-семинар "Современные проблемы механики жидкости и газа", Иркутск, 1990; III Всесоюзный семинар "Дискретная математика и ее приложения", Москва, 1990; XXV чтения К.Э.Циолковского, Калуга, 1990; Всесоюзная школа "Дискретная математика и ее применение при моделировании сложных систем", Иркутск, 1991; IV межгосударственный семинар "Дискретная математика и ее приложения", Москва, 1993; I Международная конференция по экранопланам, Иркутск, 1993; Восточно-Сибирская зональная межвузовская конференция "Математика и проблемы ее преподавания в вузе", Иркутск, 1999; конференция "Математика и ее приложения", посвященная памяти профессора А.И.Кокорина и 275-летию РАН, Иркутск, 1999; международная конференция "Дискретный анализ и исследование операций", Новосибирск, 2000; международная конференция "Математика, информатика и управление", Иркутск, 2000; VII Международный семинар "Дискретная математика и ее приложения", Москва, 2001; XII Байкальская международная конференция "Методы оптимизации и их приложения", Иркутск, Байкал, 2001; II Международная конференция "Математическое моделирование в науке, образовании и промышленности", Тирасполь, 2001; XIY Международная конференция "Математика в вузе", Псков, 2001.).

Были сделаны доклады в ведущих научных центрах: Московский государственный университет (механико-математический факультет), Санкт-Петербургский государственный университет (математико-ме-ханический факультет), Новосибирский государственный университет (механико-математический факультет), Математический институт РАН им. В.А. Стеклова (г. Москва), Институт математики СО РАН (г. Новосибирск), Университет Христиана Альбрехта (г. Киль, ФРГ), Институт динамики систем и теории управления СО РАН (г. Иркутск), Иркутский государственный университет.

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

Заключение

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

Разработанные модели, алгоритмы и компьютерные программы использовались в научных исследованиях лаборатории комплексов ИГУ.

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

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

2. Алакоз A.B., Титовский И.Н. Исследования характеристик интенсивной турбулентности и экстремальных дискретных порывов // Учен. зап. ЦАГИ. 1987. - Т. 18, № 4. - С. 74-81.

3. Альбертьян М.К. Отображения частично упорядоченных множеств и обобщенные числа Стирлинга // Сб. тр. ВНИИ систем, исслед. 1982. - № 10. - С. 142-145.

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

5. Ватутин В.А., Телевинова Т.М., Чистяков В.П. Вероятностные методы в физических исследованиях. М.: Наука, 1985. - 208 с.

6. Васильев A.A., Глазунов В.Г. Сдвиг ветра, турбулентность и вертикальные потоки в нижнем слое атмосферы, влияющие на взлет и посадку воздушных судов. Д.: Гидрометеоиздат, 1979. - 71 с.

7. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд. - М.: Наука, 1987. - 336 с.

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

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

10. Динамическое нагружение самолета при полете в неспокойном воздухе // Обзоры / ОНТИ ЦАГИ. 1986. - № 663. - 110 с.

11. Добровольский М.Н. О числе перестановок элементов п пар с двумя ограничениями позиций // Вестн. Моск. ун-та. Матем., механ.- 1966. № 5. - С. 36-40.

12. Докин В.Н. О треугольной схеме развития популяций // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1977. - Вып. 41. - С. 104-106.

13. Докин В.Н. Асимптотическая нормальность некоторых специальных чисел // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1979. - Вып. 49. - С. 202-207.

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

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

16. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука. Сиб. отд-ние, 1977. -285 с.

17. Жуков В.Д. Производящий определитель // Асимптотич. и перечислит. задачи комбинат, анализа. Красноярск: Краснояр. ун-т, 1976. - С. 47-58.

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

19. Жуков В.Д. О связи В-полиномов с коэффициентами разложения операторов Ли // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1990. - Вып. 91. - С. 220-223.

20. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976. - 735 с.

21. Кокс Д., Смит В. Теория восстановления. М.: Сов. радио, 1967.- 299 с.

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

23. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. - 480 с.

24. Кузьмин О.В. Применение комбинаторных полиномов при описании процессов восстановления // VII Всесоюз. конф. Проблемы теоретической кибернетики: Тез. докл. Иркутск, 1985. - 4.1. -С. 111-112.

25. Кузьмин О.В., Платонов М.Л. Расчет монотонно неубывающих потоков частиц, однородных в каждом поколении // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1986- Вып. 75. С. 215-220.

26. Кузьмин О.В. Обобщенные триномиальные коэффициенты и их применения // Тез. конф. молодых ученых Сибири и Дальн. Востока. Новосибирск: Новосиб. ун-т, 1987. - С. 41-44.

27. Кузьмин О.В. Новые рекуррентные формулы для полиномов разбиений // Тез. II конф. молодых ученых Сибири и Дальн. Востока.- Новосибирск: Новосиб. ун-т, 1988. С. 79-82.

28. Кузьмин О.В. Описание некоторых процессов восстановления с использованием комбинаторных полиномов // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1988. -Вып. 80. - С. 141-148.

29. Кузьмин О.В. Описание некоторых видов сложных дискретных распределений // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1988. - Вып. 82. - С. 52-60.

30. Кузьмин О.В. Взаимные преобразования элементарных и полных симметрических функций // Исслед. по геомагнетизму, аэрономии и физике Солнца. М., 1988. - Вып. 82. - С. 203-206.

31. Кузьмин О.В. Преобразования элементарных и полных симметрических функций и их применения // Тр. семинара по дискр. математике и ее приложениям / Под ред. О.Б.Лупанова. М.: Изд-во МГУ, 1989.- С. 285.

32. Кузьмин О.В. Обобщенные триномиальные коэффициенты и их построение в пространстве отображений // Теоретические и прикладные вопросы в задачах управления и анализа систем. Иркутск: ИрВЦ СО АН СССР, 1989. - С. 64-78.

33. Кузьмин О.В. "Трехточечная" модель турбулентной атмосферы // Совр. проблемы механики жидкости и газа: Тез. докл. V Все-союз. шк.-семинара. Иркутск, 1990. - С. 200.

34. Кузьмин О.В. Взаимные преобразования некоторых полиномов разбиений // Алгоритм, и комбинат, вопросы дискр. систем и ЭВМ. Иркутск: Иркут. ун-т, 1990. - С. 71-79.

35. Кузьмин О.В. Новые рекуррентные соотношения для обобщенных А- и В-полиномов // Пятая школа молодых математиков Сибири и Дальн. Востока: Тез. докл. Новосибирск: ИМ СО АН СССР, 1990. - С. 60-63.

36. Кузьмин О.В. Новые рекуррентные соотношения для полиномов разбиений // Алгоритм, и комбинат, задачи дискр. систем и ЭВМ. Иркутск: Иркут. ун-т, 1991. - С. 74-82.

37. Кузьмин О.В. Дискретная модель турбулентной атмосферы // Ирк. ун-т. Иркутск, 1992.- 15 с. Деп. в ВИНИТИ 25.03.92. -№ 1020 - В92 ДЕП.

38. Кузьмин O.B. Построение обобщенных А- и B-полиномов в пространстве отображений // Методы дискретного анализа в теории графов и сложности. Новосибирск: ИМ СО РАН, 1992. - Вып. 52. - С. 66-76.

39. Кузьмин О.В. О моделировании воздействий турбулентной атмосферы на полет экраноплана //Первая Между нар. конф. по экра-нопланам: Тез. докл. Иркутск, 1993. - С. 61-62.

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

41. Кузьмин О.В. Введение в перечислительную комбинаторику. -Иркутск: Иркут. ун-т, 1995. 112 с.

42. Кузьмин О.В. Обобщенные А- и B-полиномы и их построение в пространстве отображений //Сб. тр. семинара по дискр. математике и ее приложениям / Под ред. О.Б.Лупанова. М.: Изд-во мех.-мат. ф-та МГУ, 1997.- С. 164.

43. Кузьмин О.В. Некоторые комбинаторные числа в обобщенной пирамиде Паскаля // Асимптотич. и перечислит, задачи комбинат, анализа. Иркутск: Иркут. ун-т, 1997. - С. 90-100.

44. Кузьмин О.В., Леонова О.В. О полиномах Тушара // Асимптотич. и перечислит, задачи комбинат, анализа. Иркутск: Иркут. ун-т, 1997. - С. 101-109.

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

46. Кузьмин О.В. Обобщенная пирамида Паскаля // Сб. тр. семинара по дискр. математике и ее приложениям (2-4 февраля 1993 г.) / Под ред. О.Б.Лупанова. М.: Изд-во мех.-мат. ф-та МГУ, 1998.-С. 93-94.

47. Кузьмин О.В., Леонова О.В. О некоторых свойствах полиномов разбиений // Тр. Вост.-Сиб. зональной межвуз. конф. по математике и проблемам ее преподавания в вузе. Иркутск: Изд-во Иркут. пед. ун-та, 1999. - С.158-159.

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

49. Кузьмин О.В., Леонова О.В. Полиномы Тушара и им квазиортогональные // Оптимизация, управление, интеллект, 1999. Вып. 3. - С. 218-227.

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

51. Кузьмин О.В. Обобщения чисел Фибоначчи и Трибоначчи // Оптимизация, управление, интеллект, 2000. Вып. 4. - С. 188— 198.

52. Кузьмин О.В. Комбинаторные полиномы разбиений в обобщенной пирамиде Паскаля // Междунар. конф. "Дискретный анализ и исследование операций": Материалы конф. (г. Новосибирск, 26 июня 1 июля 2000).- Новосибирск: Изд-во Ин-та математики, 2000.- С. 75.

53. Кузьмин О.В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал, 2000.- Т.6, № 5.- С. 101-109.

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

55. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения // Дискретная математика, 2000, Т.12, вып. 3.- С. 60-71.

56. Кузьмин О.В. Комбинаторные числа и полиномы в обобщенной пирамиде Паскаля // Оптимизация, управление, интеллект, 2000.- Вып. 5.- С. 153-163.

57. Кузьмин О.В. Полиномы разбиений в обобщенной пирамиде Паскаля // Мат. VII Междунар. сем. "Дискр. математика и ее приложения" (29 янв.-2 февр. 2001 г.).- Ч.Ш.- М: Изд-во мат.-мех. ф-та МГУ, 2001.- С. 370-376.

58. Кузьмин О.В., Леонова О.В. Некоторые свойства полиномов Ту-шара // Мат. VII Междунар. сем. "Дискр. математика и ее приложения" (29 янв.-2 февр. 2001 г.).- Ч.Ш.- М: Изд-во мат.-мех. ф-та МГУ, 2001.- С. 376-378.

59. Кузьмин О.В., Леонова О.В. О полиномах разбиений // Дискретная математика, 2001, Т.13 Вып. 2.- С. 144-158.

60. Кузьмин О.В., Леонова О.В. Об аналитической сопряженности полиномов Тушара и им квазиортогональных // Дискретная математика, 2002, Т.14.- Вып. 1- С. 151-158.

61. Кук Р. Бесконечные матрицы и пространства последовательностей. М.: Физматгиз, 1960. - 472 с.

62. Левин В.И. Метод анализа случайных процессов с независимыми приращениями и дискретными состояниями // Автоматическое управление. Рига: Зинатне, 1967. - С. 207-219.

63. Макдональд И. Симметрические функции и многочлены Холла. -М.: Мир, 1985. 224 с.

64. Мокроносов B.C. Триномиальная формула // Исслед. алгебр, систем по свойствам их подсистем. Свердловск, 1987. - С. 81-87.

65. Обрубов А.Г., Грязин В.Е. Динамика самолета в условиях сдвига ветра // Труды ЦАГИ. М., 1983. - Вып. 2163. - 24 с.

66. Платонов М.Л. Обобщения чисел Стирлинга // Краткие сообщ. о науч.-исслед. работах за 1960 г. Иркутск: Иркут. ун-т, 1962. - С. 65.

67. Платонов М.Л., Докин В.Н. Треугольная схема развития популяций // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1975. - Вып. 35. - С. 26-31.

68. Платонов М.Л. Обращения формулы Бруно // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1975 -Вып. 35. - С. 32-38.

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

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

71. Платонов М.Л. Комбинаторные полиномы в алгебре операторов, перестановочных со сдвигом // Дискретная математика, 1992, Т. 4, Вып. 1, С. 33-49.

72. Прабху Н. Стохастические процессы теории запасов. М.: Мир, 1984. - 184 с.

73. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

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

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

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

77. Сачков В.Н. Комбинаторные методы дискретной математики. -М.: Наука, 1977. 320 с.

78. Севастьянов Б.А. Теория восстановления // Итоги науки и техники. Теория вероятностей. Матем. статистика. Теор. кибернетика. Т.П. - М.: ВИНИТИ, 1974. - С. 99-129.

79. Селиванов Б.И. Комбинаторный подход к формуле обращения Бюрмана Лагранжа // Комбинат, и асимптотич. анализ. -Красноярск: Краснояр. ун-т, 1977. - С. 153-169.

80. Селиванов Б.И. О комбинаторных функциях, связанных с рядом Бюрмана Лагранжа. Соотношения квазиортогональности // Дискретная математика. - 1998. - Т. 10, вып. 1. - С. 126-140.

81. Силин В.Б. Поиск структурных решений комбинаторными методами. М.: Изд-во МАИ, 1992. - 216 с.

82. Скороход А.В. Случайные процессы с независимыми приращениями. 2-е изд. М.: Наука, 1986. - 320 с.

83. Спитцер Ф. Принципы случайного блуждания. М.: Мир, 1969.- 472 с.

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

85. Такач Л. Комбинаторные методы в теории случайных процессов.- М.: Мир, 1971. 264 с.

86. Тишлер М., Джеке X. Действие турбулентной атмосферы на комбинированный дирижабль // ЭИ "Авиастроение". М. - 1983. -№ 17. - С. 8-19.

87. Успенский В.А. Треугольник Паскаля. 2-е изд. - М.: Наука, 1979. - 48 с.

88. Феллер В. Введение в теорию вероятностей и ее приложения. -Т.1. М.: Мир, 1984. 528 с.

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

90. Хитч X. Системы активного управления для гражданского самолета // Технич. информация / ОНТИ ЦАГИ, 1980. № 21-22. -С. 17-25.

91. Хоменко М.П., Строк В.В. Некоторые комбинаторные тождества для сумм композиционных коэффициентов // Укр. мат. журн. -1971. Т. 23, № 6. - С. 830-837.

92. Эндрюс Г. Теория разбиений. М.: Наука, 1982. - 256 с.

93. Эткин Б. Атмосферная турбулентность и ее влияние на полет // Ракетная техника и космонавтика. 1983. - Т. 20, № 3. - С. 154179.

94. Яблонский С.В. Введение в дискретную математику. 2-е изд. -М.: Наука, 1986. - 384 с.

95. Abramson М. Certain distributions of unlike object into cells // Math. Mag. 1970. - Vol. 43, № 4. - P. 214-218.

96. Agarwal A.K. Properties of recurring sequence // Fibonacci Quart. 1989. - Vol. 27, № 2. - P. 169-175.

97. Agronomov M. Sur une suite recurrente // Mathesis. 1914. - Vol. 4, № 5. - P. 125-126.

98. Ahuja J.C., Enneking E.A. Convolution of independent left-truncated negative binomial variables and limiting distributions // Ann. Inst. Statist. Math. 1974. - Vol. 26. - P. 265-270.

99. Ahuja J.C., Enneking E.A. Concavity property and a recurrence relation for associated Lah numbers // Fibonacci Quart. 1979. -Vol. 17, № 2. - P. 158-161.

100. Alexanderson G.L., Klosinski L.F. A Fibonacci analogue of Gaussian binomial coefficients // Fibonacci Quart. 1974. - Vol. 12, № 2. - P. 129-132.

101. Alfonso M., Hartung P. Pascal's pyramid // Pentagon. 1977. - Vol. 36, № 2. - P. 89-92.

102. Alladi K., Hoggatt V.E.,Jr. On Tribonacci numbers and ralated functions // Fibonacci Quart. 1977. - Vol. 15, № 1. - P. 42-45.

103. Ando S., Sato D. A GCD property on Pascal's pyramid and the corresponding LCM property on modified Pascal pyramid // Applications of Fibonacci numbers. Dordrecht: Kluwer Acad. Publ., 1990. - P. 7-14.

104. Barbosa R.M., Godinho P.H. Descrigao das classes de caminhos progressivos com conceitos de distancia // Rev. Mat. e Estat. 1994, Vol. 12. - P. 85-98.

105. Basil M. Pascal's pyramid // Math. Teacher. 1968. - Vol. 61, № 1.- P. 19-21.

106. Bell E.T. Partition polynomials // Ann. Math. 1927. - Vol. 29. -P. 38-46.

107. Bell E.T. Exponential polynomials // Ann. Math. 1934. - Vol. 35.- P. 258-277.

108. Benoumhani M. On Whitmey numbers of Dowling lattices // Discrete Math. 1996. Vol. 159, № 1-3. - P. 13-33.

109. Bezuszka S., DAngelo L. An application of tribonacci numbers // Fibonacci Quart. 1977. - Vol. 15, № 2. - P. 140-144.

110. Bodroza O. Enumeration of oriented walks in digraphs using system of recurrence relations // 36. рад. Прир.-мат. фак. Сер мат. / Унив. Новом Саду. 1995. - Vol. 25, № 1. - Р. 129-140.

111. Boisen M.B.,Jr. Overlays of Pascal's Triangle // Fibonacci Quart. -1969. Vol. 7, № 2. - P. 131-139.

112. Bollinger R.C. A note on Pascal-T triangles, multinomial coefficients, and Pascal Pyramid // Fibonacci Quart. 1986. - Vol. 24, № 2. - P. 140-144.

113. Buze^eanu §.N, Domoco§ V. Polynomial identities from weighted lattice path counting // Discrete Math. 1996. Vol. 150, № 1-3.- P. 421-425.

114. Cadogan C. Some generalizations of the Pascal triangle // Math. Mag. 1972. - Vol. 45, № 3. - P. 158-162.

115. Cakic N.P. The complete Bell polynomials and numbers of Mitrinovic //Publ. Elektrotehn. Fak. Ser. Mat. / Univ. Beograd. 1995. - Vol. 6. - P. 74-78.

116. Carlitz L. Generating function for power of certain sequences of numbers // Duke Math. J. 1962. - Vol. 29, № 4. - P. 521-537.

117. Carlitz L. A basic analog of the multinomial theorem // Scripta Math.- 1963. Vol. 26, № 4. - P. 317-321.

118. Carlitz L., Roselle D.P., Scoville R.A. Some remarks on ballot-type sequences of positive integers // J. Combin. Theory, ser A. 1971. -Vol. 11, № 3. - P. 258-271.

119. Carlitz L. A combinatorial property of g-Eulerian numbers // Amer. Math. Monthly. 1975. - Vol. 82, № 1. - P. 51-54.

120. Carlitz L. A note on g-Eulerian numbers //J. Combin. Theory, ser A. 1978. - Vol. 25, № 1. - P. 90-94.

121. Carlitz L. Degenerate Stirling, Bernoulli and Eulerian numbers // Util. Math. 1979. - Vol. 15. - P. 51-88.

122. Carlitz L. Weighted Stirling numbers of the first and second kind. I // Fibonacci Quart. 1980. - Vol. 18, № 2. - P. 147-162.

123. Carlitz L. Weighted Stirling numbers of the first and second kind. II // Fibonacci Quart. 1980. - Vol. 18, № 3. - P. 242-257.

124. Cerasoli M. Two identities between Bell polynomials and Fibonacci numbers // Boll. Unione. Mat. Ital., ser. 5. 1981- Vol. 18 A, № 3.- P. 387-394.

125. Charalambides Ch.A. On the generalized discrete distributions and the Bell polynomials // Sankhya. 1977. - Vol. 39, Ser. B, № 1. - P. 36-44.

126. Charalambides Ch.A. Bipartitional polynomials and their applications in combinatorics and statistics // Discrete Math. 1981. Vol. 34, № 1. - P. 81-84.

127. Charalambides Ch.A., Chrysaphinou O. Partition polynomials in fluctuation theory // Math. Nachr. 1982. - Vol. 106. - P. 89-100.

128. Chrysaphinou O. On Touchard polynomials // Discrete Math. 1985.- Vol. 54. P. 143-152.

129. Chu W. A new combinatorial interpretation for generalized Catalan numbers // Discrete Math. 1987. - Vol. 65, № 1. - P. 91-94.

130. Church C.A.,Jr. Lattice paths and Fibonacci and Lucas numbers // Fibonacci Quart. 1974. - Vol. 12, № 4. P. 366-368.

131. Comtet L. Polinômes de Bell et formule explicite des dérivées successives d'une fonction inplicite // C. R. Acad. Sci., Paris, Série A. 1968. - Vol. 267, № 14. - P. 457-460.

132. Comtet L. Sur le quatrième problème et les nombres de Schroder // C. R. Acad. Sci., Paris, Série A. 1970. - Vol. 271, № 19. - P. 913-916.

133. Comtet L. Une formule explicite pour les puissances successives de l'opérateur de dérivation de Lie // C. R. Acad. Sci., Paris, Série A.- 1973. Vol. 276, № 3. - P. 165-168.

134. Comtet L. Advanced Combinatorics. Dordrecht, Boston: Reidel, 1974. - 343 p.

135. Constantineau I., Labelle G. Une généralisation automorphe des nombres de Stirling // Discrete Math. 1996. - Vol. 157, № 1-3.- P. 53-64.

136. Damiani E., D'Antona O., Regonati F. Whitney numbers of some geometric lattices //J. Combin. Theory, ser A. 1994. - Vol. 65, №1. P. 11-25.

137. Di Cave A., Ricci P.E. Sui polinomi di Bell ed i numeri di Fibonacci e di Bernoulli // Matematiche. 1980 (1983). - Vol. 35, № 1-2. - P. 84-95.

138. Dillon J.F., Roselle D.P. Eulerian numbers of higher order // Duke Math. J. 1968. - Vol. 35, № 2. - P. 247-256.

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

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

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

142. Dulucq S., Guibert O. Stack words, standard tableaux and Baxter permutations // Discrete Math. 1996. - Vol. 157, № 1-3. - P. 91106.

143. Ehrenborg R., Méndez M. Schroder parenthesizations and chordates 11 J. Combin. Theory, ser A. 1994. - Vol. 67, № 2. - P. 127-139.

144. El-Desouky B.S. The multiparameter noncentral Stirling numbers // Fibonacci Quart. 1994. - Vol. 32, № 3. - P. 218 225.

145. Enneking E.A., Ahuja J.C. Generalized Bell numbers // Fibonacci Quart. 1976. - Vol. 14, № 1. - P. 67-73.

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

147. Feinberg M. Fibonacci Tribonacci // Fibonacci Quart. - 1963. -Vol. 1, № 3. - P. 71-74.

148. Feinberg M. New slants // Fibonacci Quart. 1964. - Vol. 2, № 2. -P. 223-227.

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

150. Foata D., Schutzenberger M.-P. Théorie géométrique des polynômes Eulériens // Lect. Notes Math. 1970. - Vol. 138.

151. Fontené G. Generalization d'une formule connue // Nouv. Ann. Math. 1915, Vol. 15, №. - P. 112.

152. Foulkes H.O. A nonrecursive combinatorial rull for Eulerian numbers // J. Combin. Theory, ser A. 1977. - Vol. 22, № 2. P. 246-248.

153. Fripertinger H. Enumeration of linear codes by applying methods from algebraic combinatorics // Graz. Math. Ber. 1996 (1997). -Vol. 328. - P. 31-42.

154. Frucht R.W., Rota G.-C. Polynomios de Bell y partitiones de conjuntos finitos // Scientia. 1965. - Vol. 32, № 126. - P. 5-10.

155. Frucht R.W. Polinomios para composiciones de numéros, una genetalizacion de los polinomios de Bell // Scientia. 1965 (1966). -Vol. 32, № 128. - P. 49-54.

156. Furlinger J., Hofbauer J. ^-Catalan numbers //J. Combin. Theory, ser A. 1985. - Vol. 40, № 2. - P. 248-264.

157. Garsia A.M., Remmel A.M. A1 combinatorial interpretation of q-Derangement and g-Laguerre numbers //Europ. J. Combinatorics.- 1980. Vol. 1. - P. 47-59.

158. García C. Una generalización der triángulo de Pascal // Rev. Real. Acad. Ci. Exact. Fis. Natur. Madrid. 1967. - Vol. 61, № 2. - P. 147-153.

159. Gessel I.M. A ç-analog of the exponential formula // Discrete Math.- 1982. Vol. 40, № 1. - P. 69-80.

160. Goldman J.R. Formal languages and enumeration //J. Combin. Theory, ser A. 1978. - Vol. 24, № 3. - P. 318-338.

161. Gould H.W. The bracket function and Fontené-Ward generalized binomial coefficients with application to fibonomial coefficients // Fibonacci Quart. 1969. - Vol. 7, № 1. - P. 23-40.

162. Gould H.W., Hopper A.T. Operational formulas connected with two generalizations of Hermite polynomials // Duke Math. J. 1962. Vol. 29, № 1. - P. 51-63.

163. Goulden I.P., Jackson D.M. Path generating functions and continued fractions // J. Combin. Theory, ser A. 1986. - Vol. 41, № 1. - P. 1-10.

164. Gouyou-Beauchamps D., Vauquelin B. Deux propriétés des nombres de Schroder // Inf. théor. et Appl. 1988. - Vol. 22, № 3. - P. 361388.

165. Grabski F. O wielostanowym procesie odnowy // Zesz. nauk. WSMW. 1977. - Vol. 18, № 4. - P. 87-97.

166. Green T.M., Hamberg C.L. Pascal's Triangle. Palo Alto: Dale Seymour, 1986. - 280 p.

167. Henrici P. An algebraic proof of the Lagrange-Bürmann formula // J. Math. Anal, and Appl. 1964. - Vol. 8, № 2. - P. 218-224.

168. Hoggatt V.E.,Jr. Fibonacci numbers and generalized binomial coefficients // Fibonacci Quart. 1967. - Vol. 5, № 4. - P. 383-400.

169. Hoggatt V.E.,Jr. A new angle on Pascal's triangle // Fibonacci Quart. 1968. - Vol. 6, № 4. - P. 221-234.

170. Hoggatt V.E.,Jr. Generalized Fibonacci numbers in Pascal's pyramid // Fibonacci Quart. 1972. - Vol. 10, № 3. - P. 271-275, 293.

171. Holte J.M. A Lucas-type theorem for Fibonacci-coefficient residues // Fibonacci Quart. 1994. - Vol. 32, № 1. - P. 60-68.

172. Howard F.T. Bell polynomials and degenerate Stirling numbers // Rend. Sem. Mat. Univ. Padova. 1979 (1980). - Vol. 61. - P. 203219.

173. Howard F.T. A special class of Bell polynomials // Math. Comput.- 1980. 35, № 151. - P. 977-989.

174. Howard F.T. Associated Stirling numbers // Fibonacci Quart. 1980- Vol. 18, № 4. P. 303-315.

175. Howard F.T. A theorem relating potential and Bell polynomials // Discrete Math. 1982. - Vol. 39, № 2. - P. 129-143.

176. Howard F.T. Degenerate weighted Stirling numbers // Discrete Math. 1985. - Vol. 57, № 1-2. - P. 45-58.

177. Hsu L.C. Generalized Stirling number pairs associated with inverse relations // Fibonacci Quart. 1987. - Vol. 25, № 4. - P. 346-351.

178. Hsu L.C. Some theorem on Stirling-type pairs // Proc. Edinburg. Math. Soc. 1993. - Vol. 36, № 3. - P. 325-335.

179. Hsu L.C., Mullen G.L., Shiue P. J.-S. Dickson-Stirling numbers // Proc. Edinburgh Math. Soc. 1997. - Vol. 40, № 3. - P. 409 423.

180. Johnson W.P. Some applications of the ^-exponential formula // Discrete Math. 1996. - Vol. 157, № 1-3. - P. 207-225.

181. Kaparthi S., Rao H.R. Higher dimensional restricted lattice paths with diagonal steps // Discrete Appl. Math. 1991. - Vol. 31, № 3.- P. 279-289.

182. Krattenthaler C. Counting lattice paths with a linear Boundary II: g-ballot and g-Catalan numbers // Sitzungsber. Osterr. Akad. wiss. Abt. 2. Math.-naturwiss. Kl. Abt. 2. 1989. - Vol. 198, № 4-7. - P. 171-199.

183. Krattenthaler C., Sulanke R.A. Counting pairs of nonintersecting lattice paths with respect to weighted turns // Discrete Math. 1996.- Vol. 153, № 1-3. P. 189-198.

184. Krouse D., Olive G. Binomial functions with the Stirling property // J. Math. Anal, and Appl. 1981. - Vol. 83, № 1. - P. 110-126.

185. Kyriakoussis A.G. On extended generalized Stirling pairs // Fibonacci Quart. 1993. - Vol. 31, № 1. - P. 44-52.

186. Lagrange R. Deux problèmes de répartition mixte // Bull. sci. math., ser. 2. 1962. - Vol. 86, № 3. - P. 81-88.

187. Lucas J.F. Paths and Pascal numbers // College Math. J. 1983. -Vol. 14. - P. 329-341.

188. McGregor J.R., Narayana T.V., Ozsoyoglu Z.M. On touchings, crossings and meetings of lattice paths with the diagonal // Util. Math. 1986. - Vol. 30. - P. 45-51.

189. MacMahon P.A. Combinatory Analysis. 2 vols. - Cambridge: Cambridge Univ. Press, 1915, 1916; reprinted New York: Celsea, 1960.

190. Magagnosc D. Recurrences and formulae in an extension of the Eulerian numbers // Discrete Math. 1980. - Vol. 30, № 3. - P. 265-268.

191. Mueller S. Recursions associated with Pascal's pyramid //Pi Mu Epsilon J. 1969. - Vol. 10. - P. 417-422.

192. Nandi S.B., Dutta S.K. On associated and generalized Lah numbers and applications to discrete distributions // Fibonacci Quart. 1987. - Vol. 25, № 2. - P. 128-136.

193. Nelsen R.B., Schmidt H.,Jr. Chains in power sets // Math. Mag. -1991. Vol. 64, № 1. - P. 23-31

194. Niculescu S.P. An asymptotic renewal theorem for m-general renewal processes // Bull. math. Soc. Sci. math. RSR. 1978. - Vol. 22, № 1. - P. 55-59.

195. Nilsson E.W., Sundell P. A new relation among Catalan numbers // J. Math. Phys. 1995. - Vol. 36, № 10. - P. 6028-6042.

196. Nilton P., Pedersen J. Catalan numbers, their generalization, and their uses // Math. Intell. 1995. - Vol. 13, № 2. - P. 64-75.

197. Nugent J. Notes on Pascal's pyramid for personal computer users // Comput. k Graphics. 1991. - Vol. 15, № 2. - P. 303-311.

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

199. Philippou A.N., Muwafi A.A. Waiting for Kth consequetive success and the Fibonacci sequence of order K // Fibonacci Quart. 1982.- Vol. 20, № 1. P. 28-32.

200. Philippou A.N. A note on the Fibonacci sequence of order K and the multinomial coefficients // Fibonacci Quart. 1983. - Vol. 21, № 2.- P. 82-86.

201. Pla J. On the existence of couples of second-order linear recurrences with reciprocal representation properties for their Fibonacci sequences // Fibonacci Quart. 1996. - Vol. 34, № 5.- P. 409-412.

202. Polya G., Alexanderson G.L. Gaussian binomial coefficients // Elem. Math. 1971. - Vol. 26, № 5. - P. 102-109.

203. Putz J.F. The Pascal polytope: an extension of Pascal's triangle to N dimensions // College Math. J. 1986. - Vol. 17, № 2. - P. 144-155.

204. Raab J.A. A generalization of the connection between the Fibonacci sequence and Pascal's triangle // Fibonacci Quart. 1963. - Vol. 1, № 3. - P. 21-31.

205. Rabinowitz S. Algorithmic manipulation of third-order linear recurrences // Fibonacci Quart. 1996. - Vol. 34, № 5. - P. 409412.

206. Rawlings D. The r-major index //J. Combin. Theory, ser A. 1981.- Vol. 31, № 2. P. 175-183.

207. Rawlings D. The (g,r)-Simon Newcomb problem // Linear and Multilinear Algebra. 1981. - Vol. 10, № 3. - P. 252-260.

208. Riordan J. Enumeration of plane trees by branches and endpoints // J. Combin. Theory, ser A. 1975. - Vol. 19, № 2. - P. 214-222.

209. Riordan J. The blossoming of Schroder's fourth problem // Acta Math. 1976. - Vol. 137, № 1-2. - P. 1-16.

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

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

212. Rohatgi V.K. Some combinatorial identities involving lattice paths // Amer. Math. Monthly. 1966. - Vol. 73, № 5. - P. 507-508.

213. Rosethal E.R. A Pascal pyramid for trinomial coefficients // Math. Teacher. 1961. - Vol. 54, № 5. - P. 336-338.

214. Sami Z. A sequence of numbers // Glas. Mat. 1988. - Vol. 23, № 1. - P. 3-13.

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

216. Schwandt A., Lind J. Revisiting Pascal's pyramid // Math. Teacher. 1979. - Vol. 72, № 2. - P. 84-86.

217. Shannon A.G. Tribonacci numbers and Pascal's pyramid // Fibonacci Quart. 1977. - Vol. 15, № 3. - P. 268, 275.

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

219. Shorter J., Stein F.M. Pascal's tetrahedron and the trinomial coefficients // Pentagon. 1982. - Vol. 42, № 1. - P. 19-33.

220. Shrivastova P.N. On generalised Stirling numbers and polynomials // Riv. Mat. Univ. Parma, ser 2. 1970. - Vol. 11,- P. 233-237.

221. Sloane N.J. A handbook of integer sequences. New York, London: Academic Press, 1973. - 206 p.

222. Spitzer F. A combinatorial lemma and its applications to probability theory // Trans. Am. Math. Soc. 1956. - Vol. 82. - P. 323-339.

223. Staib J., Staib L. The Pascal pyramid // Math. Teacher. 1978. -Vol. 71, № 6. - P. 505-510.

224. Stanley R.P. The Fibonacci lattice // Fibonacci Quart. 1975. - Vol. 13, № 3. - P. 215-232.

225. Sugihara M., Murota К. Multi-dimensional Bell polynomials // Util. Math. 1982. - Vol. 22. - P. 265-291.

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

227. Sved M. Gaussians and binomials // ARS Combinatoria. 1984. -Vol. 17A. - P. 325-351.

228. Tauber S. On quasi-orthogonal numbers // Amer. Math. Monthly. -1962. Vol. 69. - P. 365-372.

229. Tauber S. On generalised Lah-numbers // Proc. Edinburgh Math. Soc. 1965. - Vol. 14, № 3. - P. 229-232.

230. Tauber S. On K-numbers // Fibonacci Quart. 1973. - Vol. 11, № 2. - P. 179-183.

231. Todorov P.G. New defferential recurrence relations for Bell polynomials and Lie coefficients // Докл. Болг. АН. 1985. - Vol. 38, № 1. - P. 43-45.

232. Toscano L. Numeri di Stirling generalizzati, operatori difïerenzialie polinomi ipergeometrici // Commentât. Pontificia Ac. Sci. 1939. -Vol. 3. - P. 721-757.

233. Toscano L. Numeri di Stirling generalizzati e operatori permutabili secondo ordine // Mathematiche. 1969. - Vol. 24. - P. 492-518.

234. Toscano L. Some results for generalized Bernoulli, Euler, Stirling numbers // Fibonacci Quart. 1978. - Vol. 16, № 2. - P. 103-112.

235. Touchard J. Sur les cycles des substitutions // Acta Math. 1939. -Vol. 70, № 3-4. - P. 243-297.

236. Udrea G. A note on the sequence (Wn)n>o of A.F.Horadam // Port. Math. 1975. - Vol. 53, № 2. - P. 143-155.

237. Vasudevan R., Vittal P.R., Parthasarathy K.V. Combinants, Bell polynomials and applications //J. Phys. A: Math, and Gen. 1984. - Vol. 17, № 5. - P. 989-1002.

238. Voinov V., Nikulin M. Binomial functions with the Stirling property // Rev. Roum. Math. Pures Appl. 1995. - Vol. 40, № 2. - P. 107147.

239. Wagner C.G. Generalized Stirling and Lah numbers // Discrete Math. 1996. - Vol. 160, № 1-3. - P. 199-218.

240. Ward M. A calculus of sequences // Amer. J. Math. 1936. - Vol. 58, № 2. - P. 255-266.

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

242. Zeng J. Sur quelques propriétés de symétrie des nombres de Genocci // Discrete Math. 1996. - Vol. 153, № 1-3. - P. 319-333.