Course: К.И. Пименов 'Алгебраическая перечислительная комбинаторика"

Forums

Enrol me in this course

	Новостной форум Forum К.И. Пименов 'Алгебраическая перечислительная комбинаторика" (От species к теории представлений симметрической группы). Первая лекция: 03.10.09 в 9-15 в ауд. 33 на 14 линии д.29. Курс построен вокруг двух точек зрения на некоторый набор красивых комбинаторных формул. Первый сюжет, которому будет посвящено три-четыре занятия, называется "Umbral calculus", он объясняет единым образом некоторые соотношения для классических полиномиальных последовательностей. Например, интерполяционная формула Ньютона из исчисления конечных разностей $p(X)=\sum \frac {\Delta^kp(0)}{k!}X(X-1)\dots (X-k+1)$ , оказывается прямым аналогом формулы Тейлора в некотором вполне строгом смысле, связанном с переходом от стандартного мономиального базиса в пространстве многочленов к базису состоящему из многочленов $\varphi_n(X)=X(X-1)\dots (X-n+1).$ Биномиальная формула для этих многочленов $\varphi_n(X+Y)=\sum{\rm C}_n^k \varphi_k(X) \varphi_{n-k}(Y)$ также легко объясняется без единой выкладки. Хорошей иллюстрацией послужат и несколько классических соотношений между числами Стирлинга обоих родов и числами Бернулии. Философский смысл "исчисления теней" опирается на наличие естественной структуры коалгебры на кольце многочленов (коумножение задается биномом Ньютона). Поэтому такая седая классика, как исчисление конечных разностей, оказывается провозвестником такой модной в последние десятилетия темы, как комбинаторные алгебры Хопфа, антипод одной из которых использован для ренормализации по Креймеру. Впрочем вдаваться во всю эту высокую науку мы не будем. Второй, основной сюжет, посвящен комбинаторным видам или типам структур --- таким, как графы, деревья, упорядочения, разбиения на несколько частей, и задаче перечисления таких структур. В 1980 году A. Joyal предложил простое абстрактное понятие комбинаторного вида --- specie, конкретными примерами которых являляются понятия дерева и т.п. Благодаря чему многие принципы перечислительной комбинаторики оказалось вомодным сформулировать в виде теорем. Приведем два примера применения так называемого экспоненциального принципа. Первый: пусть $A(t)=\sum a_n\frac {t^n}{n!}$ --- производящая функция для числа деревьев с n вершинами. Тогда $exp(A(t))$ --- это производящая функция для числа лесов (не обязательно связных графов без циклов). Второй пример: $e^t-1=\sum 1\cdot\frac {t^n}{n!},\quad n\geqslant 1,$ --- это производящая функция для числа непустых множеств из n элементов (по одному множеству для каждого n); тогда $exp(e^t-1)$ --- это производящая функция для чисел разбиений n элементных множеств на несколько непустых частей. Легко увидеть, что рассуждения, доказывающие оба факта, идентичны, поэтому хочется сформулировать общую теорему, иллюстрацией которой эти факты служат: "производящая функция для числа несвязных структур равна экспоненте производящей функции от числа связных структур". Благодаря Joyal'ю это утверждение сменило статус расплывчатого принципа на статус несложной теоремы. Теорема перечисления Пойа про цикловой индекс действия группы на множестве оказывается составной частью теории species. Другой ключевой ингредиент --- полиномиальные функторы, по существу изобретенные И. Шуром еще в начале двадцатого века в связи с двойственностью Шура-Вейля между представлениями симметрических групп и полных линейных групп. Поэтому не случайно, что познакомившись поближе species, мы с минимальными услиями освоим базовые формулы из теории представлений симметрической группы. Например, тот факт, что характеры неприводимых представлений --- это функции Шура, получится автоматически, практически без вычислений. С примерной программой курса можно ознакомиться по адресу www.math.spbu.ru/VAlgebra/SPECIES/exam211.pdf Пререквизиты к этому курсу минимальны. Требуется понимать про действие группы на множестве, про переход от базиса к базису. К моменту начала разговора про species хорошо бы ознакомиться с определением функтора и естественного преобразования на парочке примеров. Впрочем, никакая машинерия теории категорий использоваться не будет. Скорее наоборот, на рассматриваемые нами конкретные конструкции знаток теории категорий может смотреть как на примеры общих категорных конструкций (таких как расширение Кана и т.д.) И наконец, к моменту начала изучения теории представлений симметрической группы, полезно знать про соотношения ортогональности для характеров конечной группы. Впрочем, аудитория при желании может заказать ликбез по теории представлений конечных групп. Литература: Я упомяну два учебника перечислительной комбинаторики общего плана: M. Aigner "Enumeration theory" (см. www.math.spbu.ru/VAlgebra/SPECIES/Aigner.djvu) и конечно же, "Перечислительную комбинаторику" Р. Стэнли. по Umbral Calculus и биномиальным последовательностям: глава 4 книги www.math.spbu.ru/VAlgebra/SPECIES/RotaWay.pdf и заметка Кнута www.math.spbu.ru/VAlgebra/SPECIES/KnuthCon.pdf По species: книга "Combnatorial species and tree like structures" www.math.spbu.ru/VAlgebra/SPECIES/Species.djvu, и более продвинутый курс лекций одного из авторов этой книги, в котором излагается и введение в теорию представлений симметрической группы www.math.spbu.ru/VAlgebra/SPECIES/bergeron.pdf

	3 October - 9 October Треугольник паскаля и матрица оператора сдвига $p(X)\mapsto p(X+1)$ на кольце многочленов. Биномиальная формула обращения. Количество сюръективных отображений из $m$ -элементного множества в $n$ -элементное. Матрица из чисел Стирлинга второго рода как матрица перехода от мономиального базиса к базису убывающих факториалов $X^{\underline n}=X(X-1)\dots (X-n+1)$ . Обратная к ней матрица из чисел Стирлинга первого рода со знаком. Аналог формулы Тейлора для конечных разностей. Формула Вандермонда --- биномиальное тождество для убывающих факториалов: $(X+Y)^{\underline n}=\sum\limits_k C_n^k X^{\underline k} Y^{\underline {n-k}}$ . Биномиальные последовательсти многочленов. Определение 1: при помощи биномиального тождества. Определение 2: при помощи обобщенного дельта-оператора. Вывод первого определения из второго. Определение 3: при помощи экспоненциальной производящей функции. вывод первого определения из третьего. .

	10 October - 16 October Матрица Паскаля как линейный оператор на формальных степенных рядах оказывается умножением на $e^t$ , так что биномиальная формула обращения следует из тождества $e^t\cdot e^{-t}=1$ . Линейные функционалы на пространстве $\mathbb C[X]$ , их отождествление с формальными степенными рядами $\mathbb C[[t]]$ по правилу $f(t)\mapsto \left[p(X)\mapsto f\left(\left.\frac \partial{\partial X}\right)p(X)\right\|_{X=0}\right]$ . Примеры: Значению в нуле отвечает ряд $1\in\mathbb C[[t]]$ , значению в точке $a$ отвечает ряд $e^{at}$ . Функционалу $p(X)\mapsto \int\limits_0^{a} p(s)ds$ отвечает ряд $\frac{e^{at}-1}t$ . "Базис" в $\mathbb C[[t]]$ , двойственный к мономиальному базису в $\mathbb C[X]$ , --- это $1, t, t^2/2,\dots, t^n/n!,\dots$ Оператор умножения на $e^t$ в пространстве формальных степенных рядов оказывается сопряженным к оператору сдвига на пространстве многочленов. Вообще, оператор умножения на $f(t)$ оказывается сопряженным оператору $f\left(\frac\partial {\partial X}\right)$ . Снова о биномиальных последовательностях. Вывод из определения 1 определения 3 (решение функционального уравнения $H(X+Y, t)=H(X, t)(H(Y, t)$ ). Вывод определения 2 из определения 3 --- применением оператора $g\left(\frac \partial{\partial X}\right)$ , где $g(f(t))=t$ , к равенству $e^{Xf(t)}=\sum p_n(X)\frac {t^n}{n!}$ . Иллюстрация: для биномиальной последовательности нижних факториалов отвечающей дельта-оператору $g(D)=e^D-1$ получаем формулу бинома Ньютона: $\sum X^{\underline n}\frac {t^n}{n!}=e^{XLog(1+t)}$ , т.е. $(1+t)^X=\sum \left(\begin{array}{c} X\\ n\end{array}\right)t^n$ . Композиция биномиальных последовательностей. Теорема. Умножению матриц коэффициентов двух биномиальных последовательностей многочленов соответствует подстановка ряда в ряд. Доказательство: Рассмотрим биномиальную последовательность $p_n(X)$ отвечающую дельта оператору $g(D)$ , т.е. $g(D)p_n(X)=np_{n-}(X)$ . Тогда "базис" в $C[[t]]$ , двойственный к базису $p_n(X)$ , --- это $1, g(t), g(t)^2/2, \dots, g(t)^n/n!,\dots$ , то есть получается из "стандартного базиса" подстановкой $t\mapsto g(t)$ . Пусть $q_n(X)=\sum q_{n, k} X^k$ --- биномиальная последовательность, отвечающая оператору $h(D)$ . Тогда матрицу $(q_{n, k})$ можно трактовать как матрицу перехода от базиса $p_n(X)$ к базису $r_n(X)=(q\circ p)_n(X)=\sum\limits_k q_{n, k}p_n(X)$ (напомним, что базис в пространстве $\mathbb C[X]$ мы записываем столбцом). Значит $(q_{n, k})$ --- это матрица перехода от "базиса" $1,\dots, g(t)^n/n!\dots$ в $\mathbb C[[t]]$ к базису, который двойственен к $r_n(X)$ (если выписывать "базисы" в $C[[t]]$ в строчку). Но мы знаем, что базис $1, u, u^2/2,\dots, u^n/n!,\dots$ , где $u\in \mathbb C[[t]]$ переводится умножением на матрицу $(q_{n, k})$ в базис $1, h(u), h(u)^2/2,\dots, h(u)^n/n!,\dots$ . Беря $u=g(t)$ мы видим, что базис, двойственный $r_n(X)$ --- это $1, h(g(t)), h(g(t))^2/2,\dots$ . Таким образом, $r_n(X)$ --- биномиальная последовательность, отвечающая дельта-оператору $h(g(D))$ . К примеру, если две биномиальные последовательности многочленов имеют производящие функции $e^{Xf(t)}$ и $e^{Xg(t)}$ такие, что $f(g(t))=t$ , то соответствующие матрицы коэффициентов взаимно обратны. Иллюстрация: матрица из чисел Стирлинга второго рода $(S(n, k))$ , будучи обратной к матрице перехода от мономиального базиса к нижним факториалам имеет экспоненциальную производящую функцию $\sum S(n, k)X^k\frac {t^n}{n!}=e^{X(e^t-1)}$ . Замечательное практическое следствие доказанной теоремы состоит в том, что композицию двух аналитических функций в окрестности нуля можно вычислять перемножая отвечающие им матрицы. Более того, при помощи умножения таких матриц можно написать формулу для извлечения "композиционного квадратного корня", т.е. найти ряд $h(t)$ такой, что $h(h(t))$ равен наперед заданному формальному степенному ряду.

	17 October - 23 October В планах на следующее занятие. Полиномы Белла. Формула Фаа ди Брюно для дифференцирования композиции. Биномиальная последовательность Абеля. Формула кэли для числа деревьев. Экспоненциальный принцип: почему экспоненциальные производящие функции для чисел Стирлинга первого и второго рода очевидны из комбинаторных соображений. Числа и полиномы Бернулли как частный случай последовательностей Аппеля. Формула суммирования Эйлера-Маклорена.

	24 October - 30 October В планах: определение типа струтур (specie) как функтора. Примеры операций над species.

	31 October - 6 November

	7 November - 13 November

	14 November - 20 November

	21 November - 27 November

	28 November - 4 December

	5 December - 11 December

	12 December - 18 December

	19 December - 25 December

	26 December - 1 January