#Lah symmetric functions
The Lah symmetric functions were introduced in [PS21]. 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 numbers of such trees on \(n\) nodes are \(1,\) \(1,\) \(3,\) \(15,\) \(105,\dotsc,\) see A001147.
An unordered forest of 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} \) \( \textbf{1}\) \( 1 \) \( \textbf{2}\) \( 1 \) \( 1 \) \( \textbf{3}\) \( 3 \) \( 3 \) \( 1\) \( \textbf{4}\) \( 15 \) \( 15 \) \( 6 \) \( 1 \) \( \textbf{5}\) \( 105 \) \( 105 \) \( 45 \) \( 10 \) \( 1 \)A closed-form formula is given by \(\frac{(2n-k-1)!}{2^{n-k}(n-k)!(k-1)!},\) see [Eq. 7.11, PS21].
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 forests of 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. This also implies Schur positivity, since each \(\elementaryE_d\) is the Schur function \(\schurS_{1^d}\) and products of Schur functions are Schur-positive.
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 [PS21].
Example (Lah symmetric functions for \(n=4\)).
For \(n=4,\) \[\begin{aligned} \lah_{4,1} &= 6 \elementaryE_3 + 8 \elementaryE_{21} + \elementaryE_{111} = \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{aligned}\] For example, the three terms in \(\lah_{4,1}\) count increasing ordered trees whose child-count partition is respectively \((3),\) \((2,1),\) and \((1,1,1).\)
#The connected Lah forest basis
There is a natural multiplicative basis obtained by taking connected Lah forests as generators. Define \[\ell_d(\xvec) \coloneqq \lah_{d+1,1}(\xvec) \qquad\text{and}\qquad \ell_\lambda(\xvec) \coloneqq \ell_{\lambda_1}(\xvec)\ell_{\lambda_2}(\xvec)\dotsm .\] Since \[\ell_d = d!\elementaryE_d + \text{terms involving products of smaller elementary functions},\] the functions \(\ell_\lambda\) form a basis of \(\mathrm{Sym}_{\setQ}.\) The multiplication rule is simply \[\ell_\lambda \ell_\mu = \ell_{\lambda \cup \mu}.\]
The ordinary Lah symmetric functions are positive in this basis. If \(m_a(\lambda)\) denotes the multiplicity of the part \(a\) in \(\lambda,\) then \[\lah_{n,k} = \sum_{\substack{\lambda \vdash n-k \\ \ell(\lambda) \leq k}} \frac{n!} {(k-\ell(\lambda))!\prod_i(\lambda_i+1)! \prod_{a\geq 1} m_a(\lambda)!} \ell_\lambda .\] Indeed, once the non-singleton component sizes are fixed, the coefficient counts the ways to choose their vertex sets inside \([n]\); each component then contributes one connected Lah generator after standardizing its labels.
Example (Small connected Lah-basis expansions).
In degree at most \(3,\) the connected generators begin \[\ell_1=\elementaryE_1,\qquad \ell_2=\elementaryE_{11}+2\elementaryE_2,\qquad \ell_3=\elementaryE_{111}+8\elementaryE_{21}+6\elementaryE_3.\] For \(n=4,\) the Lah symmetric functions expand as \[\lah_{4,1}=\ell_3,\qquad \lah_{4,2}=4\ell_2+3\ell_{11},\qquad \lah_{4,3}=6\ell_1,\qquad \lah_{4,4}=1.\]
Remark
The connected Lah forest basis is not a positive basis for all elementary positive symmetric functions. In particular, the complete graph \(K_2\) is a unit interval graph, but its chromatic symmetric function satisfies \[\chrom_{K_2}(\xvec) = 2\elementaryE_2 = \ell_2-\ell_{11}.\] Thus unit interval graph chromatic symmetric functions are not all positive in the connected Lah forest basis.
Bibliography
- [PS21]Mathias Pétréolle and Alan D. Sokal. Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions. European Journal of Combinatorics, 92:103235, 2021.
.bib
@article{PetreolleSokal2019x, author = {Mathias Pétréolle and Alan D. Sokal}, title = {Lattice paths and branched continued fractions. {II}. Multivariate {Lah} polynomials and {Lah} symmetric functions}, year = {2021}, journal = {European Journal of Combinatorics}, volume = {92}, pages = {103235}, doi = {10.1016/j.ejc.2020.103235}, url = {https://doi.org/10.1016/j.ejc.2020.103235}, eprint = {1907.02645} }