The symmetric functions catalog

An overview of symmetric functions and related topics


Lah symmetric functions

The Lah symmetric functions were introduced in [PS19b]. They are indexed by two integers, $n \geq k \geq 1.$ The combinatorial description is as follows.

We first need the notion of an increasing ordered tree on vertex set $[n].$ Each node has label smaller than its children (so vertex labeled $1$ is a root), and the children are ordered linearly. The number of such trees on $n$ nodes are given by $1,$ $1,$ $3,$ $15,$ $105,\dotsc,$ see A001147.

An unordered forest on increasing ordered trees is a forest on vertex set $[n],$ where each component is an increasing ordered tree. The number of such forests on $n$ vertices with $k$ trees is given by A001497:

$n \backslash k$$\textbf{1}$$\textbf{2}$$\textbf{3}$$\textbf{4}$$\textbf{5}$
A closed-form formula is given by $\frac{(2n-k-1)!}{2^{n-k}(n-k)!(k-1)!},$ see [Eq. 7.11, PS19b].

The Lah symmetric function is then defined as

\[ \lah_{n,k}(\xvec) \coloneqq \sum_{F \in \mathrm{Forests}(n,k)} \prod_{j=1}^n \elementaryE_{c(j)}(\xvec) \]

where $c(j)$ is the number of children of vertex $j,$ and the sum is taken over all unordered forest on increasing ordered trees, with $n$ vertices and exactly $k$ trees. By definition, the $\lah_{n,k}(\xvec)$ are positive in the elementary symmetric function basis.

Note: the $\lah_{n,k}(\xvec)$ is denoted $L^{(\infty)+}_{n,k}(X)$ and $L^{(\infty)-}_{n,k}(X) = \omega \lah_{n,k}(\xvec)$ in [PS19b].

Example (Lah symmetric functions for $n=4$).

We have that

\begin{align*} \lah_{4,1} &= 6 \elementaryE_3 + 8 \elementaryE_{21} + \elementaryE_{3} = \monomial_{3} + 11\monomial_{21}+36\monomial_{111}, \\ \lah_{4,2} &= 8 \elementaryE_2 + 7 \elementaryE_{11} = 7\monomial_{2} + 22\monomial_{11} \\ \lah_{4,3} &= 6 \elementaryE_{1}= 6\monomial_{1} \\ \lah_{4,4} &= 1. \end{align*}