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

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

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

В принятых выше обозначениях справедливо равенство:F2,2  x, uнн , uнв , uвн , uвв  1  bduнвuвн x 2.1   ac  2bd  uнвuвн x 2   a 2duвв  bc 2uнн  uнвuвн x 3   acuннuвв  bduнвuвн  bduнвuвн x 4Д о к а з а т е л ь с т в о . Определим производящую функциюWn,m  x, uнн , uнв , uвн , uвв  где ws ,i1 ,i2 ,i3 ,i4s 0i1 i2 i3 i4  si1 i2 i3 i4 sws ,i1 ,i2 ,i3 ,i4 uннuнвuвнuвв x ,– сумма весов неприводимых блоков всевозможной длины,состоящих из s плиток, из которых i1 плиток типа нн, i2 плиток типа нв, i3 плитоктипа вн, i4 плиток типа вв. Так как любое замощение единственным образомпредставляетсяввидепоследовательностинеприводимыхблоков,топроизводящая функция суммы весов замощений может быть найдена по формуле:Fn,m  x, uнн , uнв , uвн , uвв  k 0i1 i2 i3 i4  k  Wn,m  x, uнн , uнв , uвн , uвв   s 0si1 i2 i3 i4 kwk ,i1 ,i2 ,i3 ,i4 uннuнвuвнuвв x 11  Wn,m  x, uнн , uнв , uвн , uвв .71На рисунках 2.18-2.21 представлены неприводимые блоки различной длиныдляслучаяn=2m = 2,исоответствующиеимосциллирующиепоследовательности.zkнвсuнвсaz1аuвнz0внz2kРисунок 2.18 – Неприводимый блок длины 1 (m = 2, n = 2)zkнвdbвнz1duнвz0z2zkcuнвz0kz1нв ннc cbвнbuвнbuвнz3kcuннz2zkz1нвauввdduнвa aвв внz0z2auвнz3kРисунок 2.19 – Неприводимые блоки длины 2 (m = 2, n = 2)Производящая функция суммы весов неприводимых блоков для случаяm = 2, n = 2 имеет вид:72W2,2  x, uнн , uнв , uвн , uвв    ac  bd  uнвuвн x 2   a 2duвв  bc 2uнн  uнвuвн x3  ab cd u u u u xss s2 s 2нн нв вн ввss 1 a b d u u u x2 s 1ss 2s s2 s 1нв вн ввs 1 s 1 2 s  2  ab s cd suнвuвн xs 1s s 2 s 1  b sc 2d s 1uннuнвuвн x s 2abcduннuнвuвнuвв x 4  ac  bd  uнвuвн x   a duвв  bc uнн  uнвuвн x 1  bduнвuвн x 222232 2 42 22 2 5abcduнвuвн xa 2bd 2uнвuвнuвв x5 b2c 2duннuнвuвн x.221  bduнвuвн x1  bduнвuвн x1  bduнвuвн x 2нвнв нн...dd c...a bbвв внzkвнz1auввziz2duнвz2sz2s+2z0buвнduнв buвнz3cbвнz0cuннz2s-1нв нвzkz1cuнвduнв buвнkz2s+1нв...d...z3db aвн внz2s+1z2s-1auвнbuвнduнв buвнz2duнв buвнziduнвz2s+2kz2sРисунок 2.20 – Неприводимые блоки длины 2s + 1 (s ≥ 1) при m = 2, n = 273Отсюда следует формула:F2,2  x, uнн , uнв , uвн , uвв  11  W2,2  x, uнн , uнв , uвн , uвв 1  bduнвuвн x 2.1   ac  2bd  uнвuвн x 2   a 2duвв  bc 2uнн  uнвuвн x 3   acuннuвв  bduнвuвн  bduнвuвн x 4(2.15)Теорема 2.4 доказана.нв нвнв...ddd...a bbaвв вн внвнzkz1auввz4z2duнвz0ziauвнbuвнduнв buвнz3duнв buвнz5нв нвнвcddbвнzkz1cuнвz2sz3bвнz2s+1 kduнвz2s-1нн......cbвнz5z2s-1z2s+1z0buвнduнв buвнz2duнв buвнz4duнв buвнzicuннkz2sРисунок 2.21 – Неприводимые блоки длины 2s (s ≥ 2) при m = 2, n = 2Справедлива следующая теорема, сформулированная и доказанная автором.74Т е о р е м а 2.5.

В принятых выше обозначениях справедливо равенство:Fn,2  x, uнн , uнв , uвн , uвв   1  bdf n2uнвuвн x 2  1   ac  adf n1  2bdf n2  uнвuвн x 2 12 2 4, (2.16)bc  df n1  c  uннuнвuвн x3  b2d d  f n22  f n1 f n3   cf n3 uнвuвн xгде n – целое неотрицательное число, fi  fi  a, b, uвв , x    afi 1  bfi 2  uвв x приi  0 , f0  1, fi  0 при i  0 .Д о к а з а т е л ь с т в о . Введем обозначения произвольных замощенийпрямоугольников размером 1×n, 1×(n - 1), 1×(n - 2), 1×(n - 3) плитками размером1×1 с весом a и плитками размером 1×2 с весом b (рисунок 2.22).nn-11n-211n-31Рисунок 2.22 – Произвольные замощенияНа рисунках 2.23 и 2.24 приведены неприводимые блоки различной длиныдля случая m = 2, n ≥ 2.

Заметим, что все плитки произвольных замощенийнижнего ряда неприводимого блока имеют тип вв.Производящая функция суммы весов неприводимых блоков для случаяm = 2, n ≥ 2 имеет вид:Wn,2  x, uнн , uнв , uвн , uвв   acuнвuвн x 2  adf n1uнвuвн x 2  bdf n2uнвuвн x 2  ab d fs 1ss 2 b cd fss 1sfs 1s s 2 s 1n1 n2 нн нв внfs s 2su u x   b s d s f n1 f n3 f ns22uнвuвн x s 1 s s 2 sn 1 n 2 нв внu u u xs 2s 1 s 1 2 s  2  ab s cd s f ns2uнвuвн xs 175 b cd fs 1ss 1s 1 s 1 2 s 3  b s 1c 2d s f ns2uннuнвuвн xs 1 s 1 s 1 2 s  2n 3 n 2 нв внfu u xs 02 2 4abd 2 f n1 f n2uнвuвн x  ac  adf n1  bdf n2  uнвuвн x 1  bdf n2uнвuвн x 222 2 42 2 4b2d 2 f n1 f n3uнвuвн x bcdf n1uннuнвuвн x3 abcdf n2uнвuвн x221  bdf n2uнвuвн x1  bdf n2uнвuвн x1  bdf n2uнвuвн x 22 2 4bc 2df n3uнвuвн xbc 2uннuнвuвн x3,1  bdf n2uнвuвн x 2 1  bdf n2uнвuвн x 2где f n  f n  a, b, uвв , x    af n1  bf n2  uвв x при n  0 , f0  1 , f n  0 при n  0 .нвнвнвсaddвнabвнвна)б)нвнвнвdddbbвнвннвнвdddbвнвн......нвbнвdbaвнвннв......dbbвнвнв)Рисунок 2.23 – Неприводимые блоки при m = 2, n ≥ 2а) длины 1; б) длины n; в) длины ns (s ≥ 2)76нвнвнвнвcdddнв...d...bbbвнвнвнннcbbвнвна)нвнвнвdddнв......bbвнвннвнвнвнвcdddbbbвнвнвннвнвнвcdddbbbвнвнвнdcbbвнвннв......нвннdbaвнвннв......dbbвнвнб)Рисунок 2.24 – Неприводимые блоки при m = 2, n ≥ 2а) длины ns + 2 (s ≥ 0); б) длины ns + 1 (s ≥ 1)Отсюда следует формула:Fn,2  x, uнн , uнв , uвн , uвв  11  Wn,2  x, uнн , uнв , uвн , uвв  1  bdf n2uнвuвн x 2  1   ac  adf n1  2bdf n2  uнвuвн x 2 12 2 4.bc  df n1  c  uннuнвuвн x3  b2d d  f n22  f n1 f n3   cf n3 uнвuвн xТеорема 2.5 доказана.При произвольных m и n выполнить классификацию неприводимых блоковзамощенийвесьмазатруднительно.Вэтомслучаезадачувычисления77производящей функции весов замощений прямоугольника плитками удаетсярешить с помощью методов теории графов.Перенумеруем вершины определенного выше графа G в возрастающемпорядке первыми m + n натуральными числами и рассмотрим матрицу весовA   aij  орграфа G.

Таким образом,d j iuнн при 1  i  j  m, 0  j  i  n;d j iuнв при 1  i  m, m  1  j  m  n,1  j  i  n;aij  bi  juвн при m  1  i  m  n,1  j  m,1  i  j  m;bi  j uвв при m  1  i  m  n, m  1  j  m  n, 0  i  j  m;0 в остальных случаях.Пусть b0 = 0, d0 = 0. Для отыскания весов путей в орграфе G известен методтрансфер-матрицы [80, с.

354-356], суть которого изложена в следующей лемме.Л е м м а 2.3. Пустьhij  x    wij  x kkk 0– производящая функция суммы весов путей длины k в орграфе G, ведущих извершины i в вершину j. Тогдаhij  x   1i jdet  E  xA  jidet  E  xA ,где Е – единичная матрица, А – матрица весов орграфа G, det  E  xA  ji –определитель матрицы, полученной из  E  xA  вычеркиванием j-й строки и i-гостолбца.Непосредственное применение леммы 2.3 для решения задачи вычисленияпроизводящей функции весов замощений прямоугольника плитками требуетвычисления определителя порядка m + n. Порядок определителя удалось снизитьнавеличинуn.Полученныйрезультатсформулированная и доказанная автором.выражаетследующаятеорема,78Теорема2.6.

Для любых целых m, n (m ≥ 2, n ≥ 2) справедливаследующая формула:F  x, uнн , uнв , uвн , uвв  det R m,m,det Rгде R – матрица порядка m вида1  A11 d1uнн x  A12 A1  A22 21 A31A32 Am1,1Am1,2Am,2 Am,1Aij  uвнuнв x 2ns mi 1d 2uнн x  A13d m2uнн x  A1,m1d1uнн x  A23d m3uнн x  A2,m11  A33d m4uнн x  A3,m1Am1,31  Am1,m1Am,3Am,m1mdst m j 1d m1uнн x  A1,m d m2uнн x  A2,m d m3uнн x  A3,m ,d1uнн x  Am1,m 1  Am,mbt f s t i  j , i  1,2,..., m , j  1,2,..., m , b1 f s 1  b2 f s 2  ...

 bm f s m  uвв x при s  0,f s  f s  b1 , b2 ,..., bm , uвв , x   1 при s  0,0 при s  0,(2.17)матрица R m,m получается из R вычеркиванием m-й строки и m-го столбца.Д о к а з а т е л ь с т в о . Как следует из вышесказанного, производящаяфункцияF  x, uнн , uнв , uвн , uвв   hij  x i 0, j 0при условии, что i и j принадлежат множеству V  m  1,  m  2,..., n  1, n .Если же вершины орграфа G перенумеровать в возрастающем порядке первымиm + n натуральными числами, тоF  x, uнн , uнв , uвн , uвв   hij  x В силу леммы 2.3 получаемi m , j m.79F  x, uнн , uнв , uвн , uвв   1m mdet  E  xA mmdet  E  xA Функция Q  x   det Q , где Q   qij m ndet  E  xA mmdet  E  xA P x.Q x– матрица порядка m + n, такая, что1 при i  j;d u x при 1  i  j  m,1  j  i  n; j i ннd j iuнв x при 1  i  m, m  1  j  m  n,1  j  i  n;qij  bi  j uвн x при m  1  i  m  n,1  j  m,1  i  j  m;b u x при m  1  j  i  m  n,1  i  j  m; i  j вв0 в остальных случаях.Функция P  x   det P , где P   pij m n, причем P получается из Q заменойm-й строки строкой, в которой m-й элемент равен единице, а все остальныеэлементы равны нулю.Умножим матрицу Q слева на матрицу Q   qij m n, такую, что1 при i  j; nqij    f s  j i d suнв при 1  i  m, m  1  j  m  n; s  j i0 в остальных случаях.При этом воспользуемся рекуррентным соотношением (2.17).

Поскольку Q– верхняя треугольная матрица, элементы главной диагонали которой равны 1, тоdet Q  1 . Следовательно,det QQ  det Q  det Q  det Q  Q  x .ПолучаемQ  x   det QQ R0T Hn,80где T – матрица размерности n×m, H n – нижняя треугольная матрица порядка n,элементы главной диагонали которой равны 1, 0 – нулевая матрица размерностиm×n, R – матрица, указанная в формулировке теоремы. Отсюда находимQ  x   det R  det Hn  det R  1n  det R .Аналогично, умножим матрицу P слева на матрицу P   pij  , такую, чтоm n1 при i  j; npij    f s  j i d suнв при 1  i  m  1, m  1  j  m  n  1; s  j i0 в остальных случаях. Легко видеть, что det P  1. Следовательно, P  x   det PP .

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

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