Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer

Your Answer


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.