# Equality of times blocks of size $k$ appear in a partition with the number of distinct parts appearing $\geq k$ times?

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.

-
I don't understand. Did you mean to write "$f_k(\lambda)$ is the number of times a block of size $k$ appears in $\lambda$?" (I don't see how $k$ itself can appear more than once in a given partition.) – William DeMeo Feb 16 '12 at 8:16
@williamdemeo Yes, I mean it in that sense. For example, taking $n=13$ and $k=3$, then for the partition $\lambda=(1,1,2,3,3,3)$, I would say $f_3(\lambda)=3$. – Clara Feb 16 '12 at 9:15
Oh, okay. I was thinking of partitions of an $n$-element set; e.g. for $n=3$, $\lambda = |0|1,2|$ is a partition. – William DeMeo Feb 16 '12 at 9:20
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$". – Marc van Leeuwen Feb 16 '12 at 15:10

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$.