Оглавление
Введение 4
1. Разностные уравнения и последовательности Риордана 22
1.1. Задача Коши для многомерного разностного уравнения с постоянными коэффициентами................................... 23
1.2. Обобщение основного рекуррентного соотношения............ 26
1.3. Последовательности Риордана, ассоциированные с парой рядов Лорана................................................. 28
1.4. Описание рациональных последовательностей Риордана как решений двумерных разностных уравнений....................... 30
1.5. Примеры рациональных последовательностей Риордана ... 34
2. О рациональности ^-преобразования решений многомерных разностных уравнений и преобразования Гурвица 37
2.1. Рациональные производящие функции решений задачи Коши для многомерных разностных уравнений...................... 38
2.2. Известные обобщения классической композиции Гурвица двух рядов на многомерный случай..............................46
2.3. Преобразование Гурвица кратных рядов Лорана.............. 48
2.4. Алгебраичность преобразования Гурвица рациональных функций...................................................... 54
3. Асимптотика решений некоторых разностных уравнений 59
3.1. Асимптотика рациональных последовательностей Риордана 60
2
3.2. Асимптотика фундаментальных решений двумерных разностных уравнений специального вида....................... 63
3.3. Разложение на простейшие дроби и асимптотика коэффициентов рациональных функций................................ 67
Заключение 72
Список литературы 73
3
Введение
Теория конечно-разностных уравнений развивалась параллельно с теорией обыкновенных дифференциальных уравнений и в случае линейных уравнений имеет вполне законченный вид. Она нашла широкое применение как в теории дискретных динамических систем, так и в перечислительном комбинаторном анализе.
В многомерном случае ситуация значительно сложнее и сколько-нибудь законченной общей теории конечно-разностных уравнений не создано. Отметим работу Н. Levy, F. Lessman (1959 г.), в которой для двумерного случая рассмотрены способы построения общих решений для некоторых видов разностных уравнений ([36]). В монографии Д. Даджиопа и О. Мер-серо (1988 г.) двумерные разностные уравнения использовались в теории цифровой обработки многомерных сигналов для конструирования цифровых рекурсивных фильтров ([3]). В случае двух переменных задача об устойчивости цифрового рекурсивного фильтра решена в работе А.К. Ци-ха (1991 г.).
В работе М. Bousquet-Melou, М. Petkovsek многомерные разностные уравнения изучались с точки зрения применения к задачам перечислительного комбинаторного анализа. В пей сформулирована, задача Коши для многомерного линейного разностного уравнения и доказана теорема существования и единственности решения этой задачи ([32]).
В работе Е.К. Лейнартаса (2007 г.) приведена формула для решения задачи Коши с использованием понятия фундаментального решения ([10]).
Метод ^-преобразования (метод производящих функций) является мощным средством исследования разностных уравнений как в теории дис-
4
кретных динамических систем, так и в перечислительном комбинаторном анализе. Важный и естественный с точки зрения комбинаторики вопрос, решаемый в работе М. Bousquet-Melou и М. Petkovsek, состоит в том, как 2-преобразование решения разностного уравнения зависит от 2-преобразования начальных данных.
Последовательности Риордана впервые появились в работе L.W. Shapiro, S. Getu, W.-J. Woan, L. Woodson (1991 г.) в связи с изучением групп Риордана и определяются с помощью своего 2-преобразования ([42]). В работах D. Baccherini, D. Merlini, R. Sprugnoli показано, что такими последовательностями г(х,у) описывается число путей на целочисленной решетке ([38]), количество узлов деревьев с помеченными вершинами на некотором уровне («level generating trees», |30|), количество последовательностей Блума длины х, имеющих у изолированных элементов (см. [30], [311). Также последовательность Риордана возникает в задаче о расстановке фигур на шахматной доске, изучавшейся в работах М. Abramson, W. Moser и Г.П. Егорычева ([29], [4]). За последние годы появилось значительное число работ по данной тематике.
В одномерном случае известно, что 2-преобразование последовательности является рациональной функцией тогда и только тогда, когда эта последовательность удовлетворяет разностному уравнению с постоянными коэффициентами. В многомерной ситуации это утверждение, вообще говоря, неверно. С другой стороны, рациональные функции являются простейшим из «наиболее полезных» классов производящих функций, согласно иерархии, предложенной Р. Стенли: {рациональные производящие функции} С {алгебраические производящие функции} С {D-конечные производящие функции} (см. [22, 23, 32)).
Класс D-конечных производящих рядов представляется наиболее естественным с точки зрения перечислительного комбинаторного анализа, потому что, в частности, он замкнут относительно таких операций (преобразований) над кратными рядами, как нахождение сечения ряда и его диагонали, композиции Адамара и композиции Гурвица степенных рядов
(см. работу L. Lipshitz, (37| 1989 г.). Отметим, что вопрос о рациональности (и алгебраичности) z-преобразования для диагональных многомерных последовательной (многомерных аналогов композиции Адамара и Гурвица) рассматривался в работах А.К. Циха, К.В. Сафонова, Е.К. Лейнартаса, М.М. Елина, Т.М. Садыкова ([5, 6, 11, 13, 21]).
Исследование асимптотики решений многомерных разностных уравнений, имеет большое значение не только в комбинаторном анализе, но и в теории обработки многомерных цифровых сигналов, в частности, при исследовании устойчивости цифровых рекурсивных фильтров (|27|). В многомерном случае возникает ряд трудностей принципиального характера, одной из которых считается отсутствие понятия кратного асимптотического ряда. Один из способов исследования асимптотического поведения кратной последовательности /(л), х = (жь... ,жп) 6 Z" - это изучение асимптотики на «диагоналях» х — кр, где р - фиксированная точка из Z”, а к = 0,1,2,....
В работах [16] и [17] методы работы [27] применялись для получения асимптотических оценок коэффициентов Тейлора алгебраических и меро-морфных функций двух переменных. В случае функций с полюсами на объединении конечного числа гиперплоскостей оценки на коэффициенты Тейлора типа «О-большое» впервые приведены для п = 2 в [15), а для п > 2 рассмотрены в [17]. Этот случай представляет большой интерес с точки зрения перечислительного комбинаторного анализа. Например, в задачах о числе решеточных путей и задаче о покрытии костями домино соответствующая производящая функция представляет собой, как показано в работах R. Pernantle, М. Wilson, рациональную функцию двух переменных, знаменатель которой — произведение линейных множителей ([40, 43, 51]). Получившая существенное развитие в работах М. Forsberg, М. Passare и А.К. Циха теория амеб ([33]) была применена в работах Е.К. Лейнартаса, М. Passare и А.К. Циха ([7, 8|) к исследованию асимптотики решений многомерных разностных уравнений с постоянными коэффициентами.
G
- Київ+380960830922