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

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

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

Мак-Магона,введенном им в комбинаторной теории разбиений целых чисел (см. [71, c. 84]).Этот оператор для ряда от одной переменной λ определяется следующим образом:  ak    ak .kk k 0Связь Ω-оператора с произведением Адамара может быть выражена следующимсоотношением: 1   1 G  x   H  x    1   G   H  x   .     Таким образом, вычисление произведения Адамара может быть сведено квычислению Ω-оператора. Справедливо и обратное утверждение, иллюстрацией ккоторому может служить лемма 5 в работе [67]. Вычисление Ω-операторапредставляет интерес в связи с рядом комбинаторных задач, которые могут бытьрешены с его привлечением.

Много таких задач рассмотрено в серии работГ. Эндрюса с соавторами, подробный список которых приведен в [94]. В этихработах активно используются системы компьютерной алгебры, поскольку объемвычислений слишком велик, чтобы выполнить их вручную.Работа [94] посвящена построению алгоритма вычисления Ω-оператораМак-Магона для случая рациональных функций.

В силу отмеченного выше, этоталгоритм может быть использован для вычисления произведения Адамара, иобратно.Алгоритмиспользуетразложениерациональныхфункцийнапростейшие дроби и технику симметрических функций для отысканияΩ-оператора от произведений простейших дробей. При этом используетсяалгебраическая замкнутость поля коэффициентов.В 2011 году М.И. Толовиковым ([81], [67]) предложен метод, дающийформулы для произведений Адамара рациональных функций в виде отношения15определителей, элементы которых зависят от коэффициентов числителя изнаменателя дробей, задающих эти функции. Вывод формул используеткомбинаторную технику, и поэтому не зависит от алгебраических свойств полякоэффициентов.Рассмотрим задачу о перечислении замощений прямоугольника плитками.Рассмотрим производящую функцию f  a, b  xr 0rr11  ax  bx mпоследовательности, задаваемой рекуррентным соотношениемf r  a, b   a f r 1  a, b   b f r m  a, b (1.1)с начальными условиями: f0  1 и f r  0 при r < 0.

При a = b = 1 и m = 2 даннаяпоследовательность представляет собой последовательность чисел Фибоначчи.Элемент f r  a, b  последовательности может быть интерпретирован как суммавесов замощений прямоугольника размера 1×r плитками размера 1×1 с весом a иплитками размера 1×m с весом b. Под весом замощения понимается произведениевесовобразующихегоплиток.Суммавесовзамощенийkплиткамипрямоугольника размера 1×r равна коэффициенту при xr в выражении  ax  bx m k.Например, при r = 3 прямоугольник размера 1×3 можно замостить тремяспособами, используя для этого плитки размеров 1×1 и 1×2 (рисунок 1.1, а).Сумма весов этих замощений определяется равенством:f3  a, b   a3  2ab .(1.2)При r = 4 прямоугольник размера 1×4 можно замостить плитками размеров1×1 и 1×2 пятью способами (рисунок 1.1, б).

Сумма весов этих замощенийопределяется равенством:f 4  a, b   a 4  3a 2b  b2 .(1.3)16При r = 5 прямоугольник размера 1×5 можно замостить восьмьюспособами, используя для этого плитки размеров 1×1 и 1×2 (рисунок 1.1, в).Сумму весов этих замощений определим с помощью формул (1.1) – (1.3):f5  a, b   a f 4  a, b   b f3  a, b   a  a 4  3a 2b  b2   b  a3  2ab   a5  4a3b  3ab2 .Аналогичныеперечислительныеинтерпретациидлянекоторыхпоследовательностей натуральных чисел (например, последовательности {3 r},последовательности Якобсталя {Jr}, последовательности Трибоначчи {Tr},последовательности Пелля {Pr}) можно найти в работах О.В. Кузьмина иМ.В.

Серегиной ([32], [33]).a a aabbaа)a a a aa abababa aabbbб)a a a a aa a aba aabbbbaabba abba a aaв)Рисунок 1.1 – Различные замощения прямоугольника размера 1×rплитками размеров 1×1 и 1×2а) r = 3; б) r = 4; в) r = 5Последовательность Трибоначчи {Tr} = 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,…представляетсобойчисларазличныхзамощений(полныхпокрытий)17прямоугольника размера 1×r плитками размеров 1×1, 1×2 и 1×3 [33, с. 92].Последовательность Трибоначчи задается рекуррентным соотношениемTr  Tr 1  Tr 2  Tr 3с начальными условиями: T1  1 и Tr  0 при r < 1.Последовательность Якобсталя {Jr} = 1, 3, 5, 11, 21, 43, 85, 171, 341, 683,…представляет собой числа различных замощений прямоугольника размера 1×rквадратными плитками размера 1×1 и прямоугольными плитками размера 1×2,имеющими два разных цвета [33, с.

92]. Последовательность Якобсталя задаетсярекуррентным соотношениемJ r  J r 1  2 J r 2с начальными условиями: J1  1 и J r  0 при r < 1.Последовательность {3r} = 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,…представляет собой числа различных замощений прямоугольника размера 1×rквадратными плитками размера 1×1, имеющими три разных цвета [33, с. 92].Последовательность Пелля {Pr} = 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378,…представляет собой числа различных замощений прямоугольника размера 1×rквадратнымиплиткамиразмера1×1,имеющимидваразныхцвета,ипрямоугольными плитками размера 1×2 [33, с. 93]. Последовательность Пеллязадается рекуррентным соотношениемPr  2Pr 1  Pr 2с начальными условиями: P1  1 и P0  0 .К задачам о перечислении замощений плитками относится также задачаперечисления горизонтально выпуклых полимино [80, с.

375]. Полимино P – этоконечное объединение единичных квадратов на плоскости, вершины которыхимеют целые координаты, причем P связно и связность нельзя нарушить, удаляяконечное число точек. Полимино P называется горизонтально выпуклым, есликаждый горизонтальный ряд квадратов представляет собой нераспадающуюся18полоску. Пусть f(n) – число горизонтально выпуклых полимино, составленных изn квадратов.

Из рисунка 1.2 видно, что f 1  1 , f  2   2 , f  3  6 . Задачавычисления производящей функцииF  x    f  n  xnn 1решена А. Гесселем [80, с. 378] методом трансфер-матрицы с применениемпроизведения Адамара. Вклад в решение данной задачи был внесен такжеГ. Пойа [98], Д. Кларнером [97] и Р. Стенли [100].Рисунок 1.2 – Горизонтально выпуклые полимино при n = 1, 2, 3Вернемся к решению задачи о перечислении замощений прямоугольникаплитками.Коэффициент f r  a, b  f r  c, d  при x r в произведении11  f r  a , b  f r  c, d  x rmn1  ax  bx 1  cx  dxr 0может быть интерпретирован как сумма весов замощений прямоугольникаразмера 2×r плитками размера 1×1 с весом a и плитками размера 1×m с весом b вверхнем ряду, а также плитками размера 1×1 с весом c и плитками размера 1×n свесом d в нижнем ряду.

На рисунке 1.3 приведен пример замощенияпрямоугольника плитками.Прямоугольник размера 2×r вертикальными линиями разбивается нанеприводимые блоки меньшей длины. На рисунке 1.4 приведено разбиениезамощения, представленного на рисунке 1.3, на неприводимые блоки.19b2cda adbbdddbc c cr1 a11bm1 c11dnРисунок 1.3 – Замощение прямоугольника размера 2×r плиткамиbcda adbdbddbc c cРисунок 1.4 – Разбиение замощения на неприводимые блокиОпределим производящую функциюWm,n  x    ws x s ,(1.4)s 0где ws – сумма весов неприводимых блоков длины s. Так как любое замощениеможет быть единственным образом представлено в виде последовательностинеприводимых блоков, то производящая функция суммы весов замощений можетбыть найдена по формуле fr  a, b  fr  c, d  xr   Wm,n  x  r 0s 0s1.1  Wm,n  x (1.5)Формула (1.5) доказана математиками Р.

Стенли и А. Гесселем [91].На рисунке 1.5 приведены неприводимые блоки различной длины дляслучая m = 2, n = 2.Производящая функция суммы весов неприводимых блоков для данногослучая имеет вид:W2,2  x   acx   bd  a 2d  bc 2  x 2 s 1s 2 2ab s cd s x 2 s 1   b s c 2d s 1  a 2b s 1d s  x 2 s 202 22242abcdx3  b c d  a bd  x acx   bd  a d  bc  x 1  bdx 21  bdx 2222acx   bd  a 2d  bc 2  x 2  abcdx3  b2d 2 x 41  bdx 2.Отсюда следует формула:111  ax  bx 2 1  cx  dx 21  bdx 2.1  acx   a 2d  bc 2  2bd  x 2  abcdx3  b2 d 2 x 4(1.6)Формула (1.6) при b = 1 и d = 1 получена Л. Шапиро [99] в 1981 г. в связи снекоторыми тождествами для ортогональных полиномов Чебышева.bdaca adа)bcdc cб)...bbb...daadbd...b...dbdcв)bc...bddb...acbd...bd...adг)Рисунок 1.5 – Неприводимые блоки (при m = 2, n = 2)а) длины 1; б) длины 2; в) длины 2s + 1 (s ≥ 1); г) длины 2s (s ≥ 2)21Рассмотрим производящую функцию f  a, b  xs 0sksxkkm txaxbx1  ax  bx m t 0последовательности, элемент f s  a, b  которой может быть найден как суммавесов замощений прямоугольника размера 1×(s + k) плитками размера 1×1 свесом a и плитками размера 1×m с весом b, причем первая плитка каждогозамощения имеет размер 1×k и вес 1.В равенствеxk1s k  f s  a , b  x   f r  c, d  x r 221  ax  bx 1  cx  dxs 0r 0r kr 0r k  f r  k  a , b  x r   f r  c, d  x r   f r  k  a , b  f r  c , d  x rкоэффициентf r k  a, b  f r  c, d  при x r определяет сумму весов замощенийпрямоугольника размера 2×r плитками размера 1×1 с весом a и плитками размера1×m с весом b в верхнем ряду, а также плитками размера 1×1 с весом c иплитками размера 1×n с весом d в нижнем ряду, причем первая плитка в верхнемряду каждого замощения имеет размер 1×k и вес 1.

Первый неприводимый блоккаждого замощения содержит в верхнем ряду на первом месте плитку размера 1×kи веса 1, остальные неприводимые блоки замощения выбираются из блоков,представленных на рисунке 1.5.Нарисунке 1.6введеныобозначенияпроизвольныхзамощенийпрямоугольников размеров 1×k, 1×(k – 1), 1×m, 1×(m – 1), 1×(m – 2) плиткамиразмера 1×1 с весом c и плитками размера 1×n с весом d, причем сумма весов всехтаких замощений соответственно равна f k  c, d  , f k 1  c, d  , f m  c, d  , f m1  c, d  иf m2  c, d  .Производящую функцию суммы весов неприводимых блоков, размещаемыхна первом месте каждого замощения (рисунок 1.7), обозначим Vm,n  x  . Очевидно,22 fr k  a, b  fr  c, d  x  V2,2  x  W2,2  x   srr ks 0V2,2  x ,1  W2,2  x гдеV2,2  x   f k  c, d  x   ab dkss 0s 1f k 1  c, d  xk  2 s 1  b scd s f k 1  c, d  x k 2 s s 1adf k 1  c, d  x k 1 bcdf k 1  c, d  x k 2 f k  c, d  x 1  bdx 21  bdx 2kf k  c, d  x k  adf k 1  c, d  x k 1  bcdf k 1  c, d  x k 2  bdf k  c, d  x k 21  bdx 2f k  c, d  x k  adf k 1  c, d  x k 1  bd cf k 1  c, d    cf k 1  c, d   df k 2  c, d   x k 21  bdx 2f k  c, d  x k  adf k 1  c, d  x k 1  bd 2 f k 2  c, d  x k 2.1  bdx 2k1k-1******m11*****m-11m-21Рисунок 1.6 – Произвольные замощенияОтсюда следует формула:f k  c, d  x k  adf k 1  c, d  x k 1  bd 2 f k 2  c, d  x k 2xk1,1  ax  bx 2 1  cx  dx 2 1  acx   a 2d  bc 2  2bd  x 2  abcdx3  b 2d 2 x 4которую получил Й.

Ким [95] при b = 1 и d = 1.Особенностью неприводимых блоков замощений при m ≥ 2 и n = 2(рисунок 1.8) является то, что плитки размера 1×1 с весом a могут бытьразмещены только в начале или в конце верхнего ряда.23k2b******d*****а)...b...dadб)bd*****...b...dbdcв)Рисунок 1.7 – Неприводимые первые блоки замощений (при m = 2, n = 2)а) длины k; б) длины k + 2s + 1 (s ≥ 0); в) длины k + 2s (s ≥ 1)acmb2bbdа)...b...dб)bdв)bbda...b...dbbdd......dadbdbbdг)abdbd...b...dbdadд)Рисунок 1.8 – Неприводимые блоки (при m ≥ 2, n = 2)а) длины 1; б) длины m; в) длины ms (s ≥ 2); г) длины ms + 1 (s ≥ 1);д) длины ms + 2 (s ≥ 0)24Производящая функция суммы весов неприводимых блоков для случаяm ≥ 2 и n = 2 имеет вид:Wm,2  x   acx  bf m x m   b s d s 1 f m21 f ms22 x ms s 2 2ab d fsss 1s 1 ms 1m1 m2fx  a 2b s d s 1 f ms2 x ms 2 s 0b2df m21x 2 m2abdf m1 x m1a 2 dx 2 acx  bf m x 1  bdf m2 x m 1  bdf m2 x m 1  bdf m2 x mmacx  a 2dx 2  bf m x m  abd (2 f m1  cf m2 ) x m1  b2d ( f m21  f m f m2 ) x 2 m,1  bdf m2 x mгде f m  f m  c, d  .Отсюда получаем111m21  ax  bx 1  cx  dx 1  Wm,2  x 1  bdf m2 x m.1  acx  a 2dx 2  b( f m  df m2 ) x m  abd (2 f m1  cf m2 ) x m1  b 2d ( f m21  f m f m2 ) x 2 mПроизводящая функция суммы весов неприводимых блоков, размещаемыхна первом месте каждого замощения (рисунок 1.9), для случая m ≥ 2 и n = 2 имеетвид:Vm,2  x   f k x   b d fksss 1s 1k  msm2 m1 k 1ff x  ab s d s 1 f ms2 f k 1x k ms 1 s 0bdf m1 f k 1 x k madf k 1 x k 1 fk x 1  bdf m2 x m 1  bdf m2 x mkf k x k  adf k 1x k 1  bd ( f m1 f k 1  f m2 f k ) x k m.1  bdf m2 x mОтсюда следует формула:25xk1m1  ax  bx 1  cx  dx 2f k x k  adf k 1x k 1  bd ( f m1 f k 1  f m2 f k ) x k m,1  acx  a 2dx 2  b( f m  df m2 ) x m  abd (2 f m1  cf m2 ) x m1  b 2d ( f m21  f m f m2 ) x 2 m(1.7)которую при b = 1 и d = 1 получил Й.

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

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