Файл: Учебное пособие ульяновск 2018 msc2010 05 Combinatorics ббк 22. 176 Удк 519. 1 В313 Рецензенты.pdf

126
Доказательство. Рассмотрим λ
1
, . . . , λ
n
– все комплекс- ные собственные значения оператора ϕ . Они ненулевые и являются корнями из 1. Если среди них встречаются вещест- венные числа, то это – циклически финитные ±1, добавляю- щие в баланс циклов ровно по 1. Невещественные собствен- ные значения циклически нефинитны и встречаются сопря- ж¨
енными парами λ и λ , где λ · λ
= 1. Используя прежние вычисления, сочт¨
ем вклад такой пары в баланс циклов:
2λ
λ − 1
+
2λ
λ − 1
= 2 ·
λ · λ − λ + λ · λ − λ
λ · λ − λ − λ + 1
= 2 ,
что и доказывает лемму 8.26.
8.27. Замечание. Совмещение обобщ¨енного циклового раз- ложения с теорией Пойа требует построения экспоненциаль- ного функтора (U, V ) 7→ U
V
с ожидаемыми свойствами:
U
V
⊗ U
W
' U
V ⊕ W
; (U
V
)
W
' U
V ⊗ W
; (U ⊗V )
W
' U
W
⊗ V
W
;
V
k
' V ; V
0
' k ; k
V
' k ; 0
V
' 0 , V 6= 0 .
Частными значениями такого функтора служат симметри- ческая и внешняя (грассманова) степени S и Λ:
S(V ) ' S(k)
V
, Λ(V ) ' Λ(k)
V
Но эта тема заслуживает отдельного изучения.

Литература
[1] Bogdanchuk O.A., Mishchenko S.P., Ver¨
evkin A.B. On Lie algebras with exponential growth of the codimensions // Ser- dica Math. J., v. 40, n. 3-4, 2014, p. 209-240.
[2] Вер¨
евкин А.Б. О порождающих подалгебры Веронезе //
Уч¨
еные записки УлГУ, Фундаментальные проблемы ма- тематики и механики, 1996, вып. 2, с. 15-16.
[3] Вер¨
евкин А.Б. Фрагмент инвариантной комбинатори- ки // Тезисы XIII Междунар. конфер.
”
Проблемы теоре- тической Кибернетики“, 27-31 мая 2002 г., Казань, с. 34.
[4] Вер¨
евкин А.Б. О положительных эйлеровых произведе- ниях // Материалы VIII междунар. семинара
”
Дискрет- ная математика и е¨
е приложения“, 2-6 февраля 2004 г.–
М.: Изд. мех-мата МГУ, 2004, с. 175.
[5] Вер¨
евкин А.Б. О производящей функции представле- ний // Материалы IX Междунар. семинара
”
Дискретная математика и е¨
е приложения“, посв. 75-летию академика
О.Б. Лупанова, 18-23 июня 2007 г.– М.: Изд. мех-мата
МГУ, 2007, с. 209.
[6] Вер¨
евкин А.Б. О почти тождественных функциях //
Материалы междунар. конференции по алгебре, анализу
127

128
ЛИТЕРАТУРА
и геометрии, посв. юбилеям П.А. и А.П. Широковых.– К.:
Казанский университет, изд. АН РТ, 2016, с. 126-127.
[7] Вер¨
евкин А.Б., Мищенко С.П. О многообразиях с тож- дествами однопорожд¨
енной свободной метабелевой ал- гебры // Чебышевский сборник, 2016, т. 17, в. 2, с. 21-55.
[8] Власов Н.А. Некоторые задачи комбинаторики.– Ул.:
УлГУ, 2002, 45 с.
[9] Воробь¨
ев Н.Н. Теория рядов.– М.: Наука, 1975, 368 с.
[10] Грэхем Р., Кнут Д., Паташник О. Конкретная матема- тика. Основание информатики.– М.: Мир, 1998, 703 с.
[11] Гульден Я., Джексон Д. Перечислительная комбинато- рика.– М.: Наука, 1990, 504 с.
[12] Комбинаторный анализ. Задачи и упражнения: Уч. по- собие / Под ред. К.А. Рыбникова.– М.: Наука, 1982, 368 с.
[13] Кнут Д.Э. Искусство программирования, т. 4, А. Ком- бин. алгоритмы, ч. 1.– М.: ИД Вильямс, 2013, 960 с.
[14] Ландо С.К. Лекции о производящих функциях. 2-е изд.–
М.: МЦНМО, 2004, 144 с.
[15] Липский В. Комбинаторика для программистов.– М.:
Мир, 1988, 200 с.
[16] Nowicki A. Silnie i symbole Newtona.– Olsztyn, Toru´
n, 2012,
196 p.

ЛИТЕРАТУРА
129
[17] Ожигова Е.П. Об истоках символических и комбинатор- ных методов в конце XVIII – начале XIX в. / Историко- математические исследования, вып. XXIV.– М.: Наука,
1979, с. 121-157.
[18] Перечислительные задачи комбинаторного анализа. Сб.
переводов статей под ред. Г.П. Гаврилова.– Библиотека
Кибернетического сборника.– М.: Мир, 1979, 363 с.
[19] Полиа Г., Сег¨
е Г. Задачи и теоремы из анализа. Части
I, II.– М.: Наука, 1978, 392+432 с.
[20] Прикладная комбинаторная математика. Сб. статей под ред. Э. Беккенбаха.– М.: Мир, 1968, 364 с.
[21] Прудников А.П., Брычков Ю.А., Маричев О.И. Интег- ралы и ряды. Элемент. функции.– М.: Наука, 1981, 800 с.
[22] Риордан Дж. Введение в комбинаторный анализ.– М.:
ИЛ, 1963, 287 с.
[23] Риордан Дж. Комбинаторные тождества.– М.: Наука,
1982, 255 с.
[24] Roman S. The Umbral Calculus.– Acad. Press, 1984, 193 p.
[25] Рыбников К.А. Комбинаторный анализ. Очерки исто- рии. Уч. пособие.– М.: Изд-во Мех-мата МГУ, 1996, 125 с.
[26] Рыбников К.А. Введение в комбинаторный анализ. 2-е изд.– М.: Изд-во Московского университета, 1985, 308 с.
[27] Саломаа А. Жемчужины теории формальных языков.–
М.: Мир, 1986, 159 с.

130
ЛИТЕРАТУРА
[28] Сачков В.Н. Введение в комбинаторные методы дис- кретной математики.– М.: Наука, 1982, 384 с.
[29] Sloane N.J.A. A Handbook of Integer Sequences.– Academic
Press, 1973, 206 p.
[30] Смагин А.А. Модели разбиений.– Ул.: УлГУ, 2013, 207 с.
[31] Стенли Р. Перечислительная комбинаторика, т. 1.– М.:
Мир, 1990, 440 с.
[32] Стенли Р. Перечислительная комбинаторика. Деревья,
производящие функции и симметрические функции,
т. 2.– М.: Мир, 2009, 767 с.
[33] Уфнаровский В.А. Комбинаторные и асимптотические методы в алгебре / Итоги науки и техники. Современные проблемы математики. Фундаментальные направления,
т. 57.– М.: ВИНИТИ, 1990, с. 5-177.
[34] Харари Ф. Теория графов.– М.: Мир, 1973, 300 с.
[35] Хартсхорн Р. Алгебраическая геометрия.– М.: Мир, 1981,
600 с.
[36] Холл М. Комбинаторный анализ.– М.: ИЛ, 1963, 97 с.
[37] Эндрюс Г. Теория разбиений.– М.: Наука, 1982, 256 с.
[38] Якобс К. Машинно-порожд¨
енные 0-1-последовательнос- ти/ сб. Машины Тьюринга и рекурсивные функции.– М.:
Мир, 1972, 264 с.

ОГЛАВЛЕНИЕ
1. ЧТО ТАКОЕ КОМБИНАТОРИКА? .......................................... 1 2. ПРОИЗВОДЯЩИЕ ФУНКЦИИИ............................................. 9 3. БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ................................. 16 4. ПОЧТИ ТОЖДЕСТВЕННЫЕ ФУНКЦИИ .............................. 38 5. КОНЕЧНЫЕ РАЗНОСТИ...................................................... 54 6. ЧИСЛА КАТАЛАНА .............................................................. 74 7. ДВОИЧНОЕ РАЗЛОЖЕНИЕ ................................................ 86 8. АЛГЕБРАИЧЕСКАЯ КОМБИНАТОРИКА ............................ 103
ЛИТЕРАТУРА ..................................................................... 127

Научное издание
Верёвкин Андрей Борисович
Кандидат физико-математических наук, доцент кафедры прикладной математики
Ульяновского государственного университета
КОМБИНАТОРИКА
Учебное пособие
В авторской редакции
Издатель
Качалин Александр Васильевич
432042, Ульяновск, ул. Рябикова, 4.
Подписано в печать 20.02.2018.
Формат 60х84 1/16. Бумага офсетная.
Печать ризографическая.
Текст набран в LaTeX2ε.
Усл.печ.л. 7,71. Заказ № 18/015
Тираж 100 экз.
Отпечатано в издательско-полиграфическом центре «Гарт» ИП Качалин А.В.
432042, Ульяновск, ул. Рябикова, 4.