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

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

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

Слагаемому, равному 1, приписываетсявес a, слагаемому n – вес b. Под весом разбиения понимается произведение весовобразующих его слагаемых. Обозначимi , j   1 , 2 ,..., i  j упорядоченноеразбиение числа r на i слагаемых, равных 1 и имеющих вес c, и j слагаемых свесом d, равных целому числу m  2 , причем i  mj  r , где i, j – целыенеотрицательные числа.Рассмотрим производящие функции s ,ta sbt x s nt ,i , jci d j xi mj ,54где суммирование ведется по всем определенным выше множествам разбиений.Первая из этих функций равна производящей функции f r  a, b  x r r 01n kaxbx1  ax  bx n k 0последовательности, задаваемой рекуррентным соотношениемf r  a, b   a f r 1  a, b   b f r n  a, b с начальными условиями: f0  1 и f r  0 при r < 0. Элемент f r  a, b  может бытьнайден как сумма весов упорядоченных разбиений s ,t .

Сумма весовупорядоченных разбиений числа r на k слагаемых равна коэффициенту при xr ввыражении  ax  bx n  . Вторая функция равна производящей функцииk1m kfc,dxcxdxr1  cx  dx m k 0r 0rпоследовательности, задаваемой рекуррентным соотношениемf r  c, d   c f r 1  c, d   d f r m  c, d с теми же начальными условиями.Рассмотрим теперь разбиения вектора (r, r), представляющие собой пары r    s ,t , i , j  определенных выше разбиений числа r. Вес такого разбиенияопределим как произведение весов разбиений  s ,t , i , j . Разбиение  s ,t можнорассматривать как разбиение первой компоненты вектора на слагаемые 1 и n, аразбиение i , j – как разбиение второй компоненты вектора на слагаемые 1 и m.По определению произведения Адамара11  f r  a , b  f r  c, d  x r .nm1  ax  bx 1  cx  dxr 0(2.10)55Коэффициент f r  a, b  f r  c, d  при xr определяет сумму весов разбиений r    s ,t , i , j  .Задача вычисления производящей функции суммы весов разбиений r    s ,t , i , j  решается по теореме 2.1, сформулированной и доказаннойавтором.Теорема 2.1 позволяет определять сумму весов разбиений  r    s ,t , i , j при любом r.

С одной стороны, из теоремы 2.1 и формулы (2.10) следует, чтоP x   f r  a , b  f r  c, d  x r ,Q  x  r 0с другой стороны, по формуле Тейлора имеемP x  1 d r  P x Q  x  r 0 r ! dx r  Q  x  xr .x 0Отсюда получаемf r  a, b  f r  c, d  1 d r  P x r ! dx r  Q  x  .(2.11)x 0Применяя формулу Лейбница для вычисления производной высших порядков,находим1 r  r   r s ds  1 f r  a, b  f r  c, d     P 0 s r ! s 0  s dx  Q  x  .(2.12)x 0Покажем пример применения формулы (2.12).П р и м е р 2.9. Определим сумму весов разбиений вектора (r, r) приусловии, что r = 5, первая компонента вектора разбивается на слагаемые 1 и 3, авторая компонента вектора – на слагаемые 1 и 4.

Чтобы воспользоватьсяформулой (2.12) при r = 5, вычислим производные от функции  Q  x   :156 1 Q  x , 2QxQx  2 1 Q  x  Q  x ,232QxQ  x  Q  x 3 1 Q  x  Q  x  Q  x  Q  x ,6  6432QxQ  x Q  x  Q  x  1  Q  x    36  Q  x   Q  x    2454Q  x Q  x  Q x IV84Q  x  Q  x Q  x 32 Q  x    Q  x  ,6Q  x  Q  x 2IV32 1  Q  x    240 Q  x   Q  x   90 Q  x  Q  x     120654Q  x Q  x Q  x  Q x V532 Q  x   Q  x   20 Q  x  Q  x   10 Q  x  Q  x   Q  x 60Q  x Q  x Q  x Q  x 2IV43V32.Отсюда по формуле Лейбница получаемVP  x   Q  x  P IV  x  Q  x P  x  Q  x d 5  P x  P  x52010232dx5  Q  x   Q  x Q  x Q  x Q  x 2P  x   Q  x  3 60120Q  x P  x   Q  x  Q  x 54 604P  x  Q  x  Q  x Q  x 3P  x   Q  x   Q  x  102 180Q  x 4 40P  x  Q  x Q  x 2P  x  Q  x  Q  x Q  x 357 30P  x   Q  x  25Q  x 3P  x   Q  x  5120Q  x  206 90P  x  Q IV  x Q  x 23 240P  x  Q  x   Q  x  Q  x P  x  Q  x  Q  x Q  x 3 10P  x   Q  x   Q  x Q  x 524P  x   Q  x   Q  x 2 60Q  x P  x  Q  x  Q IV  x Q  x 34P  x QV  x Q  x 2.(2.13)При m = 4 и k = 0 из формулы (2.2) получаемP  x   a 2bcdx5  2abdx 4  1 ,Q  x   b4d 3 x12  3b3cd 2 x9  2a 2b2d 2 x8  bc 2d  a3  3b  x6  a 2bcdx5  ad  a3  4b  x 4  bc3 x3  acx  1 .P  0   1 ,Учитывая, чтоPV  0   120a 2bcd ,P  0   0 ,Q  0   1 ,P  0   0 ,Q  0   ac ,P  0   0 ,P IV  0   48abd ,Q  0   0 ,Q  0   6bc3 ,QIV  0   24ad  a3  4b  , QV  0   120a 2bcd , из формул (2.11) и (2.13) находим1 d 5  P x f 5  a , b  f 5  c, d  5! dx5  Q  x  x 01120a 2bcd  240a 2bcd  120a5c5  360 a 2bc5 120 240a 2cd  a3  4b   120a 2bcd  a5c5  2a5cd  3a2bc5  6a2bcd .(2.14)На рисунке 2.5 представлены замощения прямоугольника 2×5 (соответствующиеразбиениям  5    s ,t , i , j  при s  3t  5 , i  4 j  5 ) плитками размера 1×1 с весом58a и плитками размера 1×3 с весом b в верхнем ряду, а также плитками размера1×1 с весом c и плитками размера 1×4 с весом d – в нижнем ряду.a a a a aс с с с сa a a a aсda a a a adсbaaс с с с сba aс с с с сa aсbсa adba adbbсdbaсdaba aс с с с сaсadbda aсРисунок 2.5 – Различные замощения прямоугольника размера 2×5,соответствующие разбиениям  5Перечислим все разбиения  5    s ,t , i , j  , сумма весов которых определяется поформуле (2.14): 5   5,0 , 5,0    1,1,1,1,1 , 1,1,1,1,1  ,  5   5,0 , 1,1    1,1,1,1,1 , 1,4   , 5   5,0 , 1,1    1,1,1,1,1 ,  4,1  ,  5   2,1, 5,0    1,1,3 , 1,1,1,1,1  , 5   2,1, 5,0    1,3,1 , 1,1,1,1,1  ,  5   2,1 , 5,0     3,1,1 , 1,1,1,1,1  , 5   2,1, 1,1    1,1,3 , 1,4   ,  5   2,1, 1,1    1,3,1 , 1,4   , 5   2,1, 1,1     3,1,1 , 1,4   ,  5   2,1, 1,1    1,1,3 ,  4,1  , 5   2,1, 1,1    1,3,1 ,  4,1  ,  5   2,1, 1,1     3,1,1 ,  4,1  .Таким образом, с помощью полученного автором новогометодавычисления произведений Адамара рациональных функций, выраженноготеоремой 2.1, автором решена задача вычисления производящей функции суммывесов разбиений  r    s ,t , i , j  , где r, s, t, i, j, m, n – целые неотрицательные59числа, n  2 , m  2 , s  nt  r , i  mj  r .

Ранее эта задача была решена только вчастных случаях при n = 2 [80, с. 367].2.4 Перечисление упорядоченных разбиений компонент вектора напроизвольные слагаемыеРассмотрим  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).Рассмотрим производящие функции s1 , s2 ,..., snd nsn x s1 2 s2 d1s1 d2s2 nsn,t1 ,t2 ,...,tmbmtm xt1 2t2 b1t1b2t2 mtm,где суммирование ведется по всем определенным выше множествам разбиений.Первая из этих функций равна производящей функции f  d , d ,..., d  xr 0r12nr11  d1 x  d 2 x 2  ...  d n x n   d1 x  d 2 x 2  ...

 d n x n kk 0последовательности, задаваемой рекуррентным соотношениемf r  d1, d2 ,..., dn   d1 f r 1  d2 f r 2  ...  dn f r n60с начальными условиями f0 = 1 и fr = 0 при r < 0. Элемент f r  d1, d2 ,..., dn  можетбыть найден как сумма весов упорядоченных разбиений  s1 ,s2 ,...,sn . Сумма весовупорядоченных разбиений числа r на k слагаемых равна коэффициенту при xr ввыражении  d1 x  d2 x 2  ...

 d n x n  . Вторая функция равна производящей функцииk f b , b ,..., b  xrr 012mr11  b1x  b2 x 2  ...  bm x m   b1 x  b2 x 2  ...  bm x m kk 0последовательности, задаваемой рекуррентным соотношениемf r  b1, b2 ,..., bm   b1 f r 1  b2 f r 2  ...  bm f r mс теми же начальными условиями.Рассмотрим теперь разбиения вектора (r, r), представляющие собой пары r   s1 ,s2 ,...,sn , t1 ,t2 ,...,tmопределенных выше разбиений числа r. Вес такогоразбиения определим как произведение весов разбиений  s1 ,s2 ,...,sn , t1 ,t2 ,...,tm .Разбиение  s1 ,s2 ,...,sn можно рассматривать как разбиение первой компонентывектора на слагаемые 1, 2,…, n, а разбиение t1 ,t2 ,...,tm – как разбиение второйкомпоненты вектора на слагаемые 1, 2, …, m.Постановку задачи удобнее всего пояснить посредством конкретныхпримеров.П р и м е р 2.10.

Одно из разбиений вектора (r, r) при r = 7, такое, что перваякомпонента вектора разбивается на слагаемые 1, 2, 3, а вторая компонента – наслагаемые 1, 2, 3, 4, имеет вид: 7   2,1,1, 1,1,0,1    1,3,2,1 ,  4,1,2   .Указанное выше разбиение имеет вес b1b2b4d12d2d3 . На рисунке 2.6, а) приведеносоответствующее замощение.61d1d3b4d2 d1b1 b2а)d5b5d7b4b2d3b1 b2 b1б)Рисунок 2.6 – Замощение прямоугольника размера 2×r,соответствующее разбиениюа)  7   2,1,1, 1,1,0,1    1,3,2,1 ,  4,1,2   ;б) 15   0,0,1,0,1,0,1, 2,2,0,1,1     5,7,3 ,  5,2,4,1,2,1 П р и м е р 2.11. Одно из разбиений вектора (r, r) при r = 15 с весомb12b22b4b5d3d5d7 , такое, что первая компонента вектора разбивается на слагаемые1, 2, 3, 4, 5, 6, 7, а вторая компонента – на слагаемые 1, 2, 3, 4, 5, имеет вид:15   0,0,1,0,1,0,1, 2,2,0,1,1     5,7,3 ,  5,2,4,1,2,1  .На рисунке 2.6, б) приведено соответствующее замощение.П р и м е р 2.12.

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

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