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

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

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

В этом случае a  y  принимает видna  y    An,k x n1 y k 1 ,n 0 k 035где An , k – вероятность того, что число единиц в последовательности  I1, I 2 , , I n равно k, то естьAn,k  P  I1  I 2  In  k  .Находимa0  y   xy   1 Cnk A  0n  x n y k nkn 0 k 0 xy a0  x 1  y   xy.1  qx 1  y Отсюда по теореме 1.1 получаемay xyxy.1  qx  qxy  xy 1  qx  pxyП р и м е р 1.10. Выполняя подстановку xi 1yi  i 1x yпри i  0,при i  0в равенства (1.8) и (1.9), для рассмотренной выше последовательности находимna  y   n 0 k 0 d  d0 k 1And,0k,d x n1 y d ,где And,0k, d – вероятность того, что в последовательности  I1, I 2 , , I n  , содержащейk единиц, d непустых серий из нулей и d 0 пустых серий.По теореме 1.2 находимxt i xi 1 y  1i 1 a0 (y )   1  qt 1  tx  t t i xi 1 y i 1 t 136tx 2 y x 1x  tx 2  tx 2 y1  tx    1 2 22 22 2 txy1qt1qt1txtxtxtxy t 11  tx 1  tx  t 1 1x 1  tx 1  y   . 1  qt 1  t 2 x 2 1  y   t 1Применяя к последнему равенству свойство (1.11) произведения Адамара,получаемa0  y  x 1  qx 1  y  1  q 2 x 2 1  y .Следовательно, по теореме 1.1 имеемay x 1  qx 1  y  1  q 2 x 2  q 2 x 2 y  x  qx 2  qx 2 yx 1  qx 1  y  1  x  qx 2 1  y   q 2 x 2 1  y x 1  qx 1  y  1  x  1  q  qx 1  y 2x 1  qx 1  y  1  x  pqx 2 1  y .Таким образом, на конкретных примерах автором показана возможностьприменения произведения Адамара к вычислению производящих функцийраспределений различных статистик от серий нулей в последовательности1-зависимых индикаторов.Случайные блуждания также представляют несомненный интерес для рядаисследователей ([3], [4], [9], [15], [21] – [23], [38] – [40], [70], [81], [83]).

В третьейглаве будут показаны возможности применения произведения Адамара квычислению производящих функций некоторых статистик от серий рекуррентныхсобытий, а также производящих функций распределений некоторых статистик отосциллирующего случайного блуждания.37Глава 2. Применение произведения Адамара степенных рядовк решению некоторых комбинаторных задач2.1 Перечисление замощений прямоугольника плитками размеров 1×1и 1×nВ главе 1 были упомянуты все существовавшие до недавнего временирешения задачи перечисления замощений прямоугольника размера 2×r плиткамиразмера 1×1 с весом a и плитками размера 1×m с весом b в верхнем ряду, а такжеплитками размера 1×1 с весом c и плитками размера 1×n с весом d в нижнем ряду,сводящиеся к вычислению произведения Адамара11.1  ax  bx m 1  cx  dx nУказанное выше произведение Адамара вычислено комбинаторнымметодом в работе [96] при n = 2, b = 1, d = 1.

Метод этой работы не применим приn > 2.При произвольных m и n указанную задачу вычисления производящейфункции весов замощений прямоугольника плитками удается решить с помощьюалгебраического метода вычисления произведения Адамара ([81], [67]). Сутьэтого метода изложена в следующей лемме.Л е м м а 2.1. Для любого целого i (0 ≤ i ≤ m – 1) справедлива следующаяформула: 1 det  E  A m,mi1xi,1  q1  x  1  q2  x det  E  A iгде q1  x   b1x  b2 x 2  ...  bM x M , q2  x   d1x  d2 x 2  ...  dm x m , E – единичнаяматрица, A   aij M m– матрица порядка M + m, такая, что38b j i x j i при 1  i  m, 0  j  i  M ;aij  di  j при m  1  i  M  m, 0  i  j  m;0 в остальных случаях;b0  0 , d0  0 , det  E  A m,mi – определитель матрицы, полученной из  E  A вычеркиванием m-й строки и (m – i)-го столбца.Применение алгебраического метода вычисления произведения Адамаратребует вычисления определителей порядка M + m, то есть для того, чтобыполучить формулу (1.7), требуется вычислить определитель порядка m + 2, гдеm – произвольное целое число (m ≥ 2).

Порядок определителей удалось снизить навеличинуПолученныйm.результатвыражаетследующаятеорема,сформулированная и доказанная автором.Т е о р е м а 2.1. Для любых целых m, n, k (m ≥ 2, n ≥ 2, k < m) справедливаследующая формула:1xkdet R n,nm1  ax  bx 1  cx  dxdet S nгде S n – матрица порядка n вида1  acx  B1A121  A22 c  B2B3c  A32Bn1An1,2BnAn ,2A1,n2A1,n1A2,n2A2,n1A3,n2A3,n1c  An1,n21  An1,n1An,n2c  An,n1bcx n  A1n A2 nA3n,An1,n 1  An,n где Bi  df mi1x mi1 , Aij  bdf mi n j x m j i , i  1,2,..., n , j  2,3,..., n , матрица R nполучается из S n заменой первой строки строкойf xkkbf k n1x k 1bf k 3 x k n3 bf k 2 xk n2 bf k 1xk n1  ,39m n  m  (n  1)i  mni i a b , при m  0,f m  f m  a, b    i 0 i0, при m  0.Длядоказательстватеоремы2.1потребуетсяследующая(2.1)лемма,сформулированная и доказанная автором.Л е м м а 2.2.

Многочлены fm, определяемые формулой (2.1), удовлетворяютсоотношениюfi  a fi1  b fi nс начальными условиями: f0  1 и fi  0 при i < 0.Д о к а з а т е л ь с т в о . ПустьF  x 1.1  ax  bx nТогдаj j  j i i  n1i j1n 1 jjF  x abxxx  a b x1   a  bx n1  x j 0j 0 i 0  i  m n  m m 0 i 0  n  1 i  a mnibi xm ifm 0mxm ,то есть многочлены fm есть коэффициенты разложения F  x  в ряд по степеням x.С другой стороны,F  x   axF  x   bx n F  x   1 ,откуда, приравнивая коэффициенты левой и правой частей, получаем требуемоеутверждение.Д о к а з а т е л ь с т в о т е о р е м ы 2.1.

По лемме 2.1 получаемP x1xk,1  ax  bx n 1  cx  dx m Q  x 40где Q  x   det Q , Q   qij m n– матрица порядка m + n, такая, что1 при i  j;ax при 1  i  m, j  i  1;bx n при 1  i  m, j  i  n;qij  d при m  1  i  m  n, j  i  m;c при m  1  i  m  n, j  i  1;0 в остальных случаях.Функция P  x   det P , где P   pij m n, причем P получается из Q заменойm-й строки строкой, в которой (m – k)-й элемент равен единице, а все остальныеэлементы равны нулю.Умножим матрицу Q слева на матрицу Q   qij m n, такую, что1 при i  n и j  i  m, либо i  n  1 и i  j  n;j iпри i  n, i  j  m, j  i  m  2;df j i xqij  j idf j i x  c при i  1, j  m;0 в остальных случаях.Воспользовавшись леммой 2.2, получаем 0QQ   TmSn ,H где H – матрица размерности m×n, Tm – верхняя треугольная матрица порядка m,элементы главной диагонали которой равны 1, 0 – нулевая матрица размерностиn×m, S n – матрица, указанная в формулировке теоремы.

Вычисляя определительпо теореме Лапласа, получаем:det QQ   1 det Sn .mn41Меняя местами первые n и последние m строк матрицы Q , получим нижнюютреугольную матрицу, элементы главной диагонали которой равны 1, так чтоdet Q   1 . Следовательно, det Q  det Sn .mnАналогично, умножим матрицу P слева на матрицу P   pij m n, котораяотличается от Q только (m + n)-й строкой и m-м столбцом: pmn, j  f j k  m x j k mпри m  k  j  m  1 , pmn,m  1 , pmn, j  0 при остальных значениях j; pim  0 приi  m  n . Применяя лемму 2.2, переставляя (m + n)-ю строку и (m + n)-й столбецна первые места и заменяя элементы первой строки на противоположные, изматрицы PP получаем матрицу вида 0L mRn ,V где V – матрица размерности m×n, L m – верхняя треугольная матрица порядка m,элементы главной диагонали которой равны 1, 0 – нулевая матрица размерностиn×m, R n – матрица, указанная в формулировке теоремы.

Следовательно,det P   1mn1 det PP  det R n .Теорема 2.1 доказана.Выпишем полученный результат в явном виде при n = 3. Получим: длялюбого целого m ≥ 2 и любого целого k < m справедлива следующая формула:P x1xk,3m1  ax  bx 1  cx  dxQ xгдеP  x   f k xk  bcf k 2 x k 1  bc 2 f k 1x k 2  bd  f m1 f k 2  f m2 f k 1  2 f m3 f k  x mk bcd  f m1 f k 1  f m2 f k  bf m3 f k 2  bf m4 f k 1  x mk 1  b2d 2  f m1 f m3 f k 2  f m1 f m4 f k 1  f m22 f k 2  f m2 f m3 f k 1  f m2 f m4 f k  f m23 f k  x 2 mk ,(2.2)42Q  x   1  acx  bc3 x3  d  f m  2bf m3  x m bcd  3 f m2  2af m3  xm1  bc2d  2 f m1  af m2  bfm4  xm2 bd 2  2 f m f m3  2 f m1 f m2  bf m2 f m4  bf m23  x 2 m bcd 2  f m f m2  f m21  2bf m1 f m4  2bf m2 f m3  abf m2 f m4  abf m23  x 2 m1  b md 3 x3m .Таким образом, автором получен новый прием вычисления произведенийАдамара рациональных функций вида1xk,1  ax  bx n 1  cx  dx mгде m, n, k (m ≥ 2, n ≥ 2, 0 ≤ k < m).

Известный ранее алгебраический метод([81], [67]) вычисления произведений Адамара рациональных функций указанноговида требует вычисления определителей порядка m + n. С помощью методовкомбинаторного анализа и линейной алгебры порядок определителей авторомснижен на величину m, что расширяет возможности применения произведенияАдамара для получения решения конкретных задач в явном виде, поскольку вэтом случае порядок определителей от величины m не зависит, он равенпроизвольному, но фиксированному n. С помощью полученного автором новогоприема вычисления произведений Адамара задача перечисления замощенийпрямоугольника размера 2×r плитками размеров 1×1, 1×m и 1×n решена автором вобщем виде, а для n = 3 формулы получены автором в явном виде.2.2 Перечислениезамощенийпрямоугольникапроизвольной длиныРассмотрим производящую функцию f  d , d ,..., d  xr 0r12nr11  d1 x  d 2 x 2  ...

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

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