# 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.

-

This problem is a special case of Exercise 3.150(a) of Enumerative Combinatorics, vol. 1 (second ed.). The polynomial $A_{\lbrace k\rbrace}(x)$ of this exercise is the $F_k(x)$ of the present question. The solution to this exercise gives a recipe for computing $F_k(x)$ which can probably be used to compute quite a few values and to prove some properties such as its degree. In the solution to part (b) there is given the formula $F_3(x)=3+2x-x^2-x^3$.
Thanks for the reference Richard. Also thanks for making the second edition available on your homepage. I'll order it for our library in any event. The method you suggest in your solutions is essentially the one I was using. For some reason I failed to spot that $$\frac{1}{(1-x^2)^2}=\frac{(1+x^2)}{(1-x^2)(1-x^4)}$$. So one of my summands for $k=4$ stumped me! I'm sure the degree bound is correct. Any chance that $F_k(x)$ is computable? – John Murray Jan 21 '12 at 21:28