# Prove $\frac{(q^n-1)(q^{n-1}-1)\dots (q^{n-r+1}-1)}{(q^r-1)(q^{r-1}-1)\dots(q-1)}=\sum_{\lambda\subseteq\Pi}q^{^{|\Pi\backslash\lambda|}}$

combinatoricsgeometry

Prove the combinatorial identity

$$\frac{(q^n-1)(q^{n-1}-1)\dots (q^{n-r+1}-1)}{(q^r-1)(q^{r-1}-1)\dots(q-1)}=\sum_{\lambda\subseteq\Pi}q^{^{|\Pi\backslash\lambda|}},$$

where the summation is performed over all different Young diagrams $$\lambda$$ that fit into a rectangle $$\Pi$$ of size $$r\times(n-r)$$, and the exponent $$|\Pi\backslash\lambda|$$ is equal to the number of cells in the complement of the diagram to a rectangle (the empty diagram $$\lambda=\emptyset$$ and the entire rectangle $$\lambda=\Pi$$ are also taken into account).

The left side reminds me of formulas for the number of subspaces of a given dimension in an $$n$$-dimensional space over a field of $$q$$ elements. However, I am not sure if this is how one should reason.

Let $$F(n,r)=\frac {(q^n-1)(q^{n-1}-1)\cdots(q^{n-r+1}-1)} {(q^r-1)(q^{r-1}-1)\cdots(q-1)} ,\qquad G(n,r)=\sum_{\lambda\subseteq\Pi_{r,n-r}}q^{|\Pi-\lambda|}$$ First of all, note that \begin{align} F(n,r)&=\frac {(q^n\color{blue}{-q^r+q^r}-1)(q^{n-1}-1)\cdots(q^{n-r+1}-1)} {(q^r-1)(q^{r-1}-1)\cdots(q-1)} \\&=\frac {(q^{n}-\color{blue}{q^r})(q^{n-1}-1)\cdots(q^{n-r+1}-1)} {(q^r-1)(q^{r-1}-1)\cdots(q-1)} +\frac {(\color{blue}{q^r}-1)(q^{n-1}-1)\cdots(q^{n-r+1}-1)} {(q^r-1)(q^{r-1}-1)\cdots(q-1)} \\&=q^r\cdot\frac{(q^{n-1}-1)\cdots(q^{n-r+1}-1)(q^{n-r}-\color{blue}{1})}{(q^r-1)(q^{r-1}-1)\cdots(q-1)}+\frac{(q^{n-1}-1)\cdots(q^{n-r+1}-1)}{(q^{r-1}-1)\cdots(q-1)},\end{align} We have shown $$F(n,r)= q^r F(n-1,r)+F(n-1,r-1)$$ This makes it clear that $$F(n,k)$$ is actually a polynomial for all $$n\ge k\ge 0$$.

The key point is this; we can prove that $$G(n,k)$$ satisfies the same recurrence relation as $$F(n,k)$$. To prove this, let $$S_1=\{\lambda \subseteq \Pi\mid \text{width of \lambda is less than n-r}\}\\ S_2=\{\lambda \subseteq \Pi\mid \text{width of \lambda equals n-r}\}\hspace{.8cm}$$ We can split $$G(n,k)$$ into $$\sum_{S_1} q^{|\Pi-\lambda|}$$ and $$\sum_{S_2} q^{|\Pi-\lambda|}$$.

• For $$\sum_{S_1} q^{|\Pi-\lambda|}$$, all of the summands $$q^{\Pi-\lambda}$$ have a factor of $$q^r$$, coming from the right column of the box that $$\lambda$$ does not touch. If you factor out that $$q^r$$, what remains is the sum of $$q^{|\Sigma-\mu|}$$, where $$\Sigma$$ is n $$r\times (n-r-1)$$ box and $$\mu$$ ranges over all partitions fitting inside $$\Sigma$$. Therefore, $$\sum_{S_1} q^{|\Pi-\lambda|}= q^r G(n-1,r)$$

• Similarly, if you delete the bottom row from each $$\lambda$$ in $$\sum_{S_2} q^{|\Pi-\lambda|}$$, then what remains is a sum over partitions fitting in an $$(r-1)\times (n-r)$$ box of the size of the complement of that partitions, which is exactly $$G(n-1,r-1)$$.

We have proven the polynomial equation $$G(n,r)=q^rG(n-1,r-1)+G(n-1,r).$$ After verifying that $$G(n,k)$$ and $$F(n,k)$$ satisfy the same base cases (both are equal to $$1$$ when $$n=k=0$$, and $$0$$ when $$n=0$$ but $$k\neq 0$$), the fact that they satisfy the same recurrence leads to a proof by induction on $$n$$ that $$F(n,k)=G(n,k)$$ for all $$n,k\ge 0$$.

In particular, since everything was done in the ring of integer polynomials over $$q$$, there is no need to appeal to the equation being true for infinitely many primes $$q$$. Once we have proven they are equal as polynomials, they are automatically equal as functions of $$q$$.