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.



What is the generating function for skew Young diagrams?
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$.


