由于x义x的脑容量太小了所以不得不整一个这个东西。

Part 1 - 什么是 Symmetric Functions

一个 symmetric funcion

是一个每项度数都相等的无限元多项式（多项式只是说说而已，其实我甚至不确定它是不是幂级数……）（你也可以理解为它是一个"元数足够多"的形式幂级数）；
$x_i\leftarrow x_{w(i)}$ $w$ 是一个正整数的排列。

$n$ $\Lambda^n$ 。

很快你会发现这个人畜无害的定义总是能和莫名其妙的鬼东西发生关联。

Part 2 - Symmetric Functions 中的基本结论

Symmetric Functions 和划分有着巨大的关联。所以我们需要一些关于划分的工具。

$\lambda=(\lambda_1,\lambda_2,...,\lambda_{\ell(\lambda)})$ 。.

$|\lambda|=\sum_{}\lambda_i$ $\lambda$ $n$ $\lambda\vdash n$ $|\lambda|=n$ 。

dominance order $\le$ $\lambda\le \mu$ 当且仅当

\forall i,\lambda_1+\ldots+\lambda_i\le\mu_1+\ldots+\mu_i

我们来试图解释一下这个东西： $\mu$ $\mu_i\leftarrow\mu_i-1$ $1$ $j>i$ $\le\mu$ 的所有划分。

$\le$ $n\le 5$ $n\ge6$ 就不是了）

Part 2.1 Monomial Symmetric Function

定义 Monomial Symmetric Functions 为 $m_{\lambda}=\sum_{I}x^I$ $I$ $\lambda$ 的指标集合。

$m_{11}=\sum_{i<j}x_ix_j,m_{21}=\sum_{i\neq j}x_i^2x_j$ 。

显然， $\{m_{\lambda}:\lambda\vdash n\}$ $\Lambda^n$ 的一组线性基。

Part 2.2 Elementary Symmetric Funcion

Elementary Symmetric Functions $e_{\lambda}$ ，其定义如下： $e_n=m_{1^n},e_{\lambda}=\prod e_{\lambda_i}$ 。

$e_{\lambda},\lambda\vdash n$ $m_{\mu},\mu\vdash n$ $\color{#ea6965}e_{\lambda}=\sum_{\mu}M_{\lambda\mu}m_{\mu}$ 。

$M_{\lambda\mu}$ $\lambda_i$ $i$ $\mu$ 的放置方案数。盒和（颜色相同的）球皆不可区分。

$M_{\lambda\mu}=M_{\mu\lambda}$ 。反转"颜色"和"盒"的概念立得。

易见：

\color{#ea6965}\prod_{i,j}(1+x_iy_i)=\sum_{\lambda,\mu}M_{\lambda\mu}m_{\lambda}(x)m_{\mu}(y)

$e_{\lambda}$ 是否是一个基？

定理 1. (The Foundamental Theorem of Symmetric Functions)
$M_{\lambda\lambda^T}=1$ $M_{\lambda\mu}\neq 0$ $\mu\le\lambda^T$ 。
$M$ 是一个"上三角矩阵"。打引号是因为这里是偏序而非全序关系。）

证明 - 定理 1.
$M_{\lambda\mu}$ 和 dominance order 的组合意义，这应该是很有道理的吧！！

Part 2.3 Complete Homogeneous Symmetric Funcion

Complete Homogeneous Symmetric Functions $h_{\lambda}$ $\color{#ea6965}h_n=\sum_{\lambda\vdash n}m_{\lambda},h_{\lambda}=\prod h_{\lambda_i}$ 。

$h_{\lambda}=\sum_{\mu}N_{\lambda\mu}m_{\mu}$ $N_{\lambda\mu}$ $N_{\lambda\mu}=N_{\mu\lambda}$ 。

另有：

\color{#ea6965}\prod_{i,j}(1-x_iy_j)^{-1}=\sum_{\lambda,\mu}N_{\lambda\mu}m_{\lambda}(x)m_{\mu}(y)

$h_{\lambda}$ 是否是一个基？

$e$ $e$ $h$ 的线性变换并证明了它有逆。

定理 2.
$w$ $e$ 上的点值唯一确定。）
$\omega$ ，它将会在今后扮演重要角色。）
$\omega$ 有逆且就是自身。）

证明 - 定理 2.
$\omega$ 是积性的。
$h_{\lambda}=\sum_{\mu}W_{\lambda\mu}e_{\mu}$ 。
我们有
$e_{\lambda}=[m_{\lambda}(y)]\prod(1+x_iy_j)\\ h_{\lambda}=[m_{\lambda}(y)]\prod(1-x_iy_j)^{-1}=(-1)^{|\lambda|}[m_{\lambda}(y)]\prod(1+x_iy_j)^{-1}$
$e_{\lambda},h_{\lambda}$ $e_n,h_n$ $w(h_n)=e_n$ $w$ 的积性。）
$e_n,h_n$ 的情形。有
$e_n=[y^n]\prod(1+x_iy)\\ h_n=(-1)^{n}[y^n]\prod(1+x_iy)^{-1}$
于是，
$\sum_{i=0}^n(-1)^{n-i}e_ih_{n-i}=[n=0]$
$\omega$ $\omega(1)=\omega(e_{\varnothing})=h_{\varnothing}=1$ 。
$\sum_{i=0}^n(-1)^{n-i}h_i\omega(h_{n-i})=\sum_{i=0}^n(-1)^{i}h_i\omega(h_{n-i})=[n=0]$
$\omega(h_{n-i})$ $u_{n-i}$ 。

Part 2.4 Power Sum Symmetric Function

还有完没完了……

Power Sum Symmetric Functions $p_{\lambda}$ $\color{#ea6965}p_n=\sum_i x_i^n,p_{\lambda}=\prod p_{\lambda_i}$ 。

$\color{#ea6965}p_{\lambda}=\sum_{\mu}R_{\lambda\mu}m_{\mu}$ $R$ 的组合意义与之前类似，但是同色球必须放在同一个盒里。

$\lambda>\mu$ $R_{\lambda\mu}=0$ $R_{\lambda\lambda}\neq 0$ $p$ 也是基。

定义

\color{#ea6965}z_{\lambda}=\prod_i\lambda_i\cdot\prod_j\left(\sum_{i}[\lambda_i=j]\right)!

这个东西在巨大多群论题里出现过，各位应该已经很熟悉了。

容易验证：

\color{#ea6965} \begin{aligned} \prod_{i,j}(1-x_iy_j)^{-1}&=\exp\sum_{n=1}^{\infty}\dfrac 1np_n(x)p_n(y)\\ &=\sum_{\lambda}p_{\lambda}(x)p_{\lambda}(y)/z_{\lambda} \end{aligned}\\ \color{#ea6965} \begin{aligned} \prod_{i,j}(1+x_iy_j)&=\exp\sum_{n=1}^{\infty}\dfrac {(-1)^{n-1}}np_n(x)p_n(y)\\ &=\sum_{\lambda}p_{\lambda}(x)p_{\lambda}(y)/z_{\lambda}\cdot(-1)^{|\lambda|-\ell(\lambda)} \end{aligned}

$p_{n}$ 定理 2 $\omega$ 的特征向量。

\sum_{\lambda}h_{\lambda}=\prod_{i}(1-x_i)^{-1}=\text{exp}\sum_{n=1}^{\infty}\dfrac{p_n(x)}{n}

$\omega$ 得

\exp\sum_{n=1}^{\infty}\dfrac{w(p_n(x))}{n}=\sum_{\lambda}e_{\lambda}=\prod_{i}(1+x_i)=\exp\sum_{n=1}^{\infty}\dfrac{(-1)^{n-1}p_n(x)}{n}

$p_n(x)$ 互相线性无关，故得证。

$h,e$ $p$ 表示。

{\color{#ea6965}e_n}=[y^n]\prod(1+x_iy)=[y^n]\exp\sum_{i=1}^{\infty}\dfrac{(-1)^{i-1}}{i}p_i(x)y^i\\ \color{#ea6965}=\sum_{\lambda\vdash n}(-1)^{n-\ell(\lambda)}p_{\lambda}/z_{\lambda}

类似地，

\color{#ea6965}h_n=\sum_{\lambda\vdash n}p_{\lambda}/z_{\lambda}

Part 2.5 - 杂项

$\text{ex}$ ，它被称为 the exponential specialization。

\color{#ea6965}\text{ex}(f)=\sum_{n\ge 0}[x_1x_2...x_n]f\dfrac{t^n}{n!}

$m,e,h,p$ 上的点值。

定义 Symmetric Functions 上的点积是一个双线性函数，其部分点值如下：

\color{#ea6965}\left<m_{\lambda},h_{\mu}\right>=[\lambda=\mu]

显然它已经唯一确定了。

引理 1.
以上定义点积具有对称性，且 $f$ $\left<f,f\right>\ge 0$ $f=0$ 。

引理 1 - 证明.
对称性：注意到
$\left<h_{\lambda},h_\mu\right>=N_{\lambda\mu}=\left<h_{\mu},h_{\lambda}\right>$
立即得证。
$h$ $f$ 立得。

引理 2.
$\{u\},\{v\}$ 满足
$\color{#ea6965}\left<u_\lambda,v_{\mu}\right>=[\lambda=\mu]$
$\{u\},\{v\}$ 是对偶基）当且仅当
$\color{#ea6965}\sum_{\lambda}u_{\lambda}(x)v_{\lambda}(y)=\prod_{i,j}(1-x_iy_j)^{-1}$

引理 2 - 证明.
略。线性表示什么的瞎搓一顿就是了。

引理 3.
$\color{#ea6965}\left<f,g\right>=\left<\omega(f),\omega(g)\right>$

引理 3 - 证明.
$\left<w(p_{\lambda}),w(p_{\mu})\right>=(-1)^{|\lambda|-\ell(\lambda)}\cdot(-1)^{|\mu|-\ell(\mu)}\cdot\left<p_{\lambda},p_{\mu}\right>$
$\left<p_{\lambda},p_{\mu}\right>\neq 0$ $\lambda=\mu$ 。
引理 2 $\left<p_{\lambda},p_{\mu}\right>=z_{\lambda}[\lambda=\mu]$ 。这就得证了。

Part 3 - Schur Function

Part 3.1 - 想不到标题

Schur Function 也是 Symmetric Function，但它的定义和性质较为复杂。

我们先定义半标准杨表（Semi-Standard Young Tableau）：

$\lambda$ $\lambda$ 的杨图上的填数方案，且元素在行上不降在列上严格增。
$T$ $\text{sh}(T)$ 。
type $(\alpha_1,\alpha_2,...)$ $\alpha_i$ $i$ 的次数。
记

x^T=\prod x_i^{\alpha_i(T)}

当然，上面的杨图也可以拓展为斜杨图。

而 Schur Function 就是依托斜杨图的 SSYT 定义的：

\color{#ea6965}s_{\lambda/\mu}=\sum_{\text{sh}(T)=\lambda/\mu}x^T

这个定义有很多令人迷惑的点。首先，它真的是一个 Symmetric Function？

定理 3.
$s_{\lambda/\mu}$ 确实是一个 Symmetric Function。

定理 3 - 证明.
$x_i$ $x_{i+1}$ 。即，我们考虑构造一个从 type 为
$\alpha=(\alpha_1,...,\alpha_i,\alpha_{i+1},...)$
$\lambda/\mu$ 的 SSYT 集合到
$\alpha'=(\alpha_1,...,\alpha_{i+1},\alpha_{i},...)$
$\lambda/\mu$ 的 SSYT 集合的双射。
$i$ $i+1$ 的格子，我们称其为非自由格子。可见非自由格子成对出现，那就不管了。
$i$ $i+1$ $i$ $a$ $i+1$ $b$ $a,b$ $0$ $b$ $i$ $a$ $i+1$ 就完成交换了。

$\color{#ea6965}s_{\lambda/\mu}=\sum_{\upsilon\vdash n}K_{\lambda/\mu,\upsilon}m_{\upsilon}$ （它被称为 Kostka Number）。因为众所周知斜杨表计数不好做，而这东西比斜杨表计数强到不知道哪里去了……

$\upsilon=1^n$ ，那直接应用斜杨表计数就可以了。

$s_{\lambda}$ 是一个基。

定理 4.
$K_{\lambda\lambda}=1$ $K_{\lambda\mu}\neq 0$ $\mu\le\lambda$ 。
这直接引出 $s_{\lambda}$ 是一个基。

定理 4 - 证明.
显然，略。

Part 3.2 - 想不到标题

下面这些结论需要借助一些计数工具才能得出，比如 RSK 算法和 LGV 引理等等。

$s_{\lambda}$ 不仅是一个基，而且它还是一个标准正交基。

定理 5. (the Cauchy Identity)
$\color{#ea6965}\sum_{\lambda}s_{\lambda}(x)s_{\lambda}(y)=\prod_{i,j}(1-x_iy_j)^{-1}$
$\color{#ea6965}\left<s_{\lambda},s_{\mu}\right>=[\lambda=\mu]$ 。

定理 5 - 证明.
$m_{\lambda}m_{\mu}$ $N_{\lambda\mu}$ $\text{type}=\lambda$ $\text{type}=\mu$ 的方案数。
$m_{\lambda}m_{\mu}$ $\text{type}=\lambda$ $\text{type}=\mu$ 且形状相同的 SSYT 对数。
那么右式到左式的双射也很明显了：把颜色与盒的对应写成矩阵，对其运行 RSK 算法即可。

由上可直接推出

\color{#ea6965}h_{\lambda}=\sum_{\mu}K_{\mu\lambda}s_{\mu}

类似于 the Cauchy Identity，还有

\color{#ea6965}\sum_{\lambda}s_{\lambda}(x)=\prod_{i}(1-x_i)^{-1}\cdot\prod_{i<j}(1-x_ix_j)^{-1}

右式数的就是对称矩阵的个数。

$\prod_{i,j}(1-x_iy_j)^{-1}$ $\prod_{i,j}(1+x_iy_j)$ 有关。

$x$ $>x$ $\ge x$ 的元素。

可以用和与 RSK 算法类似的方法验证：

$0/1$ $(P,Q)$ $P^T,Q$ 是半标准杨表。

于是有 the Dual Cauchy Identity：

\color{#ea6965}\sum_{\lambda}s_{\lambda}(x)s_{\lambda^T}(y)=\prod_{i,j}(1+x_iy_j)

那么易得

\color{#ea6965}\omega(s_{\lambda})=s_{\lambda^T}

根据 LGV 引理（具体证明在此），可得

\color{#ea6965}s_{\lambda/\mu}=\text{det}(h_{\lambda_i-i-\mu_j+j})

$\omega(s_{\lambda})=s_{\lambda^T}$ 还可得

\color{#ea6965}s_{\lambda/\mu}=\text{det}(e_{\lambda^T_i-i-\mu^T_j+j})

$\text{ex}$ $\text{ex}(h_{\lambda})=\dfrac{t^{|\lambda|}}{\prod\lambda_i!}$ $t=1$ ，得：

\color{#ea6965}f^{\lambda/\mu}=(|\lambda/\mu|!)\cdot\text{det}\left(\dfrac{1}{\lambda_i-i-\mu_j+j}\right)

$f^{\lambda/\mu}$ $\lambda/\mu$ 的数量。可喜可贺！

Part 3.3 - 想不到标题

线代大法！