Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P$ be the set of partitions of n. Let $\lambda$ denote the shape of a particular partition. Let $f_\lambda(i)$ be the frequency of $i$ in $\lambda$ and let $a_\lambda(i) := \# \lbrace j : f_\lambda(j) \geq i \rbrace$.

For example: $n=5,~ \lambda=(1,1,3),~ f_\lambda(1)=2,~ a_\lambda(1)=2$ (added: since $f_\lambda(1)$ and $f_\lambda(3)$ are both at least 1). It is easy to see that for a fixed $\lambda$, $\sum_k f_\lambda(k)=\sum_k a_\lambda(k)$. But, I am having trouble showing:

For a fixed $k$, $$\sum_\lambda f_\lambda(k)=\sum_\lambda a_\lambda(k)$$

Thanks for the help!

share|improve this question
    
Sorry for being unclear. $a_\lambda$ is the order of the set (hence the \sharp). That is in the case of $a_{\lambda_5}$, it is 1, since f(1) is 4. –  ReasonWheel Oct 2 '11 at 12:12

2 Answers 2

up vote 12 down vote accepted

Here's a proof using generating functions; I haven't given much thought yet to how it could be translated into a combinatorial argument.

The generating function for the number of partitions is

$$p(x)=(1+x+x^2+\dotso)(1+x^2+x^4+\dotso)(1+x^3+x^6+\dotso)\dots=\prod_m\frac1{1-x^m}\;.$$

To count the number of times a part $k$ occurs in the partitions of $n$ (the left-hand side of the equation), we can replace the $k$-th factor by one including this count:

$$ \begin{align} f_k(x) &=\left(0+1x^k+2(x^k)^2+3(x^k)^3+\dotso\right)\prod_{m\neq k}\frac1{1-x^m}\\ &=\left(x^k\frac{\mathrm d}{\mathrm d(x^k)}\left(1+x^k+(x^k)^2+(x^k)^3+\dotso\right)\right)\prod_{m\neq k}\frac1{1-x^m}\\ &=\left(x^k\frac{\mathrm d}{\mathrm d(x^k)}\frac1{1-x^k}\right)\prod_{m\neq k}\frac1{1-x^m}\\ &=\frac{x^k}{(1-x^k)^2}\prod_{m\neq k}\frac1{1-x^m}\\ &=\frac{x^k}{1-x^k}\prod_m\frac1{1-x^m}\\ &=p(x)\frac{x^k}{1-x^k}\;.\\ \end{align} $$

To count the number of at-least-$k$-fold occurrences of parts (the right-hand side of the equation), consider this generation function (which I'll first write out for $k=2$ to illustrate the idea and then generalize):

$$\begin{align} g_2(x,y) &=\left(1+x+y(x^2+x^3+\dotso)\right)\left(1+x^2+y((x^2)^2+(x^2)^3+\dotso)\right)\dots\\ &=\left(1+x+\frac{yx^2}{1-x}\right)\left(1+x^2+\frac{y(x^2)^2}{1-x^2}\right)\dots\\ &=\frac{1-x^2+yx^2}{1-x}\frac{1-(x^2)^2+y(x^2)^2}{1-x^2}\dots\\ &=p(x)\left(1-x^2+yx^2\right)\left(1-(x^2)^2+y(x^2)^2\right)\dots\;,\\ g_k(x,y) &=\prod_m\left(\sum_{l=0}^{k-1}(x^m)^l+y\sum_{l=k}^\infty(x^m)^l\right)\\ &=p(x)\prod_m\left(1-(x^k)^m+y(x^k)^m\right)\;. \end{align} $$

Every factor of $y$ tracks the at-least-$k$-fold use of a part. What we want is the total count of factors of $y$ included in the coefficient of $x^n$; that is, we want to count $j$ times the coefficient of $y^jx^n$. This we can get by differentiating with respect to $y$ and then setting $y$ to $1$; the coefficient of $x^n$ in the result will be the desired count. But

$$\begin{align} \left.\frac{\mathrm d}{\mathrm dy}g_k(x,y)\right|_{y=1} &=\left.\frac{\mathrm d}{\mathrm dy}p(x)\prod_m\left(1-(x^k)^m+y(x^k)^m\right)\right|_{y=1}\\ &=\left.p(x)\sum_{l=1}^\infty(x^k)^l\prod_{m\neq l}\left(1-(x^k)^m+y(x^k)^m\right)\right|_{y=1}\\ &=p(x)\sum_{l=1}^\infty(x^k)^l\\ &=p(x)\frac{x^k}{1-x^k}\;,\\ \end{align}$$

which coincides with the result for the left-hand side.

share|improve this answer
    
Superb answer. I wasn't even thinking on these lines. I did find a proof using the RSK correspondence. –  ReasonWheel Oct 3 '11 at 14:13
    
@ReasonWheel: Thanks. You could write that up as another answer? –  joriki Oct 3 '11 at 14:21
    
@joriki: You can create a bijection by rotating rectangles in the diagrams. I haven't investigated whether this corresponds to your g.f. approach in any way. –  David Bevan Oct 4 '11 at 7:30

You can establish a bijection in the partitions of $n$ between parts equal to $k$ and equal parts occurring at least $k$ times by ‘rotating rectangles’ in the diagrams of the partitions.

If $f_\lambda(i)\geqslant k$, we define $\rho_i(\lambda)$ to be the partition resulting from removing $k$ parts equal to $i$ and replacing them with $i$ parts equal to $k$ (i.e. ‘rotating’ an $i\times k$ rectangle in the diagram of $\lambda$, as shown below for $\rho_5$ with $k=3$). We could write $\rho_i(\lambda)=\lambda\:-<\!\!i^k\!\!>+<\!\!k^i\!\!>$.

$\qquad\qquad\qquad\qquad\qquad\qquad$ $\rho_5$

$\rho_i(\lambda)$ is a partition that contains at least $i$ elements equal to $k$. Indeed, if $\mu$ is a partition such that $f_\mu(k)=j$ then there are $j$ distinct partitions, $\lambda_1,\dots,\lambda_j$, with $\rho_i(\lambda_i)=\mu$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.