Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Потехина, Елена Алексеевна

• Потехина, Елена Алексеевна
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Потехина, Елена Алексеевна

Оглавление

Введение

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

методы его вычисления

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

некоторых комбинаторных задач

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

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

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

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

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

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

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

некоторых вероятностных задач

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

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

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

Заключение

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

128

Введение диссертации (часть автореферата) на тему «Применение произведения Адамара степенных рядов в комбинаторных и вероятностных задачах»

Введение

х

Произведением Адамара формальных степенных рядов О(х) = ^ ^хк и

к=0

х

Н (х) = ^ Нкхк называется степенной ряд

к=0

х

О ( х )* Н ( х) = Х ёкКхк. к=0

Произведение Адамара степенных рядов находит применение в ряде задач перечислительной комбинаторики и дискретной теории вероятностей. В некоторых из них применение произведения Адамара позволяет найти решение в явном виде.

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

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

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

Исходя из целей работы, ставятся следующие задачи:

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

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

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

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

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

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

задач.

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

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

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

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

1) Автором получен новый комбинаторно-алгебраический метод вычисления произведения Адамара рациональных функций. Известный ранее алгебраический метод ([81], [67]) вычисления произведения Адамара рациональных функций требует вычисления определителей порядка т + п. С помощью методов комбинаторного анализа и линейной алгебры порядок определителей автором снижен до величины шт(т, п), что расширяет возможности применения произведения Адамара для получения решения конкретных задач в явном виде.

2) С помощью полученного автором нового метода вычисления произведения Адамара найдено общее решение задачи перечисления замощений прямоугольника размера 2хг плитками размеров 1x1, 1хт и 1хп, а для п = 3 формулы получены автором в явном виде. Решение этой задачи в частных случаях (при п = 2) с помощью комбинаторных методов ранее опубликовали в своих работах Л. Шапиро [99] и Й.Х. Ким ([95], [96]).

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

4) С помощью полученного автором нового метода вычисления произведения Адамара рациональных функций (теоремы 2.1, 2.2 и 2.3) решена задача перечисления упорядоченных разбиений компонент двумерного вектора на слагаемые (первая компонента разбивается на слагаемые 1 и п, а вторая - на слагаемые 1 и т, где т, п - произвольные целые числа, т > 2, п > 2). Ранее эта задача была решена только в частных случаях при п = 2 [80, с. 367].

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

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

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

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

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

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

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

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

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

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

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

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

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

6) на Международной конференции по алгебре, анализу и геометрии, посвященной юбилеям выдающихся профессоров Казанского университета, математиков Петра Алексеевича (1895 - 1944) и Александра Петровича (1926 -1998) Широковых (Казань, КФУ, 26 июня - 2 июля 2016 г.);

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

8) на XII Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 1 - 8 октября 2011 г.);

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

10) на XIII Всероссийском симпозиуме по прикладной и промышленной математике (весенняя открытая сессия, Петрозаводск, 2 - 9 июня 2012 г.);

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

12) на XIII Всероссийском симпозиуме по прикладной и промышленной математике (осенняя открытая сессия, Сочи-Вардане, 1 - 8 октября 2012 г.);

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

14) на XIV Всероссийском симпозиуме по прикладной и промышленной математике (Великий Новгород, 29 сентября - 5 октября 2013 г.);

15) на XIX межвузовской военно-научной конференции (Череповец, филиал ВКА им. А.Ф. Можайского, 25 - 26 ноября 2010 г.);

16) на Всероссийской научно-практической конференции «Череповецкие научные чтения-2011» (Череповец, ЧГУ, 1 - 2 ноября 2011 г.);

17) на XX межвузовской военно-научной конференции (Череповец, филиал Воен. акад. МО РФ, 11 октября 2012 г.);

18) на Всероссийской научно-практической конференции «Череповецкие научные чтения-2012» (Череповец, ЧГУ, 1 - 2 ноября 2012 г.);

19) на XXXIX военно-научной конференции молодых специалистов (Череповец, филиал ВКА им. А.Ф. Можайского, 11 - 13 мая 2011 г.);

20) на XL военно-научной конференции молодых специалистов (Череповец, филиал Воен. акад. МО РФ, 2 - 4 мая 2012 г.);

21) на 41-й военно-научной конференции молодых специалистов и ученых (Череповец, филиал Воен. акад. МО РФ, 13 - 15 мая 2013 г.);

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

23) на 42-й военно-научной конференции молодых специалистов (Череповец, ЧВВИУРЭ, 13 - 15 мая 2014 г.);

24) на 1-й совместной военно-научной конференции ФГУП «18 ЦНИИ» МО РФ и ЧВВИУРЭ (Череповец, ЧВВИУРЭ, 21 - 22 мая 2015 г.).

Результаты исследования опубликованы в 26 работах ([43] - [68]), из которых [48], [50], [56] и [67] - в рецензируемых журналах, рекомендованных ВАК РФ. В совместной работе [67] автору диссертации принадлежат теоремы 2.1, 3.3 и 3.4 диссертации, а также формула (2.2) диссертации. Кроме того, в совместной работе [68] автору диссертации принадлежат примеры вычисления производящих функций распределений статистик в последовательностях 1-зависимых индикаторов.

Основные результаты и положения, выносимые на защиту:

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

2) Комбинаторно-алгебраическим методом получено общее решение задачи перечисления замощений прямоугольника размера 2хг плитками размеров 1^1, 1хт и 1 хп, а для п = 3 формулы получены в явном виде.

3) Комбинаторно-алгебраическим методом получено общее решение задачи перечисления замощений прямоугольника размера 2хг плитками произвольной длины.

4) Комбинаторно-алгебраическим методом решена задача перечисления упорядоченных разбиений компонент двумерного вектора на слагаемые (первая компонента разбивается на слагаемые 1 и п, а вторая - на слагаемые 1 и т, где т, п - произвольные целые числа, т > 2, п > 2).

5) Комбинаторно-алгебраическим методом решена задача перечисления упорядоченных разбиений компонент двумерного вектора на произвольные слагаемые.

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

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

расположения плиток, а также вычисления производящей функции весов разбиений.

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

Основная часть работы разделена на три главы.

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

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

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

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

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

задачах и методы его вычисления

Произведение Адамара степенных рядов находит применение в ряде комбинаторных и вероятностных задач. Однако, возможности его использования для решения теоретических и прикладных комбинаторных и вероятностных задач изучены недостаточно.

Помимо задач перечислительной комбинаторики и дискретной теории вероятностей в научной литературе можно встретить применения произведения Адамара в задачах комплексного анализа ([1], [16], [37]), линейного программирования [90], математической физики ([88], [102]). В книге [7] Л. Бибербаха изложены глубокие результаты по изучению свойств произведения Адамара (там же приведена обширная библиография). Свойства произведения Адамара исследованы также в работах В.И. Горбайчука и В.И. Кузьмича [12], К.Н. Бояджиева [89]. Привлекают внимание исследователей и свойства произведения Адамара нескольких функций [91]. Результаты исследования многомерного произведения Адамара представлены в работах Л.А. Айзенберга [1], М.М. Елина [16], В.П. Кривоколеско [28], К.В. Сафонова [78].

Хорошо известно, что произведение Адамара разложений в ряд рациональных функций является рациональной функцией ([80, а 308], [34, с. 55]). Как отмечает Р. Стенли [80, а 380], установление точного источника утверждения о рациональности произведения Адамара степенных рядов, заданных рациональными функциями, является трудной задачей. Подобные утверждения для других классов функций, например, удовлетворяющих линейным дифференциальным уравнениям с полиномиальными коэффициентами, рассматриваются в работах А. Гурвица (см. [34, с. 55]) и Р. Стенли [101]. Вопрос о рациональности произведения Адамара рациональных функций нескольких переменных исследовал Е.К. Лейнартас ([35] - [37]). В то же время, явных

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

Таким образом, две основные темы, которые мы хотим затронуть, следующие:

1) комбинаторные и вероятностные задачи, связанные с применением произведения Адамара степенных рядов;

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

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

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

рядов

0 (* ) = Х ёУ

к=0

и

н (* )=Х ь

X

к=0

называется степенной ряд

о (X )* н (X ) = Х ёА

X

к=0

([93, с. 55], [41, с. 85], [42, с. 67]).

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

1

0 ( * = X ё

1 ЧХ V к=0

1.Х

X я

V к=0

кхк

X ёкЯк*к =Х ёк (я*) = 0(я*) .

к=0

к=0

да

да

да

*

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

Произведение Адамара тесно связано с О-оператором П.А. Мак-Магона, введенном им в комбинаторной теории разбиений целых чисел (см. [71, а 84]). Этот оператор для ряда от одной переменной X определяется следующим образом:

X ак ^ = X ак.

к=-ж к=0

Связь О-оператора с произведением Адамара может быть выражена следующим соотношением:

о (* )* н (* ) = а

'1 - !Л

V

о

н (Ах )

Таким образом, вычисление произведения Адамара может быть сведено к вычислению О-оператора. Справедливо и обратное утверждение, иллюстрацией к которому может служить лемма 5 в работе [67]. Вычисление О-оператора представляет интерес в связи с рядом комбинаторных задач, которые могут быть решены с его привлечением. Много таких задач рассмотрено в серии работ Г. Эндрюса с соавторами, подробный список которых приведен в [94]. В этих работах активно используются системы компьютерной алгебры, поскольку объем вычислений слишком велик, чтобы выполнить их вручную.

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

В 2011 году М.И. Толовиковым ([81], [67]) предложен метод, дающий формулы для произведений Адамара рациональных функций в виде отношения

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

Рассмотрим задачу о перечислении замощений прямоугольника плитками. Рассмотрим производящую функцию

да 1 X / ( а, Ь ) =-1--

г=0 1 а* Ь*

последовательности, задаваемой рекуррентным соотношением

/ (а, Ь ) = а/г_ 1 (а, Ь) + Ь/г_т (а,Ь ) (1.1)

с начальными условиями: / = 1 и / = 0 при г < 0. При а = Ь = 1 и т = 2 данная последовательность представляет собой последовательность чисел Фибоначчи. Элемент / (а, Ь) последовательности может быть интерпретирован как сумма

весов замощений прямоугольника размера 1*г плитками размера 1*1 с весом а и плитками размера 1*т с весом Ь. Под весом замощения понимается произведение весов образующих его плиток. Сумма весов замощений к плитками

прямоугольника размера 1*г равна коэффициенту при хг в выражении (а* + Ь*т) .

Например, при г = 3 прямоугольник размера 1*3 можно замостить тремя способами, используя для этого плитки размеров 1*1 и 1*2 (рисунок 1.1, а). Сумма весов этих замощений определяется равенством:

/ (а, Ь ) = а3 + 2 аЬ. (1.2)

При г = 4 прямоугольник размера 1*4 можно замостить плитками размеров 1*1 и 1*2 пятью способами (рисунок 1.1, б). Сумма весов этих замощений определяется равенством:

/ (а, Ь) = а4 + 3а2Ь + Ь2. (1.3)

При r = 5 прямоугольник размера 1*5 можно замостить восьмью способами, используя для этого плитки размеров 1*1 и 1*2 (рисунок 1.1, в). Сумму весов этих замощений определим с помощью формул (1.1) - (1.3):

f (a, b) = afA (a, b) + bf (a, b) = a (a4 + 3a2 b + b2) + b ( a3 + 2ab ) =

= a5 + 4 a3b + 3 ab2.

Аналогичные перечислительные интерпретации для некоторых последовательностей натуральных чисел (например, последовательности {3r}, последовательности Якобсталя {Jr}, последовательности Трибоначчи {Tr}, последовательности Пелля {Pr}) можно найти в работах О.В. Кузьмина и М.В. Серегиной ([32], [33]).

a

a

a

a

b

a

b

a a a a a

a a a a

a a a b

a

b b

a

a

b

а)

a

a

b

б)

a a b a

a

b

b

a

a

b

a b a a

bb

a

bb

b a a a

в)

Рисунок 1.1 - Различные замощения прямоугольника размера 1*г

плитками размеров 1*1 и 1x2 а) г = 3; б) г = 4; в) г = 5

Последовательность Трибоначчи {Тг} = 1, 1, 2, 4, 7, 13, 24, 44, 81, 149,... представляет собой числа различных замощений (полных покрытий)

прямоугольника размера 1*г плитками размеров 1*1, 1*2 и 1*3 [33, с. 92]. Последовательность Трибоначчи задается рекуррентным соотношением

т = т + т + т

1 г 1 г-1 + тг-2 + 1 г -3

с начальными условиями: Т = 1 и Т = 0 при г < 1.

Последовательность Якобсталя = 1, 3, 5, 11, 21, 43, 85, 171, 341, 683,... представляет собой числа различных замощений прямоугольника размера 1*г квадратными плитками размера 1*1 и прямоугольными плитками размера 1*2, имеющими два разных цвета [33, с. 92]. Последовательность Якобсталя задается рекуррентным соотношением

Л = Jr-1 + 2J1

г-2

с начальными условиями: ^ = 1 и ^ = 0 при г < 1.

Последовательность {3Г} = 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,. представляет собой числа различных замощений прямоугольника размера 1*г квадратными плитками размера 1*1, имеющими три разных цвета [33, с. 92].

Последовательность Пелля {Р} = 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378,. представляет собой числа различных замощений прямоугольника размера 1*г квадратными плитками размера 1*1, имеющими два разных цвета, и прямоугольными плитками размера 1*2 [33, с. 93]. Последовательность Пелля задается рекуррентным соотношением

Р = 2Р + Р

1 г 21 г -1 + 1 г-2

с начальными условиями: р = 1 и Р0 = 0.

К задачам о перечислении замощений плитками относится также задача перечисления горизонтально выпуклых полимино [80, с. 375]. Полимино Р - это конечное объединение единичных квадратов на плоскости, вершины которых имеют целые координаты, причем Р связно и связность нельзя нарушить, удаляя конечное число точек. Полимино Р называется горизонтально выпуклым, если каждый горизонтальный ряд квадратов представляет собой нераспадающуюся

полоску. Пусть _Ди) - число горизонтально выпуклых полимино, составленных из и квадратов. Из рисунка 1.2 видно, что /(1) = 1, /(2) = 2, /(3) = 6. Задача вычисления производящей функции

р (* )=£ (п) х

П=1

решена А. Гесселем [80, с. 378] методом трансфер-матрицы с применением произведения Адамара. Вклад в решение данной задачи был внесен также Г. Пойа [98], Д. Кларнером [97] и Р. Стенли [100].

□ Ш

в

Рисунок 1.2 - Горизонтально выпуклые полимино при п = 1, 2, 3

Вернемся к решению задачи о перечислении замощений прямоугольника плитками.

Коэффициент /г ( а, Ь ) /г ( с, ё) при хг в произведении

1 1

* т^тх=£ (аЬ>■ г-(с'ё>

может быть интерпретирован как сумма весов замощений прямоугольника размера 2*г плитками размера 1*1 с весом а и плитками размера 1*т с весом Ь в верхнем ряду, а также плитками размера 1*1 с весом с и плитками размера 1*и с весом й в нижнем ряду. На рисунке 1.3 приведен пример замощения прямоугольника плитками.

Прямоугольник размера 2* г вертикальными линиями разбивается на неприводимые блоки меньшей длины. На рисунке 1.4 приведено разбиение замощения, представленного на рисунке 1.3, на неприводимые блоки.

ь а а ь ь ь

с й й й й й с с с

а 1 ь 10 1 й

т

п

Рисунок 1.3 - Замощение прямоугольника размера 2*г плитками

ь

с й

а а

й

ь ь

й й й

ь

с с с

Рисунок 1.4 - Разбиение замощения на неприводимые блоки

Определим производящую функцию

о

ж (х) = £

т,п \ / / 1

,х)= £ w х

т,п V / / 1 5

5=0

(1.4)

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

о оо 1

£ Л (а, Ь ) /г (с, а ) х" = ]Г(Жт,п (х ))' =—±

г=0 я=0 1 жт

( х )

(1.5)

Формула (1.5) доказана математиками Р. Стенли и А. Гесселем [91].

На рисунке 1.5 приведены неприводимые блоки различной длины для случая т = 2, п = 2.

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

Ж 2 (х) = асх + (Ьа + а 2ё + Ьс2) х2 +

о оо

£ 2аЬ5сй5х 25+1 +£( Ь5с 2й5-х + а2Ь5-хй5)

+

5-1 5 \ 25

х

5=1

5=2

2

г

1

1

1

/ 2\ 2аЬс^ъ (Ьсй + аЬй )

= асх + (Ьй + ай + Ьс Iх +--- + ---

1 ' 1 - Ьйх

1 - Ьйх2

+ (Ьй + а2й + Ьс21х2 + аЬсйх3 - Ь2й2х4 1 - Ьйх2

Отсюда следует формула:

1 1

*-

1 - ах - Ьх2 1 - сх - йх2 1 - Ьйх2

1 - асх - (а2й + Ьс2 + 2Ьй| х2 - аЬсйх3 + Ь2й

2х4

(1.6)

Формула (1.6) при Ь = 1 и d = 1 получена Л. Шапиро [99] в 1981 г. в связи с некоторыми тождествами для ортогональных полиномов Чебышева.

d

а а

d

Ь

с с

а)

б)

Ь Ь ••

с d d

Ь а

• d

а Ь Ь

d d -

• Ь

d с

в)

ЬЬ ••

с d d

а Ь Ь

d d ••

а

г)

Ь

Ь

с

Рисунок 1.5 - Неприводимые блоки (при т = 2, п = 2) а) длины 1; б) длины 2; в) длины + 1 (я > 1); г) длины 28 (я > 2)

Список литературы диссертационного исследования кандидат наук Потехина, Елена Алексеевна, 2016 год

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

1. Айзенберг Л.А., Лейнартас Е.К. Многомерная композиция Адамара и ядра Сеге // Сибирский математический журнал. 1983. Т. 24, №3. С. 3-10.

2. Амелъкин В.А. Перечисление, кодирование и генерирование последовательностей с ограничениями на длины минимальных серий // Сибирский журнал вычислительной математики. 2003. Т. 6, №2. С. 101-111.

3. Афанасьев В.И. Случайные блуждания и ветвящиеся процессы: Лекционные курсы НОЦ. Вып. 6. М.: МИАН, 2007. 188 с.

4. Афанасьева Л.Г., Булинская Е.В. Некоторые асимптотические результаты для случайных блужданий в полосе // Теория вероятностей и ее применения. 1984. Т. 29, вып. 4. С. 654-668.

5. Балагура А.А., Кузьмин О.В. Перечислительные свойства комбинаторных полиномов разбиений // Дискретный анализ и исследование операций. 2011. Т. 18, №1. С. 3-14.

6. Баранский В.А., Королева Т.А. Решетка разбиений натурального числа // Доклады Академии наук. 2008. Т. 418, вып. 4. С. 439-442.

7. Бибербах Л. Аналитическое продолжение: Пер. с нем. М.: Наука, 1967.

240 с.

8. Боровков А.А. Теория вероятностей. М.: Эдуториал УРСС, 1999. 470 с.

9. Боровков А.А., Рузанкин П.С. Переходные явления для случайных блужданий при отсутствии математического ожидания скачков // Сибирский математический журнал. 2009. Т. 50, №5. С. 987-1009.

10. Вершик А.М., Якублович Ю.В. Асимптотика равномерной меры на симплексах, случайные композиции и разбиения // Функциональнй анализ и его приложения. 2003. Т. 37, вып. 4. С. 39-48.

11. Гончаров В.Л. Из области комбинаторики // Известия АН СССР. Серия матем. 1944. Т. 8, №1. С. 3-48.

12. Горбайчук В.И., Кузьмич В.И. О некоторых свойствах адамаровских композиций регулярных в круге функций // Украинский математический журнал. 1975. Т. 27, №1. С. 74-81.

13. Гульден Я., Джексон Д. Перечислительная комбинаторика: Пер. с англ. М.: Наука, 1990. 504 с.

14. Де Вальк В. Процессы со свойством 1-зависимости и их представление в гильбертовом пространстве // Теория вероятностей и ее применения. 1992. Т. 37, №1. С. 149-153.

15. Денисов Д.Э., Фосс С.Г. Об условиях невозвратности для цепей Маркова и случайных блужданий // Сибирский математический журнал. 2003. Т. 44, №1. С. 53-68.

16. Елин М.М. Многомерная композиция Адамара // Сибирский математический журнал. 1994. Т. 35, №5. С. 1052-1057.

17. Жук С.Н. Об онлайн-алгоритмах упаковки прямоугольников в несколько полос // Дискретная математика. 2007. Т. 19, вып. 4. С. 117-131.

18. Захари С., Фосс С.Г. О точной асимптотике максимума случайного блуждания с приращениями из одного класса распределений с тонкими хвостами // Сибирский математический журнал. 2006. Т. 47, №6. С. 1265-1274.

19. Зубков А.М. Оценки для сумм конечно-зависимых индикаторов и для момента первого наступления редкого события // Труды Математического института АН СССР. 1986. Т. 177. С. 33-46.

20. Зубков А.М., Михайлов В.Г. Предельные распределения случайных величин, связанных с длинными повторениями в последовательности независимых испытаний // Теория вероятностей и ее применения. 1974. Т. 19, вып. 1. С. 173-181.

21. Ким Д.К. Асимптотический анализ осциллирующих случайных блужданий с двумя уровнями переключений // Математические труды. 2005. Т. 8, №2. С. 137-167.

22. Ким Д.К., Лотов В.И. Асимптотика стационарного распределения осциллирующего случайного блуждания // Сибирский математический журнал. 2004. Т. 45, №5. С. 1112-1129.

23. Ким Д.К., Лотов В.И. Об осциллирующих случайных блужданиях с двумя уровнями переключений // Математические труды. 2003. Т. 6, №1. С. 34-74.

24. Коганов Л.М. О числе пар независимых разбиений конечного множества // Комбинаторный и асимптотический анализ. Красноярск: Изд-во Красноярского ун-та, 1975. С. 71-80.

25. Коганов Л.М. Об одном ориентированном графе, связанном с упорядоченной парой упорядоченных разбиений // Математические заметки. 1987. Т. 41, №1. С. 101-103.

26. Коршунов А.Д. Об асимптотике числа бинарных слов с заданной длиной максимальной серии // Дискретный анализ и исследование операций. 1997. Т. 4, №4. С. 13-46.

27. Косточка А.В., Мазуров В.Д., Савельев Л.Я. Число д-ичных слов с ограничениями на длину максимальной серии // Дискретная математика. 1998. Т. 10, вып. 1. С. 10-19.

28. Кривоколеско В.П., Лейнартас Е.К. О тождествах с полиномиальными коэффициентами // Известия Иркутского государственного университета. Сер. Математика. 2012. Т. 5, №3. С. 56-62.

29. Кузьмин О.В. Рекуррентные соотношения и перечислительные интерпретации некоторых комбинаторных чисел и полиномов // Дискретная математика. 1994. Т. 6, вып. 3. С. 39-49.

30. Кузьмин О.В., Леонова О.В. О полиномах разбиений // Дискретная математика. 2001. Т. 13, вып. 2. С. 144-158.

31. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения // Дискретная математика. 2000. Т. 12, вып. 3. С. 60-71.

32. Кузьмин О.В., Серегина М.В. Верхние отсечения обобщенной пирамиды Паскаля и их интерпретации // Журнал Сибирского федерального университета. Сер. Математика и физика. 2010. Т. 3, вып. 4. С. 533-543.

33. Кузьмин О.В., Серегина М.В. Плоские сечения обобщенной пирамиды Паскаля и их интерпретации // Дискретная математика. 2010. Т. 22, вып. 3. С. 83-93.

34. Ландо С.К. Лекции о производящих функциях. М.: МЦНМО, 2007.

144 с.

35. Лейнартас Е.К. Интегральные методы в многомерной теории степенных рядов и разностных уравнений: автореф. дис. ... д-ра физ.-мат. наук: 01.01.01. Красноярск, 2006. 32 с.

36. Лейнартас Е.К. Когомологии рациональных форм и многомерные аналоги композиции Адамара: автореф. дис. ... канд. физ.-мат. наук: 01.01.01. Свердловск, 1982. 14 с.

37. Лейнартас Е.К. Об одном обобщении произведения Адамара в Сп // Математические заметки. 1982. Т. 32, №4. С. 477-482.

38. Лотов В.И. О времени пребывания случайного блуждания в полосе // Сибирский математический журнал. 2010. Т. 51, №4. С. 785-804.

39. Лотов В.И. Об осциллирующих случайных блужданиях // Сибирский математический журнал. 1996. Т. 37, №4. С. 869-880.

40. Лотов В.И., Орлова Н.Г. О числе пересечений полосы траекториями случайного блуждания // Математический сборник. 2003. Т. 194, №6. С. 135-146.

41. Мазья В.Г., Шапошникова Т.О. Жак Адамар легенда математики. М.: МЦНМО, 2008. 526 с.

42. Полищук Е.М. Жак Адамар, 1865 - 1963. Л.: Наука, 1990. 252 с.

43. Потехина Е.А. Вычисление распределений некоторых статистик от серий рекуррентных событий // Материалы 42-й военно-научной конференции молодых специалистов (13 - 15 мая 2014 г.). Ч. 2. Череповец: ЧВВИУРЭ, 2015. С. 33-36.

44. Потехина Е.А. Комбинаторное решение задачи перечисления замощений прямоугольника плитками // Информатизация процессов формирования открытых систем на основе САПР, АСНИ, СУБД и систем

искусственного интеллекта: Материалы 7-й Международной научно-технической конференции (28 июня 2013 г.). Вологда: ВоГТУ, 2013. С. 154-158.

45. Потехина Е.А. Осциллирующая последовательность в задаче вычисления производящей функции весов разбиений // Материалы XX межвузовской военно-научной конференции (11 октября 2012 г.). Ч. 4. Череповец: Филиал Воен. акад. МО РФ, 2013. С. 38-42.

46. Потехина Е.А. Осциллирующая последовательность в задаче перечисления упорядоченных разбиений // Обозрение прикладной и промышленной математики. 2012. Т. 19, вып. 5. С. 739-741.

47. Потехина Е.А. Осциллирующее случайное блуждание в задаче вычисления производящей функции весов разбиений // Материалы 41 -й военно-научной конференции молодых специалистов и ученых (13 - 15 мая 2013 г.). Ч. 3. Череповец: Филиал Воен. акад. МО РФ, 2013. С. 33-36.

48. Потехина Е.А. Осциллирующее случайное блуждание в задаче перечисления упорядоченных разбиений // Наукоемкие технологии. 2013. Т. 14, № 8. С. 72-79.

49. Потехина Е.А. Приложение комбинаторно-алгебраического метода вычисления произведения Адамара к одной из комбинаторно-вероятностных задач // Материалы Международной конференции по алгебре, анализу и геометрии (26 июня - 2 июля 2016 г.). Казань: КФУ, 2016. С. 275-276.

50. Потехина Е.А. Приложение произведения Адамара к некоторым комбинаторным и вероятностным задачам // Дискретная математика. 2016. Т. 28, вып. 1. С. 101-112.

51. Потехина Е.А. Приложение произведения Адамара к одной из комбинаторно-вероятностных задач // Материалы 1 -й совместной военно-научной конференции ФГУП «18 ЦНИИ» МО РФ и ЧВВИУРЭ (21 - 22 мая 2015 г.). Ч. 3. Череповец: ЧВВИУРЭ, 2015. С. 117-118.

52. Потехина Е.А. Применение метода трансфер-матрицы в задаче перечисления замощений прямоугольника плитками // Череповецкие научные чтения - 2012: Материалы Всероссийской научно-практической конференции

(1 - 2 ноября 2012 г.): В 3 ч. Ч. 3: Естественные, экономические, технические науки и математика. Череповец: ЧГУ, 2013. С. 226-229.

53. Потехина Е.А. Применение произведения Адамара в задаче вычисления производящей функции весов разбиений // Материалы XL военно -научной конференции молодых специалистов (2 - 4 мая 2012 г.). Ч. 2. Череповец: Филиал Воен. акад. МО РФ, 2013. С. 58-60.

54. Потехина Е.А. Применение произведения Адамара в задаче перечисления упорядоченных разбиений компонент вектора на фиксированные слагаемые // Обозрение прикладной и промышленной математики. 2011. Т. 18, вып. 5. С. 798-799.

55. Потехина Е.А. Применение произведения Адамара в задаче перечисления замощений прямоугольника плитками // Череповецкие научные чтения - 2011: Материалы Всероссийской научно-практической конференции (1 - 2 ноября 2011 г.): В 3 ч. Ч. 3: Естественные, экономические, технические науки и математика. Череповец: ЧГУ, 2012. С. 172-175.

56. Потехина Е.А. Применение произведения Адамара в задаче перечисления упорядоченных разбиений // Наукоемкие технологии. 2012. Т. 13, № 8. С. 58-65.

57. Потехина Е.А. Применение произведения Адамара в задаче перечисления упорядоченных разбиений компонент вектора на произвольные слагаемые // Обозрение прикладной и промышленной математики. 2012. Т. 19, вып. 3. С. 461-463.

58. Потехина Е.А. Применение произведения Адамара в задаче распределения ресурсов вычислительной сети // Процессы управления и устойчивость. 2016. Т. 3 (19), № 1. С. 463-471.

59. Потехина Е.А. Применение произведения Адамара в одной из комбинаторно-вероятностных задач // Вероятностные методы в дискретной математике: Материалы IX Международной Петрозаводской конференции (30 мая - 3 июня 2016 г.) / Ин-т прикладных мат. исследований Карел. науч. центра РАН. Петрозаводск: ПетрГУ, 2016. С. 78-80.

60. Потехина Е.А. Применение произведения Адамара для вычисления производящих функций некоторых статистик от серий рекуррентных событий // Череповецкие научные чтения - 2013: Материалы Всероссийской научно-практической конференции (6 - 7 ноября 2013 г.): В 4 ч. Ч. 3: Естественные, экономические, технические науки и математика. Череповец: ЧГУ, 2014. С. 200-202.

61. Потехина Е.А. Применение произведения Адамара к исследованию распределения статистик в последовательностях 1-зависимых индикаторов // Материалы XXXIX военно-научной конференции молодых специалистов (11 - 12 мая 2011 г.). Ч. II. Череповец: Филиал Воен. акад. МО РФ, 2011. С. 24-27.

62. Потехина Е.А. Применение произведения Адамара к решению одной из комбинаторных задач // Сборник научных трудов. Вып. 5, ч. 1. Череповец: Филиал Воен. акад. МО РФ, 2012. С. 19-28.

63. Потехина Е.А. Применение произведения Адамара степенных рядов для вычисления распределений некоторых статистик от осциллирующего случайного блуждания // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта: Материалы 6-й Международной научно-технической конференции (24 - 25 июня 2011 г.). Вологда: ВоГТУ, 2011. С. 157-161.

64. Потехина Е.А. Произведение Адамара в задаче перечисления замощений прямоугольника плитками // Ломоносов: Материалы XX Международной молодежной научной конференции студентов, аспирантов и молодых ученых (9 - 12 апреля 2013 г.). [Электронный ресурс] М.: МАКС Пресс, 2013. 1 электрон. опт. диск (DVD-ROM).

65. Потехина Е.А. Производящие функции некоторых статистик от серий в последовательностях 1 -зависимых индикаторов // Материалы XIX межвузовской военно-научной конференции (24 - 25 ноября 2010 г.). Ч. II. Череповец: Филиал ВКА имени А.Ф. Можайского, 2011. С. 91-95.

66. Потехина Е.А. Производящие функции некоторых статистик от серий рекуррентных событий // Математика в современном мире: Материалы

Международной научно-практической конференции, посвященной 150-летию Д.А. Граве (7 - 10 октября 2013 г.). Вологда: ВГПУ, 2013. С. 58-61.

67. Потехина Е.А., Толовиков М.И. Осциллирующее случайное блуждание и произведение Адамара рациональных функций // Дискретная математика. 2013. Т. 25, вып. 3. С. 96-115.

68. Потехина Е.А., Толовиков М.И. Распределение серий в последовательностях 1 -зависимых индикаторов // Череповецкие научные чтения -2010: Материалы Всероссийской научно-практической конференции (2 - 3 ноября 2010 г.): В 3 ч. Ч. 3: Технические, естественные и экономические науки. Череповец: ЧГУ, 2011. С. 136-139.

69. Риордан Дж. Введение в комбинаторный анализ: Пер. с англ. М.: ИЛ, 1963. 288 с.

70. Рогозин Б.А., Фосс С.Г. Возвратность осциллирующего случайного блуждания // Теория вероятностей и ее применения. 1984. Т. 29, вып. 1. С. 161-168.

71. Рыбников К.А. Комбинаторный анализ. Очерки истории. М.: Изд-во Механико-математического факультета МГУ, 1996. 125 с.

72. Савельев Л.Я. Длинные серии в марковских последовательностях // Предельные теоремы теории вероятностей. Новосибирск: Наука, 1985. С. 137-144.

73. Савельев Л.Я. Максимум длин серий в обобщенных последовательностях Бернулли // Дискретная математика. 1999. Т. 11, вып. 1. С. 29-52.

74. Савельев Л.Я. Серии в марковских последовательностях // Сибирский математический журнал. 1991. Т. 32, № 4. С. 116-132.

75. Савельев Л.Я., Балакин С.В. Некоторые применения стохастической теории серий // Сибирский журнал индустриальной математики. 2012. Т. 15, №3(51). С. 111-123.

76. Савельев Л.Я., Балакин С.В. Совместное распределение числа единиц и числа 1 -серий в двоичных марковских последовательностях // Дискретная математика. 2004. Т. 16, вып. 3. С. 43-62.

77. Савельев Л.Я., Балакин С.В., Хромов Б.В. Накрывающие серии в двоичных марковских последовательностях // Дискретная математика. 2003. Т. 15, вып. 1. С. 50-76.

78. Сафонов К.В. Об условиях алгебраичности и композиции Адамара кратных степенных рядов: автореф. дис. ... канд. физ.-мат. наук: 01.01.01. Свердловск, 1986. 16 с.

79. Старовойт А.А. Группа автоморфизмов решетки разбиений натуральных чисел // Известия Иркутского государственного университета. Сер. Математика. 2012. Т. 5, №2. С. 55-60.

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

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

82. Толовиков М.И. Однородные цепи Маркова с двумя состояниями и суммы независимых случайных индикаторов // Вестник ЧГУ. 2004. №2(7). С. 134-136.

83. Фалин Г.И. Монотонность случайных блужданий по частично упорядоченным множествам // Успехи математических наук. 1988. Т. 43, вып. 2(260). С. 155-156.

84. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т. 1: Пер. с англ. М.: Мир, 1984. 528 с.

85. Ширяев А.Н. Вероятность: В 2-х кн. Кн. 1. М.: МЦНМО, 2011. 552 с.

86. Эйлер Л. Введение в анализ бесконечных. В 2-х томах. Т. 1: Пер. с лат. М.: ФИЗМАТЛИТ, 1961. 315 с.

87. Эндрюс Г.Е. Теория разбиений: Пер. с англ. М.: Наука, 1982. 256 с.

88. Bostan A., Boukraa S., Christol G., Hassani S., Maillard J-M. Ising n-fold intégrais as diagonals of rational functions and integrality of series expansions // Journal Of Physics A: Mathematical And Theoretical. 2013. V. 46, num. 18, 185201.

89. Boyadzhiev K.N. Series transformation formulas of Euler type , Hadamard product of series, and harmonic number identities //Indian J. Pure Appl. Math. 2011 V. 42, num. 5. P. 371-386.

90. De Loera J.A., Haws D., Hemmecke R., Yoshida R. A computational study of integer programming algorithms based on Barvinok's rational functions // Discrete Optimization. 2005. V. 2, num. 2. P. 135-144.

91. El-Ashwah R.M., Aouf M.K. The Hadamard product of meromorphic univalent functions defined by using convolution // Applied Mathematics Letters. 2011. V. 24. P. 2153-2157.

92. Gessel I.M., Stanley R.P. Algebraic enumeration // Handbook of Combinatorics, Vol. 2, ed. R.L. Graham, M. Grotschel, and L. Lovasz. Elsevier and MIT Press, 1995. P. 1021-1062.

93. Hadamard J. Théorème sur les séries entières // Acta Math. 1899. V. 22. P. 55-63.

94. Han G.-N. A general algorithm for the MacMahon omega operator // Annals of Combinatorics. 2003. V. 7, num. 4. P. 467-480.

95. Kim J.H. Hadamard Products and Tilings. // Journal of Integer Sequences. 2009. Vol. 12. Article 09.7.4. P. 3-16.

96. 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.

97. Klarner D.A. A combinatorial formula involving the Fredholm integral equation // J. Combinatorial Theory. 1968. V. 5. P. 59-74.

98. Polya G. On the number of certain lattice polygons // J. Combinatorial Theory. 1969. V. 6. P. 102-105.

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

100. Stanley R.P. Generating functions, in Studies in combinatorics (G.-C. Rota, ed.). Math. Assoc. of America, Washington, D.C. 1978. P. 100-141.

101. Stanley R.P. Differentiably finite power series // Europ. J. Combinatorics. 1980. V. 1. P. 175-178.

102. Zhilinskii B. Generating functions for effective Hamiltonians via the symmetrized Hadamard product // Journal Of Physics A: Mathematical And Theoretical. 2008. V. 41, num. 38, 382004.