Содержание к диссертации
Введение
1 Обобщенные пирамиды Паскаля 29
1.1 Треугольник Паскаля и его обобщения 29
1.1.1 Биномиальные коэффициенты и треугольник Паскаля 29
1.1.2 Другие арифметические треугольники 34
1.1.3 Обобщенный треугольник Паскаля 38
1.1.4 Частные случаи 38
1.1.5 Перечислительные интерпретации 43
1.2 Пирамида Паскаля и ее обобщения 47
1.2.1 Триномиальные коэффициенты и пирамида Паскаля 47
1.2.2 Обобщенная пирамида Паскаля 49
1.2.3 Частные случаи 50
1.2.4 Перечислительные интерпретации 55
2 А- и В-пирамиды 58
2.1 А- и В-треугольники 58
2.1.1 Обобщенные числа Стирлинга 58
2.1.2 Производящие функции 59
2.1.3 Обобщенные числа Фибоначчи 61
2.1.4 Частные случаи 64
2.1.5 Перечислительные интерпретации 67
2.2 А- и В-пирамиды 68
2.2.1 Обобщенные триномиальные коэффициенты 68
2.2.2 Производящие функции
2.2.3 Рекуррентные соотношения 73
2.2.4 Перечислительные интерпретации 78
2.3 Обобщенные числа Трибоначчи 79
2.3.1 Построение 79
2.3.2 Рекуррентные соотношения 80
2.3.3 Частные случаи 82
2.4 Взаимные преобразования комбинаторных чисел 84
2.4.1 Обобщенные числа Стирлинга и Фибоначчи 84
2.4.2 Обобщенные триномиальные коэффициенты и обобщенные числа Трибоначчи 88
3 Комбинаторные полиномы разбиений 91
3.1 Однородные полиномы Белла и Платонова 91
3.1.1 Введение 92
3.1.2 Рекуррентные соотношения 95
3.1.3 Частные случаи 100
3.1.4 Связь с симметрическими функциями 104
3.1.5 Интерпретации 106
3.2 Полиномы Тушара и Р-полиномы 113
3.2.1 Введение 114
3.2.2 Рекуррентные соотношения 116
3.2.3 Частные случаи 131
3.2.4 Интерпретации 135
3.3 Обобщенные А- и В-полиномы 139
3.3.1 Введение 140
3.3.2 Рекуррентные соотношения 141
3.3.3 Частные случаи 147
3.3.4 Перечислительные интерпретации 154
3.4 Взаимные преобразования полиномов 155
3.4.1 Однородные полиномы Белла и Платонова 156
3.4.2 Полиномы Платонова и обобщенные В-полиномы 158
3.4.3 Т-полиномы Тушара и Р-полиномы 160
4 Приложения 163
4.1 Пути на решетках 164
4.1.1 Введение 164
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
Литература
- Обобщенный треугольник Паскаля
- Обобщенные числа Фибоначчи
- Взаимные преобразования полиномов
- Случайные блуждания на плоскости
Обобщенный треугольник Паскаля
Задачи алгоритмического характера на дискретных конечных математических структурах встречаются на практике постоянно [20, 75, 83]. Можно выделить два класса прикладных задач: создание алгоритмов и программ с преобладанием вычислений комбинаторного характера и алгоритмов, осуществляющих конструктивное перечисление комбинаторных объектов заданного класса. В последнем случае используется либо исчерпывающий последовательный перебор, либо его некоторые модификации, позволяющие ограничить объем перебора. Предлагаемый автором в работах [30, 32, 35] метод состоит в нахождении и использовании изоморфного преобразования элементов известного множества комбинаторных объектов в элементы искомого множества.
В параграфе находятся соответствия и строятся алгоритмы взаимных преобразований обобщенных чисел Стирлинга А и 5 и обобщенных триномиальных коэффициентов A j и B h соответственно.
Пусть даны множества ап = {ао, «і,..., ап-і} и Nn = {0,1,..., п — 1}. Обозначим Ва(п, к) — множество всех -сочетаний без повторений из ап, Аа(п,к) — множество всех -сочетаний с повторениями элементов из ап. Множества/5Й, 7п, Вр(п,к), В7(п}к), Ар(п,к) и А7(п,к) определим аналогично. Через \Х\ обозначим число элементов множества X. Считаем для определенности, что Z?a(n,0) = Аа(гг,0) = 1, п 0, \Ва(п,к)\ = \Аа(п,к)\ = 0, если тт(п,к,1,п — к — I) 0.
На основании теоремы 2.5 построены алгоритм 2.1 преобразования і в 5f и алгоритм 2.2 преобразования Sf в Af, которые, на основании следствия 2.6, могут служить алгоритмами преобразования Т і{п) в Т\{п) и ему обратным. Пусть Тп — множество всех векторов t = (tQ,ti,..., n-i)? У которых & из п координат в совокупности являются элементом множества Аа(п, к), I — множества А@(п,1), жп—к—1 —множества А7(п, п — к — I). Если t Г„, тогда 1р = {j : tj Є &}, /т = {j : / Є 7n}-
Введем преобразования, действующие на множестве Тп. Пусть: ujjs7 и шр7 — преобразования, аналогичные преобразованиям иа и Соа соответственно, но действующие (не различая их) на элементах Д,- и 7?: одновременно без учета расположения аг-; та — преобразование, меняющее номера всех аг- на составляющие в совокупности множество Nn — Ip — 1-у. fa — преобразование, меняющее номера всех с на составляющие в совокупности множество щ. Теорема 2.6. Пусть В { и A i построены из элементов множеств ай, /Зп и 7п, тогда: x(Anktl) = Bnk h xWJ = Ankjh n 1, 0 к n, 0 / n - k, где x = ra о up7, x = fa йру Следствие 2.7. В условиях теоремы 2.6 справедливы соотношения: х№(п)) = Ti(n), x(Ti(n)) = Г2(п), п 1. На основании теоремы 2.6 построены алгоритм 2.3 преобразования A%i в В%! и алгоритм 2.4 преобразования В в А j, которые, на основании следствия 2.7, могут служить алгоритмами преобразования ТЦп) в Т\(п) и ему обратным. Показано, что данные алгоритмы могут быть использованы при решении некоторых задач теории кодирования [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].
Нами изучаются некоторые из таких полиномов: однородные полиномы Белла An k(x) и сопряженые с ними полиномы Платонова Вп (х), обобщающие их полиномы Ак\х) и Вк (х), а также полиномы Туша-ра Сп {х,у) и Тп (х,у) и вводятся новые, сопряженные с последними, так называемые Р-полиномы Рп,к{х,у).
Построены соответствия и получены алгоритмы взаимных преобразований однородных полиномов Белла и Платонова, полиномов Платонова и обобщенных В-полиномов, а также полиномов Тушара и Р-полиномов.
Показано, что все отмеченные полиномы (при соответствующем выборе весовых коэффициентов) могут быть представлены как элементы частных случаев обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля.
Обобщенные числа Фибоначчи
Дадим перечислительные интерпретации обобщенных чисел Стирлин-га второго рода А% и первого рода В%. — сумма весов множества всех размещений п различимых объектов по двум различным ячейкам, при которых к объектов попадают в ячейку 1 при условии, что вес очередного г -го объекта в зависимости от ячейки, в которую он попадает, равен а \ = 1 или 7?-i соответственно, а вес всего размещения равен произведению весов составляющих его объектов.
Апк — сумма весов множества всех размещений п различимых объектов по двум различным ячейкам, при которых к объектов попадают в ячейку 1 при условии, что вес очередного объекта в зависимости от ячейки, в которую он попадает, равен aj = 1 или jj соответственно, где j — число объектов, уже имеющихся в ячейке 1, а вес всего размещения равен произведению весов составляющих его объектов.
Другие перечислительные интерпретации обобщенных чисел Стир-линга второго А% и первого рода В а также соответствующих обобщенных чисел Фибоначчи {п) и Т\{п) будут даны в гл. 4. Приведем перечислительные интерпретации чисел Уитни [110]: Wn,jfe — число элементов ранга к конечной геометрической решетки L размерности п. Wm{n,k) - число элементов ранга к решетки Даулинга размерности п. Пусть а {аг }о, Р {A}OJ 7 {7г }о — базовые последовательности. Полагаем, что их члены принимают значения из некоторого числового поля. Приведем конструктивное описание обобщенных триномиальных коэффициентов, построенных из членов баз (см. [22]). Вії — сумма всех различных произведений по п сомножителей, которые без повторений их индексов в каждом произведении выбираются по к из п первых членов базы а, по / из п первых членов базы (3 и по п — к — / из п первых членов базы у. Л1 { — сумма всех различных произведений по п сомножителей, которые выбираются, допуская многократные повторения, по / из к + 1 первых членов базы /3 и по п — к — I ш к + 1 первых членов базы у, причем каждое произведение входит в сумму с коэффициентом п «,-п ( " Uv , j=0 г=0 \ si ) где Si и ti — показатели кратности соответственно р\- и 7г в данном произведении. Дополнительно полагаем, что Б$0 = AQ0 = 1; В х = Щ/ = 0, если min(n,k,l,n — к — I) 0. Непосредственно из приведенных описаний могут быть получены рекуррентные формулы (1.58) и (1.59).
Получим производящие функции для некоторых частей пирамид, составленных из чисел All и Щь построенных на базах а,Р и у. оо Обозначим Aki(z) = Аф;а,Р,у) = Е ,/Л М п=к+1 Лемма 2.8. Производящая функция Akj(z) элементов (к,1)-столбца А-пирамиды удовлетворяет рекуррентному соотношению: Аф) = 2(1 - jkzy ak-iAk-ijjz) + PkAy- z)). (2.30)
Сопоставление первого и последнего звеньев полученной цепочки равенств дает соотношение (2.30). Лемма доказана. Лемма 2.9. Производящая функция элементов (к, I)-столбца А-пирамиды имеет вид Аф) = zk+lU jAkk+l П(1 az)-\ (2.31) j=0 г =0 где Ак построены на базе {Д-(1 — 7г )-1} о Доказательство. Доказательство проводим индукцией по к и /. Для пар значений к = 0, 1 = 0; к = 1, I = 0; к = 0, /=1и& = 1,/ = 1 соотношение (2.31) справедливо, поскольку, с учетом (2.30), имеем Aofi(z) = (1 - j0z)-\ Aifi(z) = za0(l - joz) \l - jiz) \ Ay.( ) = zp0(l- y0z) 2, Аід(г) = 2a0(A,(l - 7o )_1 + A(l - 7i )_1)(l - loz) \l - 7i )_1. Пусть равенство (2.31) выполняется для пар значений к = t, I = s — їй & = t— 1, / — 5, тогда с учетом соотношений (2.30) и (при щ = 1, / = 0) (1.59) получаем Аф) = z(l - jtz)-\at-iAt-i}8(z) + PtAtf8-i(z)) = = (i - 7І ГVi -1 п мі+г1 па - 7 )-х+ j=0 г=0 + (і -ltz)-lh i+a-1 П Ml+S_1 П(і - ъ Г1 = j=0 г=0 = +в її «І П(і - T -Wr1 + А(і - т.- )-1 -1) і=0 г =0 = +вП«іП(і-7 Г1 +в, і=о і=0 что дает соотношение (2.31) при к = t,l = s. Лемма доказана. п п—к Обозначим Вп{х,у) = Вп{х,у;а,/3 ) = Е Е Щ,йку\ п \. к=о 1=0 Лемма 2.10. Производящая функция В {х у) элементов п-слоя В пирамиды удовлетворяет следующему рекуррентному соотношению: Вп{х,у) = (an_i 4- Рп-іу + jn-i)B1{zT(x,y). (2.32) Доказательство. При фиксированном натуральном п с учетом соотношения (1.58) имеем Вп( ,У) = tE Bt y1 = k=0 1=0 = Е Е п-іВЩ + Pn-iBfjU + ln-iBtf)xkyl = k=0 1=0 n n—k = a„_i E E Bnkzlxk-lyl+ k=0 1=0 n n—k n n—k +Pn-iy E E BJ7V2/-1 + 7»-i E E y V = k=0 1=1 k=0 1=0 = n-1xj:nj:lBnkjixkyi+ k=0 1=0 n—ln—k—I n—\n—k—I +A -iy E BfyW + ыЕ ?,7W = k=0 1=0 k=0 1=0 = (а„_іж + /3„_i2/ + 7ra_i)5 r(x, /). Сопоставление первого и последнего звеньев полученной цепочки равенств дает соотношение (2.32). Лемма доказана. Теорема 2.2. Справедливы следующие утверждения: 1. Производящая функция элементов, составляющих правый к-сегмент А-пирамиды, имеет вид оо к—1 к Ak(y, z) = Y, Аф)у1 = гкЦ aj П(1 - fryz - иг) 1. (2.33) /=0 І=0 г=0 2. Производящая функция элементов, образующих п-слой В-пирамиды, имеет вид Y) 1 Ті ТІ ІС Вп(х, y)=U fax + ріУ + 7,0 = Е BnKlxky\ п 1. (2.34) г=0 k=0 /=0 Доказательство. 1. С учетом соотношения (2.31) имеем оо оо k—l к Ak(y,z) = Т,Аф)у1 = Е +/ П M +z П(і -lizYW = 1=0 1=0 j=0 г=0 k—l к оо = П«іП(і-7 Г1Е +/М/ І=0 г=0 /=0
Из последнего соотношения после несложных преобразований с использованием равенства (2.5) получаем формулу (2.33).
Применив п раз формулу (2.32), можно непосредственно убедиться в справедливости соотношения (2.34). Теорема доказана.
Непосредственно из соотношения (2.33) следует, что производящая функция элементов А-пирамиды имеет вид: А(х, г/, z) = Ак_{у, z)xk = Е (xz)k П «; П (1 - Pw - 7І )_1- (2.35) k=0 k=0 j=0 i=0 Аналогично из соотношения (2.33) для производящей функции элементов Б-пирамиды имеем: оо оо п—1 B(x,y?z) = 1 + Е Bn{x,y)zn = 1 + Е zn П (otiX+Ріу - 7,0 (2-36) n=l п=1 г=0 Установим соотношения между суммами чисел В%(ИА!,Й числами В1 и Afr. Обозначим п—к В {У) = Евы, о к 1=0 п. Лемма 2.11. Производящая функция В [у) элементов (п,к)-диагонали В-пирамиды удовлетворяет рекуррентному соотношению: В {У) = (Pn-iy + K-i)B (y) + an-iBtzit=i(y)- (2.37) Доказательство. С учетом соотношения (1.58) имеем в (у) = ву = Е п-іВЩ + (Зп-iB jl, + in-iB l)yl = 1=0 1=0 rv i __ ft 77 K = «n-i E я#У + /?„_i E ,7ii2/z + 7n-i E BjjУ = 1=0 /=1 /=o n—k n-k—l n—k—1 = atn-i Y, Bltlyl + pn-iy E B7V + 7n-i E Bjf7V = /=o /+1=1 /=o = а„-іЯ; гг(г/) + (3n-iyB k(y) + Тп-і ї (у). Сопоставление первого и последнего звеньев полученои цепочки равенств дает соотношение (2.37). Лемма доказана. Лемма 2.12. Производящая функция элементов (п,к)-диагонали В-пирамиды имеет вид: В (У) = ВІП а,-, (2.38) =о где В% построены на базе {(fay + 7г)агг1} о Доказательство. Разделив обе части соотношения (2.37) на П"=о &І, получим тг—1 п— 1 п—1 в (у) П «Г1 = (A.-i2/ + 7»-i)3i=ute) П «Г1 + %гцг=тЫ П «Г1 г=0 г =0 г=0 Обозначив B j(y) Ц{=о otj1 = W, имеем Щ = Щ-1 + №-i2/ + Tn-iKiiWT"1 Сравнив последнее равенство с формулой (1.38) убеждаемся, что Wk — Б, где В% строятся на базе {(fay + 7г)»гг1} о- Лемма доказана.
Взаимные преобразования полиномов
Рассматривается ряд полиномов от нескольких переменных, определяемых с помощью сумм по различным разбиениям значений их индексов: полиномы Белла Yn(f;xi,... ,жп), однородные полиномы Белла Ank(x) и сопряженные с ними полиномы Платонова Bnk(x), обобщающие их полиномы A l (х) и В , (х), а также полиномы Тушара Cnjk{x,y) и Тпк{х,у) и вводятся новые, сопряженные с последними, так называемые Р-полиномы Рпк{х, у).
Построены соответствия и получены алгоритмы взаимных преобразований однородных полиномов Белла и Платонова, полиномов Платонова и обобщенных В-полиномов, а также полиномов Тушара и Р-полиномов.
Показано, что все отмеченные полиномы (при соответствующем выборе весовых коэффициентов) могут быть представлены как элементы частных случаев обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля.
В данном параграфе приводятся новые рекуррентные формулы для полиномов Белла и Платонова. Как следствия получены соотношения для чисел Стирлинга, Лаха, Шредера, элементарных и полных симметрических функций. Обсуждаются новые и частично известные перечислительные интерпретации (перечисление с весами) этих комбинаторных объектов. Полученные формулы позволяют по т-й строке нижней тре угольной матрицы, составленной из (каких-либо одних) рассматриваемых комбинаторных чисел или полиномов, восстановить ее (т — 1)-ю строку, а следовательно, и все начальные строки.
Однородные полиномы Белла Ап к(х) имеют вид п-к+1 Ап,к(х) = п! П х?[пЩгТ\ Щк 1,к п, (3.1) п,к i—\ где х = (#i, Х2,. .) — формальные переменные, а суммирование ведется по всем таким наборам (гі,Г2,... , rn_&+i) неотрицательных чисел, что П + 2г2 + ... + (п - к + l)rn_fc+i = п, гі + г2 + ... + гп_к+1 = &, то есть (см. [76, с. 48]) по всем разбиениям натурального п на к натуральных слагаемых. Определим функции (см. [71, с. 37]) Вщк(х) = (-1)га- № - 1)\х\п ку1 (-l)rin!(2n - к - п - 1)! 2и—2fc,n—& n-ife+1 х П х?[г{Щг ]-\ n 2, 1 fc n - 1, (3.2) г=1 где суммирование ведется по всем разбиениям натурального числа 2п— 2к на п—к натуральных слагаемых. Дополнительно полагаем ВПгП(х) — хїп,п 1. Переменные Х{, і 1, участвующие в построении АП)к(х) и Вп {х), в частности, могут считаться совпадающими с последовательными производными некоторой функции. Пусть g{t) = E i V2- Если существует функция д(и) = E i (циг/г\ такая, что g(g(t)) = t, то для д = (gh g2,...)ng = (gufa,...) (см. [71, с. 74]) имеет место соотношение Вп,к{д) - ЛП)к{д), п, к 1, к п. (3.3)
Ниже, если нет сомнения в том, по какой последовательности переменных (х\,Х2,...) построены АП)к(х) и ВП)к(х), будем иногда для краткости писать Ап к и Bn k соответственно. Учитывая тождество (3.3), функции, определяемые соотношением (3.2), будем называть полиномами Платонова, хотя по переменной х\ они полиномами не являются. Дополнительно полагаем AQ = BQ — $o,k, где 5п к — символ Кроне-кера, AUjk = BUjk = 0, если к {О,1, , п}. Известны экспоненциальные производящие функции полиномов Ащк(д)\ с Е An,k(g)tn/n\ = [д(і)Г/к\, (3.4) 00 со Е Е АПік(д)хкЄ/п\ = e W (3.5) к=0 п=к см. [77, с. 179] и [78, с. 57]). Из формул (3.4) и (3.5) с учетом тождества (3.3) могут быть получены экспоненциальные производящие функции полиномов ВПук(д): ВПгк(д)ип/п\ = [g(t)]k/k], (3.6) п—к ЕЕВп к(д)хкип/п\ = е іМ. (3.7) к=0 п=к (см. [71, с. 75], [81]). Рассмотрим сложную функцию F(t) = f\g(t)]. Пусть d d d где и — g(t). В области, где все участвующие производные существуют, выполняются соотношения, носящие название формулы Бруно: п Fn = n\Y: fkY,g?[rmrr\ п і. (3.8) k=l п,к
Правые части этих выражений, рассматриваемые как функции абстрактных переменных Д, 7г, 1 &, г тг, известны под названием полиномы Белла [109]. Отметим, что в обозначениях Белла Fn =
Если считать, что параметры gj, і 1, участвовавшие в построении однородных полиномов Белла (3.1), совпадают с употребляемыми сейчас производными аналитической функции, имеющими те же обозначения gi = g{t), то формула Бруно (3.8) может быть записана в следующем виде: п Fn = Y„(f;gu...,gn) = An:k{g(t)]fk, п 1, k = l (3.9) где Ащк[д(і)] = Ащк(д). Аналогично Вщк[/{и)] = Bn (f). Отметим, что АП)к(д) является коэффициентом при fk в п—ом полиноме Белла Yn(f;g\,...,gn) В книгах [76, 77] описаны обращения формулы Бруно при помощи символического исчисления. В [70, 71] эти обращения реализуются другим путем. В частности, доказаны следующие два утверждения. Утверждение 3.1 [70]. Разрешение формулы Бруно относительно производных функции g(t) имеет вид gn=J2 An,k[F{t)]Bk,i[f(v)l п 1. k=l (3.10) Заметим, что формула (3.10) может быть получена из очевидного равенства g(t) = f[F(t)] и соотношений (3.9) и (3.3). Утверждение 3.2 [70]. Разрешение формулы Бруно относительно производных функции f(u) имеет вид Л = Bnjk[g(t)}Fk, п 1. k=l (3.11 Пусть ge(t) = E Lo n — экспоненциальная производящая функция последовательности {gn} =0. Известна следующая Лемма 3.1 [133]. Пусть а — вещественное число и (cv)m = а(а — 1) (а — т + 1). Тогда при до ф Ы )Г = as + п=\ (а)тд%-тАп т(д) т=1 п\ Как отмечено в [28] в случае обычной производящей функции g0{t) = Т =$дпїп указанная в лемме 3.1 формула будет иметь вид со [доЖ = д%+Т п=1 E[nV(a)mgrmAn,m( g) т=1 і (3.12) где gi = ilgi. При #о — 1 равенство, эквивалентное соотношению (3.12), имеется в [77, с. 186].
Случайные блуждания на плоскости
Перейдем к обсуждению некоторых интерпретаций изучаемых комбинаторных объектов. Для Т-полиномов Тушара известна следующая перечислительная интерпретация [248]: Тп к(х\,...; ї/i,...) — число перестановок п элементов, скажем щ,..., ип, в которых точно к циклов обладают свойством Л, а все остальные — свойством В, где Xj, j = 1,..., п, есть число циклических перестановок с циклом длины j, которые обладают свойством Л, а yj, j = 1,..., п, есть число циклических перестановок с циклом длины j, которые обладают свойством В, при условии, что каждый цикл длины j определяет
Пусть свойство Л задано как следующее: элементы щг,..., щ. цикла длины j, j = 1,..., п появляются так, что %\ %2 . ij, а свойство В: элементы мг1,..., щ. цикла длины j, j = 1,... , п, появляются на любых местах, исключая те, что со свойством Л. Тогда Xj = 1, j = 1,...,п и г/j = (j — 1)! — 1, j = 1,... ,n, и число перестановок из п элементов, в которых точно к циклов, обладающих свойством Л, задается как rn 4(l,l,...;0,0,l,...,(j-l)!-l,...) = п п—к—г (Ь __ 7 \ = S».- Е НУ 7J №- , +я, г =0 j =0 \ К I где 5(п, /г) — числа Стирлинга второго рода. Дадим новую перечислительную интерпретацию Т-полиномов.
Рассматриваем все разбиения n-множества J\f на непустые блоки, среди которых к блоков обладают свойством Л, а остальные — свойством В. Вес блока, состоящего из j элементов, обладающих свойством Л, считаем равным Xj, свойством В — yj, а вес всего разбиения полагаем равным произведению весов его блоков. Тогда: ТП)к(х, у) — сумма весов всех разбиений J\f на непустые блоки, среди которых к блоков обладают свойством Л, а остальные — свойством В.
Из приведенных интерпретаций при yj = 0 следуют известные интерпретации частичных полиномов Белла Ап {х). Дадим новую интерпретацию полиномов Т к(х,у): T k(x,y) — сумма весов всех подстановок степени п, где к циклов обладают свойством Л, а все остальные — свойством В, при условии, что вес цикла длины j, который обладает свойством Л, равен x j = (j — 1)\XJ, свойством В — у) = {І — 1)!г/j, а вес подстановки — произведению весов составляющих ее циклов. Из полученной интерпретации при у! = 0 имеем перечислительную интерпретацию полиномов Сп(х) (см. [76, с. 86]), а при x j = 1 и y j = О — интерпретацию чисел Стирлинга первого рода s(n,k).
Из выражения (3.85) видим, что коэффициент tn!k(r,s) равен числу таких п-подстановок, состоящих из упорядоченных циклов, в которых точно к циклов обладают свойством Л, а все остальные — свойством В, где rj, 1 j п есть число циклических перестановок с циклом длины j, которые обладают свойством Л, a Sj, 1 j п есть число циклических перестановок с циклом длины j, которые обладают свойством В, при условии, что каждый цикл длины j определяет одно из
Как видно из (3.86), коэффициентрП]&(г, s) равен взятому с множителем (—1)Гігі!(2п — к — г\ — l)fc_ri_i(A; — 1)" числу тг-подстановок, состоящих из упорядоченных циклов, в которых точно к циклов обладают свойством Л, а все остальные — свойством В, где rj, 1 j п есть число циклических перестановок с циклом длины j, которые обладают свойством Л, a Sj, 1 п есть число циклических перестановок с циклом длины j, которые обладают свойством В, при условии, что
Как видно из выражения (3.87), коэффициент cn k(r,s) равен числу п-подстановок, в которых точно к циклов обладают свойством Л, а все остальные — свойством В, где rj, 1 j п есть число циклических перестановок с циклом длины j, которые обладают свойством Л, а sji 1 j 5; п есть число циклических перестановок с циклом длины j, которые обладают свойством Б, при условии, что каждый цикл длины
Определяет ОДНО ИЗ ЧИСеЛ rj ИЛИ Sj.
Для нецентральных чисел Стирлинга второго рода Sa(n, к) известна следующая перечислительная интерпретация [192]: Sa(n,k) — число способов размещения п различных частиц по к непомеченным и а помеченным ячейкам таким образом, что ни одна из к ячеек не пуста.
Рассмотрим одноканальную систему массового обслуживания с ожиданием (например, [74, с. 23], [7, с. 247]). Пусть to = 0, t\, 2,... — 137 моменты поступлений требований и v\, г 2,... — времена их обслуживания. Тогда ип = tn — tn i (п 1) представляют собой интервалы между поступлениями требований в систему. Положим Xk = Vk-i—Uk (к 1) и 5о = 0, Sn = Xi+X2 + .. .+Хп (п 1). Будем считать, что Xk (к 1) — взаимно независимые одинаково распределенные случайные величины и F(x) = Р{ХІ х} (—оо х +оо, 1 г п). Последовательность { т п 0} представляет собой случайное блуждание, соответствующее функции распределения F(x). Для него определим две последовательности случайных величин {Nk, к 0} и {Щ, к 0} по правилу: N0 = 0, N1 = min{n 0 : Sn 0}, Nk = min{n Nk-г : Sn SNk J (k 2); N0 = 0, N\ = min{n : Sn 0}, Nk = minjn : Sn SNk-i} (k 2). Случайная величина Nk называется k-м верхним лестничным моментом, a SNk — соответственно k-й лестничной высотой. Аналогично Nk и Sfi — нижние к-е лестничные момент и высота. Пары случайных величин (Nk,SNk) и (Nk,Sfik) назовем соответственно к-й верхней и к-й нижней лестничными точками случайного блуждания Sn. Для удобства положим N1 = N, N\ = N. Совместное распределение первой верхней лестничной точки (N, 5TV) МОЖНО записать в виде
