Диссертация (1149645), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Ким [95].k2b***********d...dа)...bbdб)b*****d...b...dbdadв)Рисунок 1.9 – Неприводимые первые блоки замощений (при m ≥ 2, n = 2)а) длины k; б) длины k + ms (s ≥ 1); в) длины k + ms + 1 (s ≥ 0)Задача перечисления замощений прямоугольника плитками тесно связана сзадачейперечисленияупорядоченныхразбиенийкомпонентвекторанаслагаемые. Эта связь указана в работе Р.

Стенли [80, с. 367]. Разбиениемназывается набор целых положительных чисел (при данной их сумме), в которомпорядокчиселнепринимаетсяврасчет[69, с. 129].КакотмечаетДж. Риордан [69], понятие разбиения введено Г. Лейбницем в 1669 г., адействительное развитие понятия разбиения начинается с трудов Л. Эйлера[86, с. 234-250]. В работах О.В. Кузьмина [29], О.В. Кузьмина и А.А. Балагура [5],О.В. Кузьмина и О.В. Леоновой ([30], [31]) разбиения применяются дляинтерпретации комбинаторных чисел и полиномов.

Упорядоченные разбиения вряде работ ([69, с. 129], [87, с. 67], [13, с. 59]) названы композициями. Понятие26композиции принадлежит П. Мак-Магону (1915). Композициями называютсяупорядоченные наборы целых положительных чисел [69, с. 129]. Развитию теориичастично упорядоченных множеств посвящены также работы В.А.

Баранского иТ.А. Королевой [6], А.М. Вершика и Ю.В. Якубловича [10], А.А. Старовойта [79].ВработахЛ.М. Коганова([24], [25])исследуютсяупорядоченныепарыупорядоченных разбиений.Таким образом, задачи перечисления замощений прямоугольника плиткамии перечисления упорядоченных разбиений компонент вектора на целыеположительные слагаемые, сводящиеся к вычислению произведения Адамараxk1,m1  ax  bx 1  cx  dx nдо недавнего времени были решены лишь в частных случаях при m ≥ 2 и n = 2.Серии в случайных последовательностях неизменно привлекают вниманиеисследователей ([2], [11], [19], [20], [26], [27], [72] – [77]).Рассмотрим последовательность случайных величин {I n }n1 , определенныхна одном вероятностном пространстве  , , P  .О п р е д е л е н и е 1.1.

Последовательность {I n }n1 называется стационарнойпоследовательностью 1-зависимых случайных индикаторов, если1) каждая из случайных величин I n принимает только два значения: 0 и 1;2) вероятностьa1, a2 ,P  I1t  a1, I 2t  a2 ,..., I k t  ak прилюбыхk,, ak {0,1} не зависит от t;3) случайные векторы I1, I 2 ,, Ii1  и Ii1, Ii2 ,, I k  независимы прилюбых k  2 , 1  i  k .Приведем примеры последовательностей 1-зависимых индикаторов.П р и м е р 1.1.Простейшимпримеромявляетсяпоследовательностьнезависимых случайных величин, распределенных по закону Бернулли ипринимающих только два значения 0 и 1.27П р и м е р 1.2.

Пусть { X n }n1 – последовательность независимых одинаковораспределенных случайных величин и f :2 0,1 – измеримая функция.Построим новую последовательность {I n }n1 следующим образом: для любогоnположим I n  f  X n , X n1  . Тогда {I n }n1 – последовательность 1-зависимыхслучайных индикаторов. Об этой последовательности говорят, что она имеет2-блочную структуру.П р и м е р 1.3. В условиях примера 1.2 положим0 при X  Y ,f  X ,Y   1 при X  Y .При этом будем говорить, что пара (X, Y) образует убывание, если X  Y , иобразует возрастание, если X  Y .

Таким образом, {I n }n1 – последовательность1-зависимых случайных индикаторов возрастаний в последовательности { X n }n1 .П р и м е р 1.4.Приведемпримерпоследовательности1-зависимыхслучайных индикаторов, которая не имеет 2-блочной структуры. Пример такойпоследовательности имеется в статье [14]. При    положим 1 1 0 0 1 011x   0  , y     , A1    0 1 , A0   0 0 1  . 0 0 0 0 00  Определим распределение последовательности случайных индикаторов {I n }n1следующимP  I1  a1, I 2  a2 ,образом:длялюбых, I k  ak   Aa1 Aa2 ... Aak y  x ,a1, a2 ,гдеточка, ak {0,1}означаетположимскалярноепроизведение в пространстве столбцов размерности три.

Нетрудно проверить, что{I n }n1 – последовательность 1-зависимых случайных индикаторов и для этойпоследовательности28P  I1  0, I 2  0,Пусть0,1 при k  1,, I k  0    при k  2,0 при k  3.– полугруппа всех слов над алфавитомконкатенации слов. Функция A : 0,1 A a1a20,1с операциейопределяется равенствамиak   P  I1  a1, I 2  a2 , , I k  ak  , A  e   1,где е – пустое слово. Далее будем обозначать w длину слова w 0,1 , а s  w –число единиц в нем.Рассмотримформальныепроизводящиефункцииотмножества не коммутирующих между собой переменных y0 , y1, y2 ,ay a0  y  где y   y0 , y1, y2 , , y w  yi yi12 A  w ywбесконечного:,(1.8)w0,1  1s ww0,1 yA 0ww,(1.9)yik при w  0i110i21 10ik , y e  y0 .Т е о р е м а 1.1.

Для производящих функций a  y  и a0  y  справедливоследующее равенство:a  y   a  y  a0  y   a 0  y  .Из теоремы 1.1 вытекает, что распределение последовательности {I n }n1полностью определяется последовательностью значений { A  0n }n1 . Функциюa0  x    A  0n  x nn 0назовем порождающей производящей функцией последовательности случайныхиндикаторов.Для вычисления a0  y  можно использовать произведение Адамара.29Т е о р е м а 1.2.

Справедливо равенствоt i yi  .a0 (y )   a0 (t )  i 0 i1  t  t yi i 0 t 1Теоремы 1.1 и 1.2 доказаны М.И. Толовиковым в [68].Рассмотрим некоторые примеры нахождения производящих функцийраспределения некоторых статистик от серий нулей в последовательности I1, I 2 ,, In  .П р и м е р 1.5. Пусть {I n }n1 – последовательность случайных индикаторов,P  I n  1  p ,распределенных по закону Бернулли,P  I n  0   q . Найдемпроизводящую функцию a  y  при подстановке yi  xi 1 y i ( i  0, 1, ...

).Для любого слова w 0,1 справедливо равенствоA  w  p   qs ww  s  w.Определим порождающую функцию a0  x  для последовательности {I n }n1 :n 0n 0a0  x    A  0n  x n   q n x n Выполняя подстановкуyi  xi 1 y i1.1  qx( i  0, 1, ... ) в выражение, определяющеефункцию a0  y  , получаемna0  y   x  1n 0 m 0nmCnm A  0n  x n y m ,где m – число нулей в последовательности  I1, I 2 , , I n  , Сnm – число сочетаний изn по m.Легко видеть, что30a0  y   x a0  x  y  1  x1  qx  y  1.(1.10)Выполним проверку равенства (1.10), воспользовавшись теоремой 1.2.xi i ixtxy 1 11  txy i 0a0 (y )   tx1qt 1  qt 1  t t i xi 1 y i 11txy t 1i 0 t 1  1x .1qt1txy1 t 1Воспользовавшись свойством1 g  t   g  t 1  t(1.11)произведения Адамара, находимa0  y  xx.1  qtx  y  1 t 1 1  qx  y  1Таким образом, получен результат, совпадающий с формулой (1.10).Производящая функция a  y  при подстановке yi  xi 1 y i ( i  0, 1, ...

) вравенство, ее определяющее, принимает вид:na  y   x An,m x n y m ,n 0 m 0где An,m  P  I1  I 2  I n  n  m  – вероятность того, что число нулей впоследовательности  I1, I 2 , , I n  равно m.Подставляя формулу (1.10) в равенство теоремы 1.1, находимxay a0  y 1  qx  y  1xx.x1  a0  y  1 1  x  qy  q  1 1  x  qy  p 1  qx  y  131П р и м е р 1.6.Найдемпроизводящиеayфункциииa0  y  I1, I 2 ,, In  ,рассмотренной выше последовательности при подстановке yi xi 1 при i  0,1,yi  i 1при i  ryx, r,в равенства, их определяющие.В этом случае a  y  принимает видna  y   xn 0 m0 n k0 k1  kr k 1mгде An, m, k0 , k1 ,, kr , kAn, m, k0 , k1 ,, kr , kx n y0k0 y1k1yrkr y k ,– вероятность того, что в последовательностисодержащей m нулей, k0 серий из нулей длины 0, k1 серий длины 1, …, kr серийдлины r, k серий, длина которых превышает r.Применяя теорему 1.2, находимri ii ixtxyxytxi 1i 0i  r 1 a0 (y )  r 1  qt 1  tx t i xi y  txy t i xi  ii 0i  r 1t 1ryt r 1 x r  2i ix  t x yi  11  txi 0r 2 r 2r 1  qt 1  tx t i xi y  yt xi1  txi 0  t 1rri i2i ir 1 r  2xtxytxtxyytxii 1 1i 0i 0 rr1qt 1  qt 1  tx  tx t i xi y  t 2 x 2 t i x i y  yt r 2 x r 2 iii 0i 0 t 1xy0  tx 2 y1  t 2 x3 y2   t r x r 1 yr  tx 2 y0  t 2 x3 y1   t r 1x r 2 yr  t r 1x r 2 y  1  tx  txy0  t 2 x 2 y1   t r 1 x r 1 yr  t 2 x 2 y0  t 3 x3 y1   t r 2 x r 2 yr  t r 2 x r 2 y  t 132xy0  tx 2  y1  y0   t 2 x3  y2  y1    t r x r 1  yr  yr 1   t r 1x r 2  y  yr   1 .2 2r 1 r 1r 2 r 2 1  qt 1  tx  y0  1  t x  y1  y0    t x  yr  yr 1   t x  y  yr   t 1Применяя к последнему равенству свойство (1.11), получаемra0  y  xy0   qi xi 1  yi  yi 1   q r 1x r 2  y  yr i 1r1  qx  y0  1   q xi 1 i 1i 1 yi  yi1   qr 2 r 2x y  yr xy0  qx 2  y1  y0   q 2 x3  y2  y1    q r x r 1  yr  yr 1   q r 1x r 2  y  yr ,1  qx  y0  1  q 2 x 2  y1  y0    q r 1x r 1  yr  yr 1   q r 2 x r 2  y  yr По теореме 1.1 находимray xy0   qi xi 1  yi  yi 1   q r 1x r 2  y  yr i 1r1  x  px  y0  1  p  q xi 1i i 1 yi  yi1   pqr 1 r  2x y  yr xy0  qx 2  y1  y0   q 2 x3  y2  y1    q r x r 1  yr  yr 1   q r 1x r 2  y  yr .1  x  px  y0  1  pqx 2  y1  y0    pq r x r 1  yr  yr 1   pq r 1x r 2  y  yr При r = 1 имеемxy0  qx 2  y1  y0   q 2 x3  y  y1 ,a0  y  1  qx  y0  1  q 2 x 2  y1  y0   q3 x3  y  y1 xy0  qx 2  y1  y0   q 2 x3  y  y1 .ay 1  x  px  y0  1  pqx 2  y1  y0   pq 2 x3  y  y1 При r = 2 получаемxy0  qx 2  y1  y0   q 2 x3  y2  y1   q 3 x 4  y  y2 ,a0  y  1  qx  y0  1  q 2 x 2  y1  y0   q3 x3  y2  y1   q 4 x 4  y  y2 xy0  qx 2  y1  y0   q 2 x3  y2  y1   q 3 x 4  y  y2 .ay 1  x  px  y0  1  pqx 2  y1  y0   pq 2 x3  y2  y1   pq 3 x 4  y  y2 33П р и м е р 1.7.

Выполняя подстановку xi 1 y при i  r ,yi  при i  r0в равенства (1.8) и (1.9), для рассмотренной выше последовательности находимna  y    Anr,k x n1 y k 1 ,n 0 k 0где Anr,k – вероятность того, что в последовательности  I1, I 2 , , I n  , содержащей kединиц, длина максимальной серии из нулей не превышает r.Применяя теорему 1.2, получаемrri ixy  t x xy  q i xi 1i 0i 0 a0 (y )  rri i 1  qt 1  txy t i xi 1  qxy  q xi0i 0 t 1q r 1 x r 1  1xy  q r 1 x r 1  1qx  1q r 1 x r 1  1 qx  1  qxy  q r 1 x r 1  11  qxyqx  1xyxy  q r x r  q r 1 x r 1 1  qxy  q r x r  q r 1 x r 1  qx  1 qx  1.Отсюда по теореме 1.1 находимay xy  q r x r  q r 1 x r 1 1  pxy  q r x r  q r 1x r 1  qx  1 qx  1П р и м е р 1.8. Выполним подстановку xi 1 y0 ,yi   xi 1 y1 ,если i  четное,если i  нечетное,.34в выражения (1.8) и (1.9), определяющие функции a0  y  , a  y  .

При этомna  y   n 0 k 0 s0  s1 k 1Ans0,k,s1 x n1 y0s0 y1s1 ,где Ans0,k,s1 – вероятность того, что в последовательности  I1, I 2 , , I n  , содержащейk единиц, s0 серий из нулей четной длины и s1 серий из нулей нечетной длины.Тогда по теореме 1.2 имеем2 i 2 i 12 i 1 2 i  2txytxy01 1i 0 a0 (y )   i  01qt2i2i12i12i21  t  t x y0  t  t x y1 i 0i 0 t 1xy0tx 2 y1 12 21tx1  t 2 x22 2 1  qt 1  txy0  t x y11  t 2 x2 1  t 2 x2 1x  y0  txy1 . 2 22 2 1qt1txytxytx01 t 1 t 1Применяя к последнему равенству свойство (1.11), получаемa0  y  x  y0  qxy1 .1  qxy0  q 2 x 2 y1  q 2 x 2(1.12)Подставляя формулу (1.12) в равенство теоремы 1.1, находимay x  y0  qxy1 1  qxy0  xy0  q 2 x 2 y1  qx 2 y1  q 2 x 2П р и м е р 1.9.x  y0  qxy1 .1  pxy0  pqx 2 y1  q 2 x 2Найдемпроизводящиефункцииayиa0  y рассмотренной выше последовательности при подстановке yi  xi 1 y  i  0, 1, ... вравенства, их определяющие.

Характеристики

Список файлов диссертации