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

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

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

Перечислим все возможные разбиения  r вектора (r, r) приr = 5, такие, что первая компонента вектора разбивается на слагаемые 1 и 3, авторая компонента – на слагаемые 2 и 3:5,0,0, 0,1,1    1,1,1,1,1 ,  2,3  ,5,0,0, 0,1,1    1,1,1,1,1 , 3,2   ,2,0,1, 0,1,1    1,1,3 ,  2,3  ,2,0,1, 0,1,1    1,3,1 ,  2,3  ,2,0,1, 0,1,1     3,1,1 ,  2,3  ,2,0,1, 0,1,1    1,1,3 , 3,2   ,2,0,1, 0,1,1    1,3,1 ,  3,2   ,2,0,1, 0,1,1     3,1,1 , 3,2   .62Сумма весов этих разбиений с учетом формулы (2.7) определяется равенством:f5  d1, d3  f5  b2 , b3    d15  3d12d3  2b2b3  2b2b3d15  6b2b3d12d3 .На рисунке 2.7 приведены соответствующие замощения.d1 d1 d1 d1 d1b2b3d1 d1 d1 d1 d1b3b2d1 d1b2d1 d1b3d1d3b2d3b3d3b3d1d3d1b2b3d1b2d3b3d3b2d1 d1b3d1 d1b2Рисунок 2.7 – Различные замощения прямоугольника размера 2×5,соответствующие разбиениям  5   s1 ,s2 ,s3 , t1 ,t2 ,t3при s1  3s3  5 и 2t2  3t3  5Задача вычисления производящей функции суммы весов разбиений r   s1 ,s2 ,...,sn , t1 ,t2 ,...,tmв общем виде решается с помощью теорем 2.2 и 2.3,сформулированных и доказанных автором.Таким образом, спомощью полученного автором новогометодавычисления произведения Адамара рациональных функций, выраженноготеоремами 2.2 и 2.3, автором в общем виде решена задача вычисленияпроизводящей функции суммы весов разбиений  r   s1 ,s2 ,...,sn , t1 ,t2 ,...,tm компонентдвумерного вектора на произвольные слагаемые.

Полученный автором новыйметод вычисления произведения Адамара рациональных функций позволяет вданной задаче снять ограничения на величину слагаемого и решить известнуюранее задачу в новой постановке.632.5 Применение метода трансфер-матрицы в задаче перечислениязамощенийпрямоугольникаплиткамипочислутиповвзаимногорасположения плитокРассмотрим задачу замощения прямоугольника плитками в динамике.Будем укладывать верхний ряд прямоугольника размера 2×r плитками размеров1×1, 1×2,…, 1×n, имеющими соответственно вес d1, d2,…, dn, а нижний ряд –плитками размеров 1×1, 1×2,…, 1×m с весом b1, b2,…, bm соответственно.Укладку верхнего ряда будем выполнять последовательно слева направо дотех пор, пока верхний ряд не станет выступать над нижним.

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

Плитку нижнего ряда назовем плиткой типа вв, если при ее укладке,выступающим остается верхний ряд. Если же при укладке плитки нижнего ряда,выступающим становится нижний ряд, то эту плитку отнесем к плиткам типа вн.Плитку верхнего ряда назовем плиткой типа нн, если при ее укладке,выступающим остается нижний ряд. Под весом замощения понимаетсяпроизведение весов образующих его плиток.Постановку задачи удобнее пояснить посредством конкретных примеров.П р и м е р 2.13. На рисунке 2.8 представлено замощение прямоугольникаразмера 2×r (r = 16) десятью плитками, имеющее вес b22b4b8d23d32d4 и содержащеетри плитки типа нн, три плитки типа нв, три плитки типа вн, одну плитку типа вв.П р и м е р 2.14. Замощение прямоугольника размера 2×r (r = 11) восьмьюплитками, представленное на рисунке 2.9, имеет вес b1b32b4d1d2d3d5 и содержит64одну плитку типа нн, три плитки типа нв, три плитки типа вн, одну плитку типавв.1 d11211d22...

1d33dnnнвнннннвнннвd2d4b8d2d3b2d3b4d2b2вввнвнrвн1 b1111b22... 1b33bmmРисунок 2.8 – Замощение прямоугольника размера 2×16нвнн нвнвd3d2 d1d5b1b4b3b3вввнвнвнРисунок 2.9 – Замощение прямоугольника размера 2×11П р и м е р 2.15. На рисунке 2.10 представлено замощение прямоугольникаразмера 2×r (r = 14) семью плитками, имеющее вес b4b10d22d32d4 и содержащее триплитки типа нн, две плитки типа нв, две плитки типа вн.нвннd2d4нннвннd2d3b10d3b4внвнРисунок 2.10 – Замощение прямоугольника размера 2×1465Определение xk k 1 ,  yk k 12.1. Пусть– последовательностинеотрицательных целых чисел. Последовательность целых чисел  zk k 0 называютосциллирующей, если она удовлетворяет условиям: z0  0 ; если k > 0, то zk 1  ykzk   zk 1  xkприzk 1  0,приzk 1  0.Будем полагать, что элементы последовательностей xk k 1 ,  yk k 1принадлежат множествам 0,1,..., n , 0,1,..., m соответственно.

Тогда элементыосциллирующей zk  k 0последовательностипринадлежатмножествуm  1,  m  2,..., n  1, n .Рассмотрим ориентированный граф 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 ввПоследовательность zk  k 0при i  0, j  0;при i  0, j  0;при i  0, j  0;при i  0, j  0.элементовмножестваVявляетсяпоследовательностью вершин некоторого бесконечного пути в орграфе G тогда итолько тогда, когда она является осциллирующей.Если в качестве последовательностей xk k 1 ,  yk k 1рассматриватьсоответственно последовательности длин плиток верхнего и нижнего ряда66замощения прямоугольника размером 2×r, то осциллирующая последовательность zk  k 0строится по описанному выше алгоритму укладки плиток.

Здесь z0  0соответствует начальному моменту укладки, когда прямоугольник пуст.ПримерГрафически2.16.осциллирующаяпоследовательность,соответствующая замощению десятью плитками, приведенному на рисунке 2.8,представлена на рисунке 2.11. Рядом с дугами конечного пути из вершины z0  0в вершину z10  0 в орграфе G, изображенного на рисунке 2.11, указанысоответствующие им веса.П р и м е р 2.17. На рисунке 2.12 графически представлена осциллирующаяпоследовательность,соответствующаязамощениювосьмьюплитками,приведенному на рисунке 2.9.zkz5z1z9b2uввd3uнвz6d2uнвz0d2uнвz4b8uвнd2uннz8b4uвнb2uвнz10d3uннz3z7d4uннz2Рисунок 2.11 – Осциллирующая последовательность, соответствующаязамощению прямоугольника размера 2×16k67zkz1z7b1uввz2d3uнвb3uвнz5b4uвнd1uнвz0d5uнвz4z8kb3uвнd2uннz6z3Рисунок 2.12 – Осциллирующая последовательность, соответствующаязамощению прямоугольника размера 2×11 восьмью плиткамиПример2.18.

Осциллирующая последовательность для замощенияпрямоугольника семью плитками, приведенного на рисунке 2.10, графическипредставлена на рисунке 2.13.Вычислим производящую функцию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 – сумма весов замощений прямоугольников всевозможных размеров kплитками, из которых i1 плиток типа нн, i2 плиток типа нв, i3 плиток типа вн, i4плиток типа вв.Рассмотримсначалачастныеслучаирешениязадачивычисленияпроизводящей функции весов замощений прямоугольника плитками с учетомтипов взаимного расположения плиток, позволяющие получить формулы в явномвиде.Рассмотрим замощения прямоугольника размером 2×r плитками размера1×1 с весом c и плитками размера 1×n с весом d в верхнем ряду, а также плитками68размера 1×1 с весом a и плитками размера 1×m с весом b в нижнем ряду. Искомуюпроизводящую функцию обозначим для данного случая Fn,m  x, uнн , uнв , uвн , uвв  .zkz1z5d2uнвz0z7d3uнвb4uвнkd3uннz4b10uвнd2uннz6z3d4uннz2Рисунок 2.13 – Осциллирующая последовательность, соответствующаязамощению прямоугольника размера 2×14 семью плиткамиП р и м е р 2.19.

На рисунке 2.14 представлено замощение прямоугольникаразмера 2×r (r = 14), имеющее вес a 4b5c5d 3 и содержащее две плитки типа нн,шесть плиток типа нв, шесть плиток типа вн, три плитки типа вв.П р и м е р 2.20. На рисунке 2.15 представлено замощение прямоугольникаразмера 2×r (r = 15), имеющее вес a5b5c3d 4 и содержащее одну плитку типа нн,шесть плиток типа нв, шесть плиток типа вн, три плитки типа вв.Для вычисления производящей функции Fn,m  x, uнн , uнв , uвн , uвв  суммы весовзамощений прямоугольников всевозможной длины k плитками воспользуемся69комбинаторным методом, примененным Л.

Шапиро [99] в связи с некоторымитождествами для ортогональных полиномов Чебышева, а также Й.Х. Кимом [96],получившим некоторое обобщение результатов Л. Шапиро.нв нв нн2нвc c ca bнн нвнвнвc cdda a adbbbbвнвн вв вв внrвн вн1 c1вв1внdn1 a11bmРисунок 2.14 – Замощение прямоугольника размера 2×142нвнв нннвнвdc cbddabbнвнвdca a a abbвнвн вв вв вн внrвв внвнвв1 c11dn1 a11bmРисунок 2.15 – Замощение прямоугольника размера 2×15Прямоугольник размера 2×r вертикальными линиями разбивается нанеприводимые блоки меньшей длины. Этот факт поясним примерами.Пример2.21. На рисунке 2.16 приведено разбиение замощения,представленного на рисунке 2.14, на неприводимые блоки.нвнв нннвнннвнвнвcaвнc cbвнdccdda a aвв вв внbввbвнbвнbвнРисунок 2.16 – Разбиение замощения прямоугольника размера 2×14на неприводимые блоки70Пример2.22.Разбиениенанеприводимыеблокизамощения,изображенного на рисунке 2.15, представлено на рисунке 2.17.нвнв ннda bвв внc cbвннвdbввнвнвнвdda a aвв вв внcaвнbвнbвнРисунок 2.17 – Разбиение замощения прямоугольника размера 2×15на неприводимые блокиСправедлива следующая теорема, сформулированная и доказанная автором.Т е о р е м а 2.4.

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

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