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

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

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

Получаем P  x   det PP Sm0VLn,где V – матрица размерности n×m, L n – нижняя треугольная матрица порядка n,элементы главной диагонали которой равны 1, 0 – нулевая матрица размерностиm×n, S m – матрица порядка m, получающаяся из R заменой m-й строки строкой, вкоторой m-й элемент равен единице, а все остальные элементы равны нулю.Отсюда находимP  x   det Sm  det Ln  det Sm  1n  det Sm .Применяя теорему Лапласа, раскладываем det Sm по m-й строке.

ПолучаемP  x   det Sm   1 det R m,m  det R m,m .2mТеорема 2.6 доказана.Таким образом, комбинаторным методом автором получены явныеформулыдлявычисленияпроизводящейфункциивесовзамощенийпрямоугольника плитками по числу типов взаимного расположения плиток приm = 2, n = 2 (теорема 2.4), а также при m = 2, n ≥ 2 (теорема 2.5). Объект81исследования в данном случае является новым.

С помощью методов теорииграфов указанная задача решена автором не только для частных случаев, но и вобщем виде (теорема 2.6). Применение метода трансфер-матрицы, по сравнению скомбинаторным методом, позволяет снять ограничения на длину плитки.2.6 Осциллирующее случайное блуждание в задаче перечисленияупорядоченных разбиений X k k 1 , Yk k 1 О п р е д е л е н и е 2.2. Пусть Z – случайная величина,последовательности неотрицательных случайных величин. Последовательность Z k k 0 , определенная формуламиZ0  Z ,Z k  Z k 1  sg  Z k 1 Ysg  Z0 ...sg  Zk 1   sg  Z k 1  X sg  Z0... sg  Zk 1 , k  0,(2.18)где1sg  Z   0при Z  0,при Z  0,sg  Z   1  sg  Z  ,называется осциллирующим случайным блужданием, построенным по тройке Z , X k k 1, Yk k 1 .Понятие осциллирующего случайного блуждания приведено в соответствиис источником [8, с.

246]. Там оно имеет несколько иной смысл, однако в случае,когда случайные величины в каждой из последовательностей X k k 1 , Yk k 1одинаково распределены, распределения случайного процесса Z k  k 0определения 2.2 и соответствующего случайного процесса из [8] совпадают.из82Рассмотрим  s1 ,s2 ,...,sn  1 , 2 ,..., s1 s2 ...sn – упорядоченное разбиение числа rна s1 слагаемых, равных 1, s2 слагаемых, равных 2, и т.д., sn слагаемых, равныхцеломуn  2,числуs1  2s2  ...

 nsn  r ,причемгдеr,si–целыенеотрицательные числа (i = 1, 2, …, n). Слагаемому, равному i, приписывается весdi. Под весом разбиения понимается произведение весов образующих егослагаемых. Обозначим t1 ,t2 ,...,tm  1 , 2 ,..., t1 t2 ...tmупорядоченное разбиениечисла r на t1 слагаемых, равных 1 и имеющих вес b1, t2 слагаемых, равных 2 иимеющих вес b2, и т.д., tm слагаемых с весом bm, равных целому числу m  2 ,причем t1  2t2  ...  mtm  r , где tj – целые неотрицательные числа (j = 1, 2, …, m).Разбиения вектора (r, r), представляющие собой пары определенных вышеразбиений числа r, обозначим  r   s1 ,s2 ,...,sn , t1 ,t2 ,...,tm .

Вес такого разбиенияопределим как произведение весов разбиений  s1 ,s2 ,...,sn , t1 ,t2 ,...,tm .Пусть Z0  0 . По формуле (2.18) построим осциллирующее случайноеблуждание  Z k k 0 , полагая, что элементы последовательностей X k k 1 , Yk k 1принадлежат множествам 0,1,..., n , 0,1,..., m соответственно, то есть тем жемножествам, что и элементы разбиений  s1 ,s2 ,...,sn , t1 ,t2 ,...,tm . Тогда элементыосциллирующегослучайногоблуждания Z k  k 0принадлежатмножествуm  1,  m  2,..., n  1, n .Пусть–l(k)наименьшеенатуральноечисло,такое,чтоsg  Z 0   ...  sg Zl  k 1  k . Тогда элемент k 1 упорядоченного разбиения  s1 ,s2 ,...,snназовем элементом типанн, если Zl  k   0 и Zl  k 1  0 ;нв, если Zl  k   0 и Zl  k 1  0 .83Пусть–h(k)наименьшеенатуральноечисло,такое,чтоsg  Z 0   ...  sg Z h k 1  k .

Тогда элемент k 1 упорядоченного разбиения t1 ,t2 ,...,tmназовем элементом типавн, если Zl  k   0 и Zl  k 1  0 ;вв, если Zl  k   0 и Zl  k 1  0 .Рассмотрим ориентированный граф G  V , D  с множеством вершинV  m  1,  m  2,..., n  1, nи множеством дугD   i, j  V 2 i  0, j  i или i  0, j  i .Припишем дуге  i, j  орграфа G весd j iuннd j iuнвwij  bi  j uвнb u i  j ввпри i  0, j  0;при i  0, j  0;при i  0, j  0;при i  0, j  0.Определим вес пути в орграфе G как произведение весов дуг этого пути.Последовательность  Z k k 0 элементов V является последовательностью вершиннекоторого бесконечного пути в орграфе G тогда и только тогда, когда онаявляется осциллирующим случайным блужданием.Алгоритм укладки плитками прямоугольника размером 2×r, описанный впараграфе 2.5, соответствует осциллирующему случайному блужданию дляразбиения.Пример2.23.

Разбиение11    2,4,1,4  , 1,3,4,2,1  , имеющее весb12b2b3b4d1d2d42 , содержит один элемент типа нн, три элемента типа нв, дваэлемента типа вв, три элемента типа вн. На рисунке 2.25 приведено замощениепрямоугольникаразмером2×11,соответствующееразбиению8411    2,4,1,4  , 1,3,4,2,1  , имеющее вес b12b2b3b4d1d2d42 и содержащее однуплитку типа нн, три плитки типа нв, две плитки типа вв, три плитки типа вн.Соответствующееосциллирующееслучайноеблужданиеграфическипредставлено на рисунке 2.26. Рядом с дугами конечного пути из вершины Z0 = 0в вершину Z9 = 0 в орграфе G, изображенного на рисунке 2.26, указанысоответствующие им веса.Рисунок 2.25 – Замощение прямоугольника, соответствующее разбиению11    2,4,1,4  , 1,3,4,2,1 Вычислим производящую функциюF  x, uнн , uнв , uвн , uвв  k 0i1 i2 i3 i4  ki1 i2 i3 i4 kwk ,i1 ,i2 ,i3 ,i4 uннuнвuвнuвв x ,где wk ,i1 ,i2 ,i3 ,i4 – сумма весов разбиений  r   s1 ,s2 ,...,sn , t1 ,t2 ,...,tm , состоящих из kэлементов ( k  s1  s2  ...

 sn  t1  t2  ...  tm ), в том числе i1 элементов типа нн, i2элементов типа нв, i3 элементов типа вн, i4 элементов типа вв.Задача вычисления производящей функции суммы весов разбиений сучетом типов взаимного расположения элементов в общем виде решается потеореме 2.4, сформулированной и доказанной автором.Комбинаторным методом найдем явные формулы для вычисленияпроизводящей функции суммы весов разбиений  r    s ,t , i , j  , состоящих из kэлементов ( k  s  t  i  j , s  nt  r , i  mj  r ), с учетом типов взаимногорасположения элементов.85Рисунок 2.26 – Осциллирующее случайное блуждание, построенное дляразбиения 11    2,4,1,4  , 1,3,4,2,1 Справедлива следующая теорема, сформулированная и доказанная автором.Т е о р е м а 2.7.

В принятых выше обозначениях справедливо равенство:F3,2  x, uнн , uнв , uвн , uвв   1  abduнвuвнuвв x3   1  acuнвuвн x 2   3abduвв  bc 2uнн  uнвuвн x3   a3duвв2  b2cuннuвв  b2cduнвuвн  uнвuвн x 4   b3d 2uнвuвнuвв  a 2bcduннuвв2  uнвuвн x5  .1(2.19)Д о к а з а т е л ь с т в о . Каждому разбиению  r    s ,t , i , j  соответствуетпоследовательность  Zi i 0 , такая, что k  s  t  i  j и Z0  Z k  0 .

Вершины этойkпоследовательности образуют цикл в орграфе G. Всякий цикл можноединственным образом разбить на простые циклы.Определим производящую функцию Wn,m  x    s0 ws x s , где ws – суммавесов простых циклов длины s. Тогда86Fn,m  x, uнн , uнв , uвн , uвв    Wn,m  x   ss 01.1  Wn,m  x Перечислим все разбиения, соответствующие простым циклам в орграфе Gдля случая m = 2, n = 3:1) 1   1 , 1  ;2)  3    3 , 1,1,1  ,  3    3 , 1,2   ,  3    3 ,  2,1 ;3) при s  2 3s   0,s ,  s2,s1     3,3,...,3 , 1,1,2,1,2,1,...,2,1,1  , 3s   0,s ,  s2,s1     3,3,...,3 ,  2,2,1,2,1,...,2,1,2,2   , 3s   0,s ,  s ,s     3,3,...,3 , 1,1,2,1,2,1,...,2,1,2,2   , 3s   0,s ,  s ,s     3,3,...,3 ,  2,2,1,2,1,...,2,1,1  ;4) при s  1 3s1   1,s ,  s1,s1     3,3,...,3,1 ,  2,2,1,2,1,...,2,1,2   , 3s1   1,s ,  s1,s1    1,3,3,...,3 ,  2,1,2,1,...,2,1,2,2   , 3s1   1,s ,  s1,s     3,3,...,3,1 , 1,1,2,1,2,...,1,2   , 3s1   1,s ,  s1,s    1,3,3,...,3 ,  2,1,2,1,...,2,1,1  ;5) при s  0 3s2   2,s ,  s ,s1    1,3,3,...,3,1 ,  2,1,2,1,...,2,1,2   .Производящая функция суммы весов простых циклов для случая m = 2,n = 3 имеет вид:W3,2  x   acuнвuвн x 2  2abduнвuвнuвв x3  a3duнвuвнuвв2 x 4 s 2s 2s s s 1 3 s 1s s s 1 3s 1  a s 2b s 1d suнвuвнuвв x   a s 2b s 1d suнвuвнuвв x s s s 3 s 1 2 a b d u u u x   a s 1b s 1сd suннuнвuвнuвв x s ss 2ss s s 3sнв вн ввs 187  a b сd u u u xs 1 s 1ss 1s 1 s 1 s 1 3 s 1нв вн вв a b сd u u u xs 1 sss 1s 1 s 1 s 3 s  2нв вн ввs s s 1 3 s  2  a s 1b s сd suннuнвuвнuвв xs 1s 1 s 1 s 3 s 3  a sb s 1с 2d suннuнвuвн uвв xs 02 2 3 7a 4bd 2uнвuвнuвв x acuнвuвн x  2abduнвuвнuвв x  a du u u x 1  abduнвuвнuвв x32332 4нв вн вв2 22 2 2 6b3d 2uнвuвнuвв x52a 2b2d 2uнвuвнuвв x b2cduннuнвuвнuвв x 41  abduнвuвнuвв x3 1  abduнвuвнuвв x3 1  abduнвuвнuвв x32 2 4b2cduнвuвн xa 2bcduннuнвuвнuвв2 x51  abduнвuвнuвв x3 1  abduнвuвнuвв x32 2a 2bcduнвuвнuвв x5bc 2duннuнвuвн x3.1  abduнвuвнuвв x3 1  abduнвuвнuвв x3Отсюда получаемF3,2  x, uнн , uнв , uвн , uвв  1 1  abduнвuвнuвв x3  1  W3,2  x  1  acuнвuвн x 2   3abduвв  bc 2uнн  uнвuвн x3   a3duвв2  b2cuннuвв  b2cduнвuвн  uнвuвн x 4   b3d 2uнвuвнuвв  a 2bcduннuвв2  uнвuвн x5  .1Теорема 2.7 доказана.Таким образом, комбинаторным методом с помощью осциллирующегослучайного блуждания автором получена явная формула для вычисленияпроизводящей функции весов разбиений  r    s ,t , i , j  ( s  nt  r , i  mj  r ) сучетом типов взаимного расположения элементов для случая m = 2, n = 3.88Глава 3.

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

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