Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/f00/notes/comb01.ps Дата изменения: Thu Jan 23 16:43:45 2003 Дата индексирования: Sat Dec 22 19:17:35 2007 Кодировка: Windows-1251 Поисковые слова: http astrokuban.info astrokuban

С.В.Дужин
КОМБИНАТОРИКА
Лекция 1
1. Вступительные замечания: перечислительная комбинаторика, структурная ком-
бинаторика, перечисление комбинаторных структур.
2. Числа Фибоначчи. Определение. Последовательность Фибоначчи определяется
рекуррентным соотношением F n = F n 1 + F n 2 и начальными условиями F 0 = 0,
F 1 = 1.
3. Вывод формулы для чисел Фибоначчи при помощи линейной алгебры.
4. Теорема о решении линейных рекуррентных соотношений с постоянными коэф-
фициентами.
5. Вывод формулы для чисел Фибоначчи при помощи производящих функций.
6. Алгебра формальных степенных рядов. Умножение на число, сложение, умно-
жение. Композиция.
7. Числа Каталана C n . Определение.
1 Ж . Число способов расстановки скобок в произведении n букв.
2 Ж . Число правильных скобочных структур из n 1 пар скобок.
3 Ж . Число последовательностей fa 1 ; a 2 ; :::; a 2n 1 g с такими свойствами: a i > 0, a 1 =
a 2n 1 = 0, ja i a i+1 j = 1 для всех i.
4 Ж . Число триангуляций n + 1-угольника.
5 Ж . Число посаженных плоских деревьев с n ребрами.
6 Ж . Число посаженных плоских бинарных деревьев с n листьями.
7 Ж . Число хордовых диаграмм, состоящих из n 1 непересекающихся хорд.
Домашнее задание
Упражнение 1. Решить рекуррентное соотношение F n = 3F n 2 2F n 3 с началь-
ными условиями F 0 = 3, F 1 = 1, F 2 = 8.
Упражнение 2. Проверьте, что формальные степенные ряды для e t 1 и ln(1 + t)
взаимно обратны в смысле композиции.
Упражнение 3. Докажите эквивалентность приведенных выше определений чисел
Каталана.
Упражнение 4. а) Докажите рекуррентное соотношение для чисел Каталана
C n =
n 1
X
k=1
C k C n k :
б) Переформулируйте это рекуррентное соотношение как уравнение на производя-
щую функцию C(t) =
P 1
n=0
C n t n .
в) Найдите функцию C(t) в явном виде.
г) Найдите явное выражение для C(n) через биномиальные коэффициенты.
д) Докажите следующее соотношение
C(x) =
x
1
x
1
x
1 : : :
;
предварительно придав ему смысл.