Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах Потехина Елена Алексеевна

Содержание к диссертации

Введение

Глава 1. Произведение Адамара в комбинаторных и вероятностных задачах и методы его вычисления 12

Глава 2. Применение произведения Адамара степенных рядов к решению некоторых комбинаторных задач 37

2.1 Перечисление замощений прямоугольника плитками размеров 11 и 1n 37

2.2 Перечисление замощений прямоугольника плитками произвольной длины 42

2.3 Перечисление упорядоченных разбиений компонент вектора на фиксированные слагаемые 53

2.4 Перечисление упорядоченных разбиений компонент вектора на произвольные слагаемые 59

2.5 Применение метода трансфер-матрицы в задаче перечисления замощений прямоугольника плитками по числу типов взаимного расположения плиток 63

2.6 Осциллирующее случайное блуждание в задаче перечисления упорядоченных разбиений 81

Глава 3. Применение произведения Адамара степенных рядов к решению некоторых вероятностных задач 88

3.1 Производящие функции некоторых статистик от серий рекуррентных событий 88

3.2 Вычисление распределений некоторых статистик от осциллирующего случайного блуждания 101

3.3 Вероятность замощения прямоугольника плитками 113

Список литературы

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

Введение к работе

Актуальность темы исследования. Произведением Адамара формальных степенных рядов

О(х) = ^2-₀к^хк и ^Я(^Х) = 2Г-<А-^ называется степенной ряд

v / v / ^— Z~ik=o&k ^к

Хорошо известно, что произведение Адамара разложений в ряд рациональных функций является рациональной функцией. В то же время, явных формул для вычисления произведения Адамара степенных рядов рациональных функций в общем случае до недавнего времени известно не было. Техника вычисления произведения Адамара в задачах дискретной математики недостаточно развита и не систематизирована.

Произведение Адамара степенных рядов находит применение в ряде задач перечислительной комбинаторики и дискретной теории вероятностей. В некоторых из них применение произведения Адамара позволяет найти решение в явном виде. Конкретные задачи, с одной стороны, служат источником примеров, в которых требуется вычислять произведение Адамара степенных рядов, а с другой - их решение позволяет находить новые методы вычисления произведения Адамара рациональных функций в более или менее общих ситуациях.

Цель работы: исследовать возможности применения произведения Адамара степенных рядов для некоторого класса комбинаторных и вероятностных задач.

Задачи диссертационной работы:

проанализировать существующие методы вычисления произведения Адамара степенных рядов рациональных функций;

проанализировать существующие подходы к решению комбинаторных и вероятностных задач с применением произведения Адамара;

получить новый метод вычисления произведения Адамара степенных рядов рациональных функций;

используя новый метод вычисления произведения Адамара степенных рядов рациональных функций, решить ряд комбинаторных задач;

решить некоторые вероятностные задачи с применением произведения Адамара.

Объектом исследования является класс комбинаторных и вероятностных задач.

Предметом исследования являются комбинаторные и вероятностные задачи, связанные с применением произведения Адамара степенных рядов, а также методы вычисления произведения Адамара степенных рядов рациональных функций.

Методологическую и теоретическую основу исследования составляют научные труды отечественных и зарубежных авторов в области комбинаторного анализа и дискретной теории вероятностей.

Методы исследования. При выполнении исследования использовались следующие методы: метод производящих функций, методы линейной алгебры, теории вероятностей, метод трансфер-матрицы, а также алгебраический метод вычисления произведения Адамара.

Научная новизна результатов исследования:

1) Автором получен новый комбинаторно-алгебраический метод вычисления произведения Адамара рациональных функций. Известный ранее алгебраический метод¹ [19] вычисления произведения Адамара рациональных функций требует вычисления опреде-

¹ Толовиков М.И. Случайные блуждания и произведение Адамара степенных рядов // Обозрение прикладной и промышленной математики. 2011. Т. 18, вып. 3. С. 505-506.

лителей порядка m + n. С помощью методов комбинаторного анализа и линейной алгебры порядок определителей автором снижен до величины min(m, n), что расширяет возможности применения произведения Адамара для получения решения конкретных задач в явном виде.

2) С помощью полученного автором нового метода вычисления произведения
Адамара найдено общее решение задачи перечисления замощений прямоугольника раз
мера 2r плитками размеров 11, 1m и 1n, а для n = 3 формулы получены автором в
явном виде. Решение этой задачи в частных случаях (при n = 2) с помощью комбинатор
ных методов ранее опубликовали в своих работах Л. Шапиро¹ и Й.Х. Ким².

3) Полученный автором новый метод вычисления произведения Адамара рацио
нальных функций позволяет в задаче перечисления замощений прямоугольника размера
2r плитками снять ограничения на длину плитки и решить известную ранее задачу в но
вой постановке (получено общее решение задачи перечисления замощений прямоуголь
ника размера 2r плитками произвольной длины).

4) С помощью полученного автором нового метода вычисления произведения
Адамара рациональных функций (теоремы 1, 2 и 3) решена задача перечисления упоря
доченных разбиений компонент двумерного вектора на слагаемые (первая компонента
разбивается на слагаемые 1 и n, а вторая – на слагаемые 1 и m, где m, n – произвольные
целые числа, m 2, n 2). Ранее эта задача была решена только в частных случаях при
n = 2³.

1. С помощью доказанных автором теорем 2 и 3 решена задача перечисления упорядоченных разбиений компонент двумерного вектора на произвольные слагаемые. Полученный автором новый метод вычисления произведения Адамара рациональных функций позволяет в данной задаче снять ограничения на величину слагаемого и решать известную ранее задачу в новой постановке.

2. Комбинаторным методом автором получены явные формулы для вычисления производящей функции весов замощений прямоугольника плитками по числу типов взаимного расположения плиток с максимальными длинами в верхнем и нижнем ряду m = 2, n = 2 соответственно, а также при m = 2, n 2. Объект исследования в данном случае является новым.

3. Получено общее решение задачи вычисления производящей функции весов замощений прямоугольника плитками по числу типов взаимного расположения плиток, а также вычисления производящей функции весов разбиений. Решение получено с применением метода трансфер-матрицы, что по сравнению с комбинаторным методом позволяет снять ограничения на длину плитки, а также на величину слагаемого в разбиении.

4. С применением произведения Адамара автором явно вычислены производящие функции распределений некоторых статистик от серий рекуррентных событий, а также производящие функции распределений некоторых статистик от осциллирующего случайного блуждания. Ранее произведение Адамара в задачах исследования распределений статистик от серий указанных выше случайных событий не применялось. Применение произведения Адамара позволяет явно вычислить производящие функции распределений

¹ Shapiro L.W. A combinatorial proof of a Chebyshev polynomial identity // Discrete Math.
1981. Vol. 34. P. 203-206.

² Kim J.H. Hadamard products, lattice paths, and skew tableaux. Doctor of Philosophy thesis,
Brandeis University Department of Mathematics. ProQuest, UMI Dissertation Publishing, 2012. 69 p.

³ Стенли Р. Перечислительная комбинаторика: Пер. с англ. М.: Мир, 1990. 440 с.

некоторых характеристик случайных последовательностей в тех случаях, в которых их явное вычисление с помощью комбинаторных методов затруднительно.

Теоретическая и практическая значимость исследования. Работа носит теоретический характер. Результаты ее первой главы представляют методический интерес и могут быть использованы в преподавании, в частности, для чтения специальных курсов. Все результаты представляют интерес для специалистов по комбинаторному анализу и теории вероятностей и могут быть использованы в этих областях для решения конкретных задач. Некоторые результаты исследования (теоремы 10 и 11) могут быть использованы при разработке алгоритмов распределения ресурсов в вычислительных сетях.

Апробация результатов исследования. Результаты исследования докладывались на 24 научных конференциях, симпозиумах и семинарах:

– на семинаре отдела дискретной математики Математического института им. В.А. Стеклова РАН (Москва, 8 апреля 2013 г.);

– на семинаре кафедры математической кибернетики Московского государственного университета им. М.В. Ломоносова (28 ноября 2014 г.);

– на XX Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2013» (Москва, МГУ, 9 – 12 апреля 2013 г.);

– на XLVII Международной конференции «Процессы управления и устойчивость» (Санкт-Петербург, СПбГУ, 4 – 7 апреля 2016 г.);

– на IX Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (Петрозаводск, Институт прикладных математических исследований Карельского научного центра РАН, 30 мая – 3 июня 2016 г.);

– на Международной конференции по алгебре, анализу и геометрии (Казань, КФУ, 26 июня – 2 июля 2016 г.);

– на Международной научно-практической конференции «Математика в современном мире», посвященной 150-летию Д.А. Граве (Вологда, 2013 г.);

– на XII, XIII и XIV Всероссийских симпозиумах по прикладной и промышленной математике (2011 – 2013 гг.)

– на 6-й и 7-й Международных научно-технических конференциях «Информатизация процессов формирования открытых систем на основе САПР, АСНИ, СУБД» (Вологда, ВоГТУ, 2011 г., 2013 г.);

– на четырех Всероссийских научно-практических конференциях «Череповецкие научные чтения» (Череповец, ЧГУ, 2010 – 2013 гг.);

– на семи военно-научных конференциях (Череповец, филиал Воен. акад. МО РФ, ЧВВИУРЭ, 2010 – 2015 гг.).

Публикации. Результаты исследования опубликованы в 26 работах ([1] – [26]), из которых [9], [17], [19] и [23] – в журналах, рекомендованных ВАК РФ. В совместной работе [19] соискателю принадлежат разделы 4 и 7, а также свойство 3 теоремы 7. Кроме того, в совместной работе [1] соискателю принадлежат примеры вычисления производящих функций распределений статистик в последовательностях 1-зависимых индикаторов.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, а также списка литературы, содержащего 102 наименования. Работа проиллюстрирована 38 рисунками. Общий объем работы – 138 страниц.

Перечисление замощений прямоугольника плитками произвольной длины

Задача перечисления замощений прямоугольника плитками тесно связана с задачей перечисления упорядоченных разбиений компонент вектора на слагаемые. Эта связь указана в работе Р. Стенли [80, с. 367]. Разбиением называется набор целых положительных чисел (при данной их сумме), в котором порядок чисел не принимается в расчет [69, с. 129]. Как отмечает Дж. Риордан [69], понятие разбиения введено Г. Лейбницем в 1669 г., а действительное развитие понятия разбиения начинается с трудов Л. Эйлера [86, с. 234-250]. В работах О.В. Кузьмина [29], О.В. Кузьмина и А.А. Балагура [5], О.В. Кузьмина и О.В. Леоновой ([30], [31]) разбиения применяются для интерпретации комбинаторных чисел и полиномов. Упорядоченные разбиения в ряде работ ([69, с. 129], [87, с. 67], [13, с. 59]) названы композициями. Понятие композиции принадлежит П. Мак-Магону (1915). Композициями называются упорядоченные наборы целых положительных чисел [69, с. 129]. Развитию теории частично упорядоченных множеств посвящены также работы В.А. Баранского и Т.А. Королевой [6], А.М. Вершика и Ю.В. Якубловича [10], А.А. Старовойта [79]. В работах Л.М. Коганова ([24], [25]) исследуются упорядоченные пары упорядоченных разбиений.

Таким образом, задачи перечисления замощений прямоугольника плитками и перечисления упорядоченных разбиений компонент вектора на целые положительные слагаемые, сводящиеся к вычислению произведения Адамара xk 1 - ax - bx m 1-cx- dx n, до недавнего времени были решены лишь в частных случаях при т 2 ип = 2. Серии в случайных последовательностях неизменно привлекают внимание исследователей ([2], [11], [19], [20], [26], [27], [72] - [77]). Рассмотрим последовательность случайных величин {In}"=1, определенных на одном вероятностном пространстве (Q, F,P). Определение 1.1. Последовательность {In } n=1 называется стационарной последовательностью 1-зависимых случайных индикаторов, если 1) каждая из случайных величин In принимает только два значения: 0 и 1; 2) вероятность P(I 1+t=a1, I2+t=a2,..., Ik+t=ak) при любых kєП, a 1, a2,..., ак є {0,1} не зависит от t; 3) случайные векторы (I 1, I 2,...,/ ) и (Ii+1,Ii+2,...,Ik) независимы при любых k 2, 1 i k. Приведем примеры последовательностей 1-зависимых индикаторов. Пример 1.1. Простейшим примером является последовательность независимых случайных величин, распределенных по закону Бернулли и принимающих только два значения 0 и 1. Пример 1.2. Пусть {Хп}=1 - последовательность независимых одинаково распределенных случайных величин и /:R2 {0,1} - измеримая функция. Построим новую последовательность {1„}=1 следующим образом: для любого пєП положим I„ = f(Xn,Xn+1). Тогда {/„}"=1- последовательность 1-зависимых случайных индикаторов. Об этой последовательности говорят, что она имеет 2-блочную структуру. Пример 1.3. В условиях примера 1.2 положим , ч Г0 при X Y, f(Xj) = \ [1 при X Y.

При этом будем говорить, что пара (X, Y) образует убывание, если X Y, и образует возрастание, если X Y. Таким образом, {I}=1- последовательность 1-зависимых случайных индикаторов возрастаний в последовательности {Хп }"=1.

Пример 1.4. Приведем пример последовательности 1-зависимых случайных индикаторов, которая не имеет 2-блочной структуры. Пример такой последовательности имеется в статье [14]. При а Р положим 1 ґ1 -1 0 0 1 0" 0 , у = а , А = а 0 -1 , л - 0 0 1 0 Л vP 0 0, v000у

Определим распределение последовательности случайных индикаторов {1п}=1 следующим образом: для любых а1,(%,...,ак є{0,1} положим P(/1 = а1, 12 = а2,..., 1к = ак ) = Аа Аа .. .Аа у х, где точка означает скалярное произведение в пространстве столбцов размерности три. Нетрудно проверить, что {/„}"=1- последовательность 1-зависимых случайных индикаторов и для этой последовательности k=0) = P(/1 = 0,/2 = 0,...,/, = 0) а при к = 1, (3 при к = 2, 0 при к 3. Пусть {0,1} - полугруппа всех слов над алфавитом {0,1} с операцией конкатенации слов. Функция 4: {0,1} —» R определяется равенствами А(а1а2...ак) = P(lx =a1J2=a2,...,Ік =ак), А(е) = 1, где е - пустое слово. Далее будем обозначать w длину слова we {0,1} , а s(w) число единиц в нем. Рассмотрим формальные производящие функции от бесконечного множества не коммутирующих между собой переменных у0,у1,у2,...: a(y)= X A(w)y, (1.8) WE{0,1} a0 (y)= (-1)5W (0H)yw, (1.9) we{0,1} где y = (у0,У1,у2,--), yw = УІУІ УІ при w = 0h10 21..lO k, yе =у0. Теорема 1.1. Для производящих функций a (y) и a0(y) справедливо следующее равенство: a(y) = a(y)a0(y) + a0(y). Из теоремы 1.1 вытекает, что распределение последовательности {1„}=1 полностью определяется последовательностью значений { 4(0И}"=1. Функцию а0[х] = (x) = fiA(0")xa и=0 назовем порождающей производящей функцией последовательности случайных индикаторов. Для вычисления a0 (y) можно использовать произведение Адамара. Т е о р е м а 1.2. Справедливо равенство a0(y) = a0(t) Y/УІ 2=0 1 + ф у і=0 J t=1

Теоремы 1.1 и 1.2 доказаны М.И. Толовиковым в [68]. Рассмотрим некоторые примеры нахождения производящих функций распределения некоторых статистик от серий нулей в последовательности (лл,-,/я). Пример 1.5. Пусть {/}=1 – последовательность случайных индикаторов, распределенных по закону Бернулли, P(7и = 1) = / , P(7и = 0) = д. Найдем производящую функцию a(y) при подстановке yi = х +1у (z = 0,1,...).

Перечисление упорядоченных разбиений компонент вектора на произвольные слагаемые

Меняя местами первые п и последние т строк матрицы Q, получим нижнюю треугольную матрицу, элементы главной диагонали которой равны 1, так что detQ = (-і)"". Следовательно, det Q = det S„.

Аналогично, умножим матрицу Р слева на матрицу Р = (рЛ , которая отличается от Q только (т + и)-й строкой и т-м столбцом: pm+nJ = fj+k_mxj+k m при m-k j m-\, рт+пт = -1, рт+п}= О при остальных значениях ; рш = О при іФт + п. Применяя лемму 2.2, переставляя (т + п)-ю строку и (т + п)-й столбец на первые места и заменяя элементы первой строки на противоположные, из матрицы РР получаем матрицу вида о 1С [к у/ где V - матрица размерности тп, Lm- верхняя треугольная матрица порядка т, элементы главной диагонали которой равны 1, 0 - нулевая матрица размерности пт, R - матрица, указанная в формулировке теоремы. Следовательно, OTI-1 detP = (-ir-1det(PP) = detR, Теорема 2.1 доказана. Выпишем полученный результат в явном виде при п = 3. Получим: для любого целого т 2 и любого целого к т справедлива следующая формула: =Н, (2-2) \-ax-bx 3 \-cx-dx m Q(x) где Р(х) = fkxk + bcfk_2xk+1 +bc2fk_lXk+2 + bd(fm_Jk_2 + fm_Jk_x - 2fm_3fk)xm+k + +bcd(fm_Jk_l - fm_Jk - bfm_Jk_2 +bfm-Jk- m+k+l b2d2 (fmJm.Jk-2 J m-\J m-4J k-\ Jm-2Jk-2 + J m-2J m- J k-\ + J m-2J m- J к Jm-3Jk)X 42 Q(x) = 1-acx-bc3x3 -d(fm + 2bfm_3)xm -bcd(3fm_2-2afm_3)xm+1-bc2d(2fm_1-afm_2+bfm_4)xm+2 + +bd2(2fmfm_3-2fm_Jm_2-bfm_2fm_4 +bf2_3)x2m + f m f m-2 f m-1 2bf m-1m-4 + 2bf m-2 f m-3 +abf m-2 f m-4 abf2-3 Таким образом, автором получен новый прием вычисления произведений Адамара рациональных функций вида 1 хк +bcd2(fmfm_2-f2_1-2bfm_Jm_4+2bfm_2fm_3 +abfm_2fm_4-abf2_3)x2m+1-bmd3x3m. 1-ax- Ьх" 1-cx- dxm где т,п,кєХ (т 2,п 2, 0 к т). Известный ранее алгебраический метод ([81], [67]) вычисления произведений Адамара рациональных функций указанного вида требует вычисления определителей порядка т + п. С помощью методов комбинаторного анализа и линейной алгебры порядок определителей автором снижен на величину т, что расширяет возможности применения произведения Адамара для получения решения конкретных задач в явном виде, поскольку в этом случае порядок определителей от величины т не зависит, он равен произвольному, но фиксированному п. С помощью полученного автором нового приема вычисления произведений Адамара задача перечисления замощений прямоугольника размера 2г плитками размеров 11, 1ти 1п решена автором в общем виде, а для п = 3 формулы получены автором в явном виде.

Перечисление замощений прямоугольника плитками произвольной длины Рассмотрим производящую функцию r=0 1-d1x-d2x -...-dnx" последовательности, задаваемой рекуррентным соотношением fr{d1,d2,...,dn) = dJr_1+d2fr_2+... + dnfr_n (2.3) с начальными условиями /0 = 1 и fr = 0 при г 0. При 4= 1 (; = 1, 2, …,Й) иИ = 2 данная последовательность представляет собой последовательность чисел Фибоначчи. Элемент /Д А...А) может быть интерпретирован как сумма весов замощений прямоугольника размера 1г плитками размеров 11, 12,…, 1п, имеющими соответственно вес d1, d2,…, dn. Под весом замощения понимается произведение весов образующих его плиток. Сумма весов замощений к плитками прямоугольника размера 1г равна коэффициенту при хг в выражении \d,x + d2x2 +... + d х") . у 1 и J

Пример 2.1. При г = 2 прямоугольник размера 12 можно замостить двумя способами, используя для этого плитки размеров 11, 12 и 13 (рисунок 2.1, а). Сумма весов этих замощений определяется равенством: f2(d1,d2,d3) = d12+d2. (2.4) Пример 2.2. При г = 3 прямоугольник размера 13 можно замостить четырьмя способами, используя для этого плитки размеров 11, 12 и 13 (рисунок 2.1, б). Сумма весов этих замощений определяется равенством: /3 (d1,d2,d3) = d13 + 2d1d2 + d3. (2.5) Пример 2.3. При г = 4 прямоугольник размера 14 можно замостить плитками размеров 11, 12 и 13 семью способами (рисунок 2.1, в). Сумма весов этих замощений определяется равенством: /4(d1,d2,d3) = d14 + 3d12d2 + 2d1d3 + d2. (2.6) Пример 2.4. При r = 5 прямоугольник размера 15 можно замостить тринадцатью способами, используя для этого плитки размеров 11, 12 и 13 (рисунок 2.1, г). Сумму весов этих замощений определим с помощью формул (2.3) - (2.6): /5( ) = 4/4(Ш)+ /3Ш)+4/2ЙЛ4)= = d1(d14 +3d12d2 + 2d1d3+d22) + d2(d13 + 2d1d2+d3) + d3(d12 +d2) = = d15 + 4d13d2 + 3d21d3 + 3d1d22 + 2d2d3 (2.7) d1 d1 d2 d1 d1 d1 d1 d2 d2 d1 d3 а) б) d1 d1 d1 d1 d1 d1 d2 d1 d2 d1 d2 d1 d1 d2 d d1 d3 d3 d1 в) d1 d1 d1 d1 d1 d1 d1 d1 d2 d1 d1 d2 d1 d1 d2 d1 d1 d2 d1 d1 d1 d1 d2 d2 d2 d1 d2 d2 d2 d1 d1 d1 d3 d3 d1 d1 d1 d3 d1 d2 d3 d3 d2 r) Рисунок 2.1 - Различные замощения прямоугольника размера 1 хr плитками размеров 1x1, 1х2 и 1x3 а) r = 2; б) r = 3; в) r = 4; г) r = 5 Коэффициент fr(d1,d2,...,dn)fr(b1,b2,...,bm) при хг в произведении = 2 И 2 12 n 12 m Y,fr(d1,d2,..., tn)fr(b1A,...A)xr r=0 может быть интерпретирован как сумма весов замощений прямоугольника размера 2 г плитками размеров 1x1, 1x2,..., \ п в верхнем ряду, а также плитками размеров 1x1, 1x2,..., 1х - в нижнем ряду. Плитка верхнего ряда размера 1х/ имеет вес dt (і = 1, 2,..., ЇЇ). Плитка нижнего ряда размера І / имеет вес bj (j = 1, 2,..., т).

Пример 2.5. На рисунке 2.2 представлено замощение прямоугольника размера 2хг (г = 16) плитками произвольной длины п (пєЩ Вес данного замощения равен b13b2b3d12d2d3d4. 1 d1 1d2 1 d3 ... 1 d„ 2 3 п 2 d3 d1 d1 d2 d4 d2 d3 Ъ1 Ъ1 Ъ2 h h b2 b2 b2 b2 1 г h 1 Ь2 1 и3 ... 1 Ът 2 3 т Рисунок 2.2 – Замощение прямоугольника размера 2r плитками Пример 2.6. При г = 2 прямоугольник размера 2x2 можно замостить четырьмя способами, используя для этого плитки размеров 1x1, 1x2 и 1x3 (рисунок 2.3, а). Сумма весов этих замощений с учетом формулы (2.3) определяется равенством: f2(d1,d2,d3)f2(b1,b2,b3) = (d12 +d2)(b12 +b2) = b12d12 +b12d2 +b2d12+b2d2. Пример 2.7. Прямоугольник размера 2x3 (г = 3) можно замостить шестнадцатью способами, используя для этого плитки размеров 1x1, 1x2 и 1x3 (рисунок 2.3, б). Из формулы (2.5) следует, что сумма весов этих замощений определяется равенством:

Вычисление распределений некоторых статистик от осциллирующего случайного блуждания

Рассмотрим А552 5и =(81,52,...,85+52+ +5) - упорядоченное разбиение числа г на S1 слагаемых, равных 1, s2 слагаемых, равных 2, и т.д., sn слагаемых, равных целому числу п 2, причем s1+2s2+... + nsn = r, где г, st - целые неотрицательные числа (/ = 1, 2, …, п). Слагаемому, равному /, приписывается вес ф. Под весом разбиения понимается произведение весов образующих его слагаемых. Обозначим At1, 2 ={b[,b 2,...,b t 2+ .+/J упорядоченное разбиение числа г на t1 слагаемых, равных 1 и имеющих вес b1, t2 слагаемых, равных 2 и имеющих вес Ь2, и т.д., tm слагаемых с весом Ьт, равных целому числу т 2, причем t1+2t2+... + mtm = г, где tj - целые неотрицательные числа (J = 1, 2, …,т). Рассмотрим производящие функции 1 ,s 2 ,...,s„ 1 , 2 ,.., ш где суммирование ведется по всем определенным выше множествам разбиений. Первая из этих функций равна производящей функции 00 1 Y.fMA,..,d.y = 2 = t0 1-rf1jc-rf2Jt -...-d„x со . k=0 последовательности, задаваемой рекуррентным соотношением fr{d1,d2,...,dn) = dJr-1+d2fr_2+... + dnfr_n с начальными условиями/0 = 1 и/г = 0 при г 0. Элемент fr(d1,d2,...,dn) может быть найден как сумма весов упорядоченных разбиений Д ... . Сумма весов упорядоченных разбиений числа г на к слагаемых равна коэффициенту при хг в выражении (d1x + d2x2+... + dnx")k . Вторая функция равна производящей функции t0 1-l\x-b2x -...-bjc со . к=0 последовательности, задаваемой рекуррентным соотношением fr{KK...A) = bJr-1+b2fr-2+... + bJr-m с теми же начальными условиями. Рассмотрим теперь разбиения вектора (г, г), представляющие собой пары Л = (Д5152 5,A/1/2 /т) определенных выше разбиений числа г. Вес такого разбиения определим как произведение весов разбиений Д .. , \,2,...,,т. Разбиение AS1,S2,...,Sn можно рассматривать как разбиение первой компоненты вектора на слагаемые 1, 2,…, п, а разбиение \Мт - как разбиение второй компоненты вектора на слагаемые 1, 2, …,т. Постановку задачи удобнее всего пояснить посредством конкретных примеров. П р и м е р 2.10. Одно из разбиений вектора (г, г) при г = 7, такое, что первая компонента вектора разбивается на слагаемые 1, 2, 3, а вторая компонента - на слагаемые 1, 2, 3, 4, имеет вид: К7 = (Д21,1, А1 101) = ((1,3,2,1), (4,1,2)).

Указанное выше разбиение имеет вес bfi d12d . На рисунке 2.6, а) приведено соответствующее замощение. d1 d3 d2 d1 b4 h ь2 а) d5 d7 d3 b5 b2 b4 b1 b2 b1 б) Рисунок 2.6 - Замощение прямоугольника размера 2r, соответствующее разбиению а) К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. Одно из разбиений вектора (г, г) при г = 15 с весом b12b2b4b5d3d5d7, такое, что первая компонента вектора разбивается на слагаемые 1, 2, 3, 4, 5, 6, 7, а вторая компонента - на слагаемые 1, 2, 3, 4, 5, имеет вид: \5 = К,0,1,0,1,0,1, \2,0,1,1) = ((5,7,3), (5,2,4,1,2,1)). На рисунке 2.6, б) приведено соответствующее замощение. Пример 2.12. Перечислим все возможные разбиения А вектора (г, г) при г = 5, такие, что первая компонента вектора разбивается на слагаемые 1 и 3, а вторая компонента - на слагаемые 2 и 3: (А5,0,0, V,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)). Сумма весов этих разбиений с учетом формулы (2.7) определяется равенством: /5 ( Д )/5 (62 А) = (d1 + 3d12d3)2b2b3 = 2b2b3d15 + 6b2b3d12d3. На рисунке 2.7 приведены соответствующие замощения. d1 d1 d1 d1 d1 d1 d1 d1 d1 d1 d1 d1 d3 d1 d3 d1 d3 d1 d1 b2 b 3 b 3 b2 b2 b 3 b2 b 3 b2 b d1 d1 d3 d1 d3 d1 d3 d1 d1 b 3 b2 b 3 b 2 b 3 b2 Рисунок 2.7 - Различные замощения прямоугольника размера 25, соответствующие разбиениям Д = ( А 3, \А,3) при + 3 3 = 5 и 2 2 + 3ґ3 = 5 Задача вычисления производящей функции суммы весов разбиений АГ=(Л55 s,\t t ) в общем виде решается с помощью теорем 2.2 и 2.3, сформулированных и доказанных автором.

Таким образом, с помощью полученного автором нового метода вычисления произведения Адамара рациональных функций, выраженного теоремами 2.2 и 2.3, автором в общем виде решена задача вычисления производящей функции суммы весов разбиений A = (A5152 5, А/1/2 /т) компонент двумерного вектора на произвольные слагаемые. Полученный автором новый метод вычисления произведения Адамара рациональных функций позволяет в данной задаче снять ограничения на величину слагаемого и решить известную ранее задачу в новой постановке. 2.5 Применение метода трансфер-матрицы в задаче перечисления замощений прямоугольника плитками по числу типов взаимного расположения плиток

Рассмотрим задачу замощения прямоугольника плитками в динамике. Будем укладывать верхний ряд прямоугольника размера 2r плитками размеров 11, 12,…, 1n, имеющими соответственно вес d1, d2,…, dn, а нижний ряд – плитками размеров 11, 12,…, 1m с весом b1, b2,…, bm соответственно.

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

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

Вероятность замощения прямоугольника плитками

Определим понятие рекуррентного события в соответствии с источником [84]. Рассмотрим последовательность повторяющихся испытаний с возможными исходами Е. (/ = 1, 2,…). Предполагается, что испытания могут продолжаться неограниченно, и вероятности PІЕу ,Еу ,...,Еу\ определяются однозначно для всех конечных наборов. Пусть 8 - некоторое свойство конечных последовательностей: для любого набора (EA,Eh,...,EJn) можно сказать, обладает он свойством 8 или нет. Выражение «S происходит на п-м месте в (конечной или бесконечной) последовательности Е.,Е.,...» понимается как синоним слов «подпоследовательность ЕЛ,ЕЛ,...,Е обладает свойством S». Это означает, что появление 8 при п-м испытании зависит только от исходов первых п испытаний. Подразумевается также, что, говоря о «рекуррентном событии 8», имеем в виду класс событий, определенных условием «8 происходит».

Определение 3.1. Свойство 8 определяет рекуррентное событие, если: 1) для того чтобы 8 происходило на п-м и (п + т)-м местах последовательности (EA,Eh,...,EJnm), необходимо и достаточно, чтобы 8 происходило на последнем месте каждой из двух подпоследовательностей (EA,Eh,...,EJn) и (EJn+i,EJni,...,EJnm); 2) если 8 происходит на п-м месте, то P(EA,Eh,...,EJnm ) = P(EA,Eh,...,EJn )P(EJn+i,EJn+i,...,EJn+m ). Очевидно, что с каждым рекуррентным событием ё связаны две последовательности чисел, определенные для п = 1, 2,… следующим образом: ип = Р {ё происходит при п-м испытании), /п = Р(ё впервые происходит при п-м испытании). Положим /0 = 0, и0 = 1. Введем производящие функции 00 00

Заметим, что {«}=0 не является распределением вероятностей, более того, в типичных случаях _ии = оо. С другой стороны, события «ё впервые происходит при п-м испытании» несовместны, и, следовательно, / = F(1) = /„ 1.

Тогда разность 1- f следует интерпретировать как вероятность того, что ё ни разу не происходит в продолженной до бесконечности последовательности испытаний. Лемма 3.1. Производящие функции последовательностей {и}=0 и {/}0 связаны соотношением U[x) = 1-F(JC) Доказательство леммы 3.1 приведено в [84, с. 325-326]. Рассмотрим формальные производящие функции от бесконечного множества не коммутирующих между собой переменных у0,у1,у2,...\ v(y0,y1,...)= X ри,...,ЛУн...У к (зл) h+h+...+U+k=n Я(У0,У1,..) = пУ 1, (3-2) и=1 где P. . . - вероятность того, что рекуррентное событие 8 произошло в последовательности из п испытаний при испытаниях с номерами i\ + \, /і +/2 + 2,…, і\ + /2 +…+ ik + К а при испытаниях с остальными номерами - не произошло. Справедлива следующая сформулированная и доказанная автором теорема. Теорема 3.1. Для производящих функций V(y0,y1,..) и F , ,...) справедливо следующее равенство: V(y0,y1,...) = V(y0,y1,...)F(y0,y1,...) + F(y0,y1,...). Доказательство. Пусть ;єЕ (/ = 1, 2,…). Функция р:Е {0,1} определяется следующими равенствами: если событие 8 произошло на п-м месте в последовательности из п испытаний; если событие 8 не произошло на п-м месте в последовательности из п испытаний. Пусть {0,1} - полугруппа всех слов над алфавитом {0,1} с операцией конкатенации слов. Функция 4: {0,1} —» R определяется равенствами А(а 1a2...ak) = = a1,(p[Eh) = a2,..; p(EJk) = ак), А(е) = 1, где е - пустое слово. Далее будем обозначать \w\ длину слова we {0,1} , а s(w) -число единиц в нем. Тогда функции (3.1) и (3.2) принимают следующий вид: {0,1} 1 »=1 где w = 0 11021... 10П. Докажем справедливость следующего равенства: A(w)= X А(и1)А0 1і + АІ0 11\. (3.3) Доказательство проводим методом математической индукции по числуs(w). I. База индукции. При s(w) = 1 равенство (3.3) очевидно. П. Индуктивный переход. Пусть равенство (3.3) справедливо для всех слов we{0,1} таких, что 1 s(w) k. Докажем справедливость равенства (3.3) при s(w) = k + 1. Представим слово w такое, что s(w) = k + 1, в виде w = W10m1. Из условия 2) определения 3.1 получаем A(w) = A(w 1)A(0m1). Так как s(V1) = к, то в силу индуктивного предположения имеем A(w) = \ X A(U 1A(0 1) + A(0 1) \А(0т1) = \w 1=u 1v 1 J = X А(и 1)А(0и1 А(0т1) + А(0и1 А(0т1). w 1=u W1 Из условия 2) определения 3.1 находим A(w)= X А(І/10 1)А(0 1) + А(0 10 1). w W1v 1 Так как s( 0 10Г1] = 2, то в силу индуктивного предположения имеем A(w)= X (w 10M1) (0m1) + (0M1) (0m1) + (0H-11). w W1v 1 Отсюда следует A(w)= X A(u1)A{0v1) + A{0 11). w=u1v1

Тогда по теореме индукции равенство (3.3) справедливо для любого натурального числа s(w). Утверждение теоремы непосредственно вытекает из равенства (3.3) и определения операций над формальными степенными рядами. Теорема 3.1 доказана. Справедлива следующая сформулированная и доказанная автором теорема. Теорема 3.2. Пусть z y y . y x". п=\ Тогда справедливо следующее равенство: F(y0,y1,...) = (z0(t,y0,y1,..) F(t))\ (3.4) Д ок аза т ел ьство . Производящая функция (3.2) может быть найдена с помощью произведения Адамара: ЧУо,Уі,-) = \Ц/«УЛ \п=1 л t=\ VVn-l J \п-\ J J t=\ (zo(f o, 1,...) F(0)M, что и требовалось доказать.

Рассмотренный пример показывает преимущества применения произведения Адамара в задачах данного типа по сравнению с комбинаторным методом. При решении задач с применением произведения Адамара для вычисления производящей функции (3.1) не требуется непосредственно вычислять вероятность Р . , что значительно упрощает решение.