# generating function formula

Suppose $\lambda$ is a young tableau, with one color boxes. Prove the generating function,

$F(x) = \Sigma_{\lambda} x^{i} = \prod_{n \geq 1} \frac{1}{1-x^n}$, where $i$ is the number of boxes in the young tableau.

attempt:

$\Sigma_{\lambda} x^{i} = \prod_{n \geq 1} \frac{1}{1-x^n} = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^4}\cdots = (1 + x + x^2 + x^3 + \cdots)(1 + x^2 + x^4+ \cdots )(1 + x^3 + x^6 + x^9 + \cdots)( 1+ x^4 + x^8 + x^{12} \cdots ) = 1 + x + 2x^2 + 3x^3 + \cdots$ .

Here this one comes from when we have zero boxes so we would have $x^0$, and when there is only one box, then we have $x^1$, similarly, there are $2x^2$ since there are two ways of having a young tableau with two boxes (horizontally, and vertically), and so on.

Suppose we have a Young tableaux with shape \begin{eqnarray*} (\underbrace{k,\cdots,k}_{a_k \text{times}}, \underbrace{k-1,\cdots,k-1}_{a_{k-1} \text{times}},\cdots,\underbrace{2,\cdots,2}_{a_2 \text{times}}\underbrace{1,\cdots,1}_{a_1 \text{times}}) \end{eqnarray*} This will give a contribution of $x^n$ to the generating function, where $n=a_1+2a_2+\cdots+(k-1)a_{k-1}+ka_k$.

To get all possible Young tableauxs, $k$ can take any value $1,2,\cdots$ and the values $a_k$ can take any value $0,1,\cdots$. So the generating function is given by \begin{eqnarray*} \sum_{a_1=0}^{\infty} \sum_{a_2=0}^{\infty} \cdots \sum_{a_{k-1}=0}^{\infty} \sum_{a_k=0}^{\infty} \cdots x^n \end{eqnarray*} All of the sums will "decouple" and this can be rewritten as \begin{eqnarray*} \sum_{a_1=0}^{\infty} x^{a_1} \sum_{a_2=0}^{\infty} x^{2 a_2}\cdots \sum_{a_{k-1}=0}^{\infty} x^{(k-1)a_{k-1}} \sum_{a_k=0}^{\infty} x^{ka_k}\cdots \end{eqnarray*} Now sum each of these geometric plums & we get \begin{eqnarray*} \frac{1}{(1-x)} \frac{1}{(1-x^2)} \cdots \frac{1}{(1-x^{k-1})} \frac{1}{(1-x^k)} \cdots = \prod_{k=0}^{\infty} \frac{1}{(1-x^k)} \end{eqnarray*}

Let $p(n,k)$ denote the number of partitions of $n$ with largest part at most $k$. Then, of the $p(n,k)$ such partitions, there are some that have a partition with part $k$ and some that don't. Those that don't have part $k$ are all precisely the partitions of $n$ with largest part at most $k-1$, so there are $p(n,k-1)$ of them. Those that do have part $k$ can be converted into a partition of largest part $k$ of $n-k$ by removing the $k$. Thus, we have the recurrence $$p(n,k) = p(n-k,k) + p(n,k-1).$$ Defining the generating function $F_k(x) = \sum_{n\geq0}p(n,k)x^n$, the recurrence translates to $$F_k(x) = x^kF_k(x) + F_{k-1}(x)$$ which rearranges to $$F_k(x) = \frac{F_{k-1}(x)}{1-x^k}.$$

Can you proceed from here?

Edit:

Now, note that $F_1(x) = \sum_{n\geq0} x^n = \frac1{1-x}$ since there is always exactly one way to write $n$ as a partition with largest part $1$. Then, induction shows that $F_k(x) = \prod_{1\leq n\leq k}\frac1{1-x^n}$. It follows that for partitions of any large sized part, you take the desired infinite product.

• I don't know how that would be equivalent to $\Sigma_{\lambda} x^i$. – Mahidevran Jul 26 '17 at 20:32
• Ok, I'll add a bit more steps in the answer. – Tai Jul 26 '17 at 20:33