Симметрические многочлены и массивы. Семинар 1

Симметрический многочлен — это многочлен от набора переменных, который не меняется при перестановках этих переменных. Например, теорема Виета, выражающая коэффициенты многочлена через его корни, выдаёт их в виде симметрических многочленов, называемых элементарными симметрическими. Все симметрические многочлены можно выразить как многочлены от элементарных симметрических — поэтому их произведения образуют базис в пространстве всех симметрических многочленов.
Но также есть и много других базисов в симметрических многочленах, естественно возникающих в разных задачах. Мы обсудим взаимосвязь между этими базисами. Отдельно выделим многочлены Шура $s_{\lambda}$ — базис, индексированный разбиениями натуральных чисел, и докажем тождество Коши $\prod _{i,j} 1/(1-x_iy_j)=\sum_{\lambda}s_{\lambda}(\bar x)s_{\lambda}(\bar y)$. Его мы будем доказывать при помощи совершенно комбинаторного понятия массива — прямоугольной таблицы с шариками, которые можно передвигать по определённым правилам.
Также при помощи массивов мы докажем, что любой перестановке из n элементов можно сопоставить пару таблиц Юнга (диаграмм Юнга, заполненных числами от $1$ до $n$) одинаковой формы $\lambda$, где $\lambda$ является разбиением числа $n$. Такое соответствие называется соответствием Робинсона-Шенстеда.
Курс планируется доступным школьникам, нужно знать формулу бесконечной геометрической прогрессии и уметь воспринимать комбинаторные конструкции.