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

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

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

 d n x nплитками43последовательности, задаваемой рекуррентным соотношениемf r  d1, d2 ,..., dn   d1 f r 1  d2 f r 2  ...  dn f r n(2.3)с начальными условиями f0 = 1 и fr = 0 при r < 0. При di = 1 (i = 1, 2, …, n) и n = 2данная последовательность представляет собой последовательность чиселФибоначчи. Элемент f r  d1, d2 ,..., dn  может быть интерпретирован как суммавесовзамощений1×1, 1×2,…, 1×n,прямоугольникаимеющимиразмерасоответственно1×rвесплиткамиd1, d2,…, dn.размеровПодвесомзамощения понимается произведение весов образующих его плиток. Сумма весовзамощений k плитками прямоугольника размера 1×r равна коэффициенту при xr ввыражении  d1 x  d2 x 2  ...

 d n x n  .kПостановку задачи удобнее всего пояснить посредством конкретныхпримеров.П р и м е р 2.1. При r = 2 прямоугольник размера 1×2 можно замоститьдвумя способами, используя для этого плитки размеров 1×1, 1×2 и 1×3(рисунок 2.1, а). Сумма весов этих замощений определяется равенством:f 2  d1, d2 , d3   d12  d2 .(2.4)П р и м е р 2.2.

При r = 3 прямоугольник размера 1×3 можно замоститьчетырьмя способами, используя для этого плитки размеров 1×1, 1×2 и 1×3(рисунок 2.1, б). Сумма весов этих замощений определяется равенством:f3  d1, d2 , d3   d13  2d1d2  d3 .(2.5)П р и м е р 2.3. При r = 4 прямоугольник размера 1×4 можно замоститьплитками размеров 1×1, 1×2 и 1×3 семью способами (рисунок 2.1, в). Сумма весовэтих замощений определяется равенством:f 4  d1, d2 , d3   d14  3d12d2  2d1d3  d22 .(2.6)П р и м е р 2.4.

При r = 5 прямоугольник размера 1×5 можно замоститьтринадцатью способами, используя для этого плитки размеров 1×1, 1×2 и 1×344(рисунок 2.1, г). Сумму весов этих замощений определим с помощью формул(2.3) – (2.6):f5  d1, d2 , d3   d1 f 4  d1, d2 , d3   d2 f3  d1, d2 , d3   d3 f 2  d1, d2 , d3   d1  d14  3d12d2  2d1d3  d22   d2  d13  2d1d2  d3   d3  d12  d2   d15  4d13d2  3d12d3  3d1d22  2d2d3 .d1 d1d2d1 d1 d1d1 d2а)(2.7)d2 d1d3б)d1 d1 d1 d1d1 d1 d2d1d1 d2 d1d3d3d2 d1 d1d2d2d1в)d1 d1 d1 d1 d1d1 d2d2d1 d1 d1 d2d2 d1 d2d1d3d1d1 d1 d2 d1d2d2 d1d2d3d1 d2 d1 d1d1 d1d2 d1 d1 d1d3d3d3d1 d1d2г)Рисунок 2.1 – Различные замощения прямоугольника размера 1×rплитками размеров 1×1, 1×2 и 1×3а) r = 2; б) r = 3; в) r = 4; г) r = 5Коэффициент f r  d1, d2 ,..., dn  f r  b1, b2 ,..., bm  при x r в произведении112n1  d1x  d 2 x  ...

 d n x 1  b1x  b2 x 2  ...  bm x m45  f r  d1 , d 2 ,..., d n  f r  b1 , b2 ,..., bm  x rr 0может быть интерпретирован как сумма весов замощений прямоугольникаразмера 2×r плитками размеров 1×1, 1×2,…, 1×n в верхнем ряду, а такжеплитками размеров 1×1, 1×2,…, 1×m – в нижнем ряду. Плитка верхнего рядаразмера 1×i имеет вес di (i = 1, 2,…, n). Плитка нижнего ряда размера 1×j имеетвес bj (j = 1, 2,…, m).П р и м е р 2.5. На рисунке 2.2 представлено замощение прямоугольникаразмера 2×r (r = 16) плитками произвольной длины n ( n ).

Вес данногозамощения равен b13b25b3d12d22d32d4 .1 d1121d221d33d3d1 d1 d2d4b1 b1 b2b3b1 b2r1 b111b221b33... 1dnnd2b2... 1b2d3b2bmmРисунок 2.2 – Замощение прямоугольника размера 2×r плиткамиП р и м е р 2.6. При r = 2 прямоугольник размера 2×2 можно замоститьчетырьмя способами, используя для этого плитки размеров 1×1, 1×2 и 1×3(рисунок 2.3, а). Сумма весов этих замощений с учетом формулы (2.3)определяется равенством:f 2  d1, d2 , d3  f 2  b1, b2 , b3    d12  d2 b12  b2   b12d12  b12d 2  b2d12  b2d 2 .П р и м е р 2.7.

Прямоугольник размера 2×3 (r = 3) можно замоститьшестнадцатью способами, используя для этого плитки размеров 1×1, 1×2 и 1×3(рисунок 2.3, б). Из формулы (2.5) следует, что сумма весов этих замощенийопределяется равенством:46d1 d1b1 b1d1 d1b2d2b1 b1d2b2а)d1 d1 d1b1 b1 b1d1 d2b1 b1 b1d2 d1b1 b1 b1d3b1 b1 b1d1 d1 d1b1 b2d1 d1 d1b2 b1d1 d2b1 b2d1 d2b2 b1d2 d1b1 b2d2 d1b2 b1d3b1 b2d3b2 b1d1 d1 d1b3d1 d2b3d2 d1b3d3b3б)Рисунок 2.3 – Различные замощения прямоугольника размера 2×rплитками размеров 1×1, 1×2 и 1×3а) r = 2; б) r = 3f3  d1, d2 , d3  f3  b1, b2 , b3    d13  2d1d2  d3 b13  2b1b2  b3   b13d13  2b13d1d2  b13d3  2b1b2d13  4b1b2d1d2  2b1b2d3  b3d13  2b3d1d 2  b3d3 .П р и м е р 2.8.

Прямоугольник размера 2×4 (r = 4) можно замостить сорокадевятью способами, используя для этого плитки размеров 1×1, 1×2 и 1×3 (рисунок2.4).Из формулы (2.6) следует, что сумма весов этих замощений определяетсяравенством:f 4  d1, d2 , d3  f 4  b1, b2 , b3    d14  3d12d2  2d1d3  d22 b14  3b12b2  2b1b3  b22   b14d14  3b14d12d2  2b14d1d3  b14d22  3b12b2d14  9b12b2d12d2  6b12b2d1d3  3b12b2d22  2b1b3d14  6b1b3d12d2  4b1b3d1d3  2b1b3d22  b22d14  3b22d12d2  2b22d1d3  b22d22 .47d1 d1 d1 d1b1 b1 b1 b1d1 d1 d2b1 b1 b1 b1d1 d2 d1b1 b1 b1 b1d2 d1 d1b1 b1 b1 b1d1d3b1 b1 b1 b1d3d1b1 b1 b1 b1d2d2b1 b1 b1 b1d1 d1 d1 d1b1 b1 b2d1 d1 d1 d1b1 b2 b1d1 d1 d1 d1b2 b1 b1d1 d1 d2b1 b1 b2d1 d1 d2b1 b2 b1d1 d1 d2b2 b1 b1d1 d2 d1b1 b1 b2d1 d2 d1b1 b2 b1d1 d2 d1b2 b1 b1d2 d1 d1b1 b1 b2d2 d1 d1b1 b2 b1d2 d1 d1b2 b1 b1d1d3b1 b1 b2d1d3b1 b2 b1d1d3b2 b1 b1d3d1b1 b1 b2d3d1b1 b2 b1d3d1b1 b1d2d2b1 b1 b2b1d2b2 b1d2d2b2 b1 b1d1 d1 d1 d1b1b3d1 d1 d1 d1b3b1d1 d1 d2b1b3d1 d1 d2b3b1d1 d2 d1b1b3d1 d2 d1b3b1d2 d1 d1b1b3d2 d1 d1b3b1d1b1d1d2d2b1b3d2d2b3b1b2d3b3d2d3b3d3b1d1 d1 d1 d1b2b2b1d1b3d1 d1 d2b2b2d1d3b2b2d3b3d1b1d1 d2 d1b2b2d3d1b2b2d2b2d2 d1 d1b2b2d2b2Рисунок 2.4 – Различные замощения прямоугольника размера 2×4плитками размеров 1×1, 1×2 и 1×3Общее решение задачи перечисления замощений прямоугольника размера2×rплиткамипроизвольнойдлинывыраженотеоремами2.2и2.3,сформулированными и доказанными автором.Т е о р е м а 2.2.

Для любых целых m, n, k (m ≥ 2, n ≥ 2, k < m) справедливаследующая формула: 1 det R m,mk ,1xk2n2m1  d1 x  d 2 x  ...  d n x 1  b1x  b2 x  ...  bm xdet Rkгде R – матрица порядка m вида481  A11 d1 x  A121  A22 A21 A31A32 AAm1,2 m1,1 AAm,2 m,1Aij  ns mi 1ds xt m  j 1d1 x  A23 d m 3 xbt f s t i  j ,m 3 A2,m11  A33d m4 x m4  A3,m1Am1,31  Am1,m1Am,3Am,m1nmsd m2 x m2  A1,m1d 2 x 2  A13Bi    f s mi d s x s ,B1 B2 B3 ,Bm1 Bm i  1,2,..., m ,j  1,2,..., m  1 ,s m id0  1 ,b1 f s 1  b2 f s 2  ...  bm f s mf s  f s  b1 , b2 ,..., bm   1 при s  0,0 при s  0,при s  0,(2.8)матрица R m,mk получается из R вычеркиванием m-й строки и (m – k)-го столбца.Д о к а з а т е л ь с т в о .

Как следует из леммы 2.1, для произведения АдамараP x1xk1  d1 x  d2 x 2  ...  d n x n 1  b1 x  b2 x 2  ...  bm x m Q  x функция Q  x   det Q , где Q   qij m n– матрица порядка m + n, такая, что1 при i  j;j iпри 1  i  m,1  j  i  n;  d j i xqij  bi  j при m  1  i  m  n,1  i  j  m;0 в остальных случаях.Функция P  x   det P , где P   pij m n, причем P получается из Q заменойm-й строки строкой, в которой (m – k)-й элемент равен единице, а все остальныеэлементы равны нулю.Умножим матрицу Q слева на матрицу Q   qij m n, такую, что491 при i  j; nqij    f s  j i d s x s при 1  i  m, m  1  j  m  n; s  j i0 в остальных случаях.При этом воспользуемся рекуррентным соотношением (2.8).

Поскольку Q –верхняя треугольная матрица, элементы главной диагонали которой равны 1, тоdet Q  1 . Следовательно,det QQ  det Q  det Q  det Q  Q  x .ПолучаемQ  x   det QQ R0T Hn,где 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 s x s при 1  i  m  1, m  1  j  m  n  1; s  j i0 в остальных случаях. Легко видеть, что det P  1.

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

Для любых целых m, n, k (m ≥ 2, n ≥ 2, k < m) справедливаследующая формула:1xkdet G,2n2m1  d1 x  d2 x  ...  d n x 1  b1 x  b2 x  ...  bm xdet Hгде H – матрица порядка n видаL12 D1 D1  L22 2 D3b1  L32 Dn1 bn3  Ln1,2bn2  Ln ,2 Dnmb0  1 , Lij   bs xs  j is iL13L1,n1L23L2,n11  L33L3,n1bn4  Ln1,31  Ln1,n1bn3  Ln,3b1  Ln,n1s  j id ft jtmi 1s t  j i, Di    bs i 1 f s x s , i  1,2,..., n , j  2,3,..., n ,s 0d1 f s 1  d 2 f s 2  ...

 d n f s nf s  f s  d1 , d 2 ,..., d n   1 при s  0,0 при s  0,при s  0,матрица G получается из H заменой первой строки строкойC1nCi  x k i 1  d s f k s i 1 .s iL1,n L2,n L3,n ,Ln1,n 1  Ln,n C2 C3Cn1 Cn  ,(2.9)51Д о к а з а т е л ь с т в о . Как следует из леммы 2.1, для произведения Адамарасправедливо представлениеP x1xk,1  d1 x  d2 x 2  ...  d n x n 1  b1 x  b2 x 2  ...  bm x m Q  x в котором функция Q  x   det Q , где Q   qij m n– такая матрица порядка m + n,что1 при i  j;j iпри 1  i  m,1  j  i  n;  d j i xqij  bi  j при m  1  i  m  n,1  i  j  m;0 в остальных случаях,а функция P  x   det P , где P   pij m n, причем P получается из Q заменой m-йстроки строкой, в которой (m – k)-й элемент равен единице, а все остальныеэлементы равны нулю.Умножим матрицу Q слева на матрицу Q   qij  , в которойm n1 при i  j; nqij    bs f s i  j x s i  j при m  1  i  m  n,1  j  m; s i  j0 в остальных случаях.При этом воспользуемся рекуррентным соотношением (2.9).

Поскольку Q –нижняя треугольная матрица, элементы главной диагонали которой равны 1, тоdet Q  1 . Следовательно,det QQ  det Q  det Q  det Q  Q  x .ПолучаемQ  x   det QQ SmT0H,52где T – матрица размерности m×n, S m – верхняя треугольная матрица порядка m,элементы главной диагонали которой равны 1, 0 – нулевая матрица размерностиn×m, H – матрица, указанная в формулировке теоремы. Отсюда находимQ  x   det Sm  det H  1m  det H  det H .Аналогично, умножим матрицу P слева на матрицу P   pij m n, в которой1 при i  j;j m kпри i  m, m  k  j  m  1; f j m k x npij  s i  jпри m  1  i  m  n  1,1  j  m  1;  bs f s i  j x s i  j0 в остальных случаях.  Легко видеть, что det P  1. Следовательно, P  x   det PP . Разложив det PP по последнему столбцу, получаем определитель, равный det PPи имеющийпорядок m + n – 1.

Таким образом, имеем P  x   det PP Vm1W0G,где Vm1 – верхняя треугольная матрица порядка m – 1, элементы главнойдиагонали которой равны 1, W – матрица размерности (m – 1)×n, 0 – нулеваяматрица размерности n×(m – 1), G – матрица, указанная в формулировкетеоремы. Отсюда находимP  x   det Vm1  det G  1m1  det G  det G .Теорема 2.3 доказана.Теорема 2.2 используется при n > m, а теорема 2.3 – при n < m. Эти теоремыприменимы для правильных рациональных дробей (при k < m). В общем случаеможновыделитьцелуючастьдроби,применитьсвойствопроизведения Адамара, а также формулу x k   s0 g s x s  g k x k .линейности53Таким образом, автором получен новый метод вычисления произведенийАдамара рациональных функций вида1xk,1  d1 x  d 2 x 2  ...

 d n x n 1  b1x  b2 x 2  ...  bm x mгде m, n, k (m ≥ 2, n ≥ 2, 0 ≤ k < m), сводящийся к вычислению определителейпорядка min(m, n). Известный ранее алгебраический метод ([81], [67]) вычисленияпроизведений Адамара рациональных функцийуказанного вида требуетвычисления определителей порядка m + n. Посредством сформулированных идоказанных автором теорем 2.2 и 2.3 задача перечисления замощенийпрямоугольника размера 2×r плитками произвольной длины решена автором вобщем виде. Полученный автором новый метод вычисления произведенияАдамара рациональных функций позволяет в данной задаче снять ограничения надлину плитки и решить известную ранее задачу в новой постановке.2.3 Перечисление упорядоченных разбиений компонент вектора нафиксированные слагаемыеРассмотрим упорядоченное разбиение  s , t   1, 2 ,..., st  числа r на sслагаемых, равных 1, и t слагаемых, равных целому числу n  2 , причем s  nt  r ,где r, s, t – целые неотрицательные числа.

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

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