# The Problem

This strikes me as a very natural problem which should have been asked (and solved?) already.

For each positive integer k, find a *nice* expression for the following generating function in the variable x:
$$
\sum_{\lambda/\mu} x^{|\lambda|}.
$$

Here \lambda ranges over all partitions and \mu over those partitions contained in \lambda for which the skew Young diagram \lambda/\mu has k nodes i.e. each partition of n is weighted by the number of partitions of n-k it contains.

Examples: k=1, the function is $\frac{x}{(1-x)}P(x) $, where $P(x)=\prod_{i=1}^\infty(1-x^i)^{-1}$ is the partition generating function. So in this case I'm just enumerating partitions by the number of removable nodes. The formula is equivalent to the well-known fact that every partition has one more addable than removable node.

I've computed the cases k=2,3,4 also (k=4 was painful - I broke it into 14 possible *types* of skew-diagrams). For k=2 the generating function is $\frac{ x^2(2-x)}{(1-x)(1-x^2)}P(x).$

It seems plausible that there is a polynomial F_k(x) of degree at most k(k-1)/2 (with leading coefficient \pm 1) so that the power series is $$ \frac{ x^k F_k(x)}{(1-x)(1-x^2)..(1-x^k)}P(x). $$

If $F_k(x)$ exists, it's easy to see that it must have *lowest* terms
$p_k+p_{k+1}x+2(p_{k+2}-1)x^2+...$, where p_n=number of partitions of n, after which the terms depend on congruences for k. This suggests that its complicated. Perhaps there is no nice expression for $F_k(x)$. Even knowing whether $F_k(x)$ exists is of interest to me. Maybe there is a neater way of expressing the entire generating function?

# Motivation

The coefficient of $x^n$ in the generating function is the dimension of the centre of a certain subalgebra of the complex group algebra of the symmetric group of degree n. This is ${\mathbb C}S_n^{S_{n-k}}$, the *centralizer* of the subgroup $S_{n-k}$ in ${\mathbb C}S_n$. It is easy to see that this has as ${\mathbb C}$-basis the $S_{n-k}$-orbit sums in $S_n$. The centre is indexed by pairs $(\chi,\phi)$, where $\chi$ is an irreducible character of $S_n$, and $\phi$ is an irreducible character of $S_{n-k}$ occuring in the restriction of $\chi$. The formulation above is then an easy consequence of the parametrization of irreducible characters of $S_n$, and the classic *branching rule*.

# Literature

Yoshiaki Ueno, On the Generating Functions of the Young Lattice, J. Algebra 116 (1988) 261--270.

This gives a generating polynomial for the partitions contained in a given partition \lambda in terms of a determinant involving Gaussian coefficients. It's a beautiful result, but it did not give me any insight into my problem.