2
$\begingroup$

I've been reading up on combinatorics in my spare time recently. Suppose $\lambda$ is a partition of $n$, and $f_k(\lambda)$ the number of times that $k$ appears as a part of $\lambda$. Also, let $g_k(\lambda)$ be the number of distinct parts of $\lambda$ which occur at least $k$ times in $\lambda$. Why is it that $\sum f_k(\lambda)=\sum g_k(\lambda)$ for fixed $k$, if we let the sums run over all partitions $\lambda$ of a fixed $n$?

I think the general idea is that for any partition $\lambda$ of $n$, and any part $p$ occurring at least $k$ times, one needs to associate some partition $\delta$ of $n$ so that the total number of times given $\delta$ occurs is the same as the number of parts of $\delta$ which are equal to $k$. Is there a way to flesh this out? Thank you.

  • 0
    Your second paragraph doesn't read well. The number of distinct combinations $(\lambda,p)$ should equal the total number of occurrences of $k$, so "so that the total number of times given $\delta$ occurs is the same as the number of parts of $\delta$ which are equal to $k$" should be just "and an occurrence of a part $k$ in $\delta$".2012-02-16

1 Answers 1

1

For convenience let $F_k(n)=\sum_{\lambda\vdash n}f_k(\lambda)\;\text{ and }\;G_k(n)=\sum_{\lambda\vdash n}g_k(\lambda)\;.$ I’m pretty sure that it can’t be done by pairing up partitions of $n$. However, I can show that $F_k(n)=F_k(n-k)+p(n-k)\tag{1}$ and $G_k(n)=G_k(n-k)+p(n-k)\tag{2}\;,$ from which the result follows by induction.

$(1)$ is fairly easy. If $\lambda\vdash n$ has a part $k$, removing that part leaves a partition \lambda'\vdash n-k, and clearly f_k(\lambda)=f_k(\lambda')+1. If $\lambda\vdash n$ has no part $k$, then $\lambda$ does not contribute to $F(n)$. Thus, F_k(n)=\sum_{\begin{array}{}\lambda\vdash n\\k\in\lambda\end{array}}f_k(\lambda)=\sum_{\begin{array}{}\lambda\vdash n\\k\in\lambda\end{array}}\Big(f_k(\lambda')+1\Big)=F_k(n-k)+p(n-k)\;.

$(2)$ is a little harder. Start with a partition $\lambda\vdash n-k$, and let \lambda' be the partition of $n$ obtained by adding $k$ $1$-parts to $\lambda$; every partition of $n$ with at least $k$ $1$-parts is obtained in this way, so there are $p(n-k)$ partitions of $n$ with at least $k$ $1$-parts. To put it a little diffently, $1$-parts contribute $p(n-k)$ to $G_k(n)$.

Now suppose that $\lambda\vdash n$ has at least $k$ $r$-parts, where $r>1$. Let \lambda_r' be the partition of $n-k$ obtained by subtracting $1$ from each of $k$ $r$-parts of $\lambda$; clearly \lambda_r' has at least $k$ $(r-1)$-parts. Conversely, if $\lambda\vdash n-k$ has at least $k$ $s$-parts for some $s\ge 1$, the partition $\lambda_s^*\vdash n$ has at least $k$ $(s+1)$-parts. It follows that for $r>1$, the contribution of $r$-parts to $G_k(n)$ is equal to the contribution of $(r-1)$-parts to $G_k(n-k)$ and hence that the total contribution to $G_k(n)$ of $r$-parts for all $r>1$ is $G_k(n-k)$. Putting the pieces together yields $(2)$.

To get the induction started, note that $G_k(k)=1=F_k(k)$, via the partitions $1+\dots+1$ and $k$, respectively, and of course $G_k(n)=F_k(n)=0$ if $k>n$.