Show that the number of $1$s in all the partitions equals the sum of number of distinct elements in each partition

Consider the number $$n$$ a partition $$P$$ of $$n$$. Denote by $$f_n(P)$$ the number of $$1$$s in $$P$$ and by $$g_n(P)$$ the number of distinct elements in $$P$$. Show that $$\displaystyle\sum_{P} f_n(P) = \displaystyle\sum_{P} g_n(P)$$. Note that a partition is a non-decreasing sequence of integers that add upto $$n$$.

Here is my take on the problem :

Denote by $$p(n)$$ the number of partitions of $$n$$. Now any partition of $$n+1$$ such that it has a $$1$$ is basically $$1$$ $$+$$ some partition of $$n$$, which gives -

$$\displaystyle\sum_P f_{n+1}(P) = p(n) + \displaystyle\sum_P f_{n}(P)$$

Similarly just add $$1$$ to the largest element of every partition of $$n$$ to get $$n+1$$. Consider the partitions of $$n+1$$ into two categories - one having the largest integer appear only once in the partition and another having the largest integer repeat. In the second category, reducing the last number (by $$1$$) either keeps the number of distinct elements same or decreases by $$1$$, which isn't desired, while in the first category, reducing the largest element by $$1$$ yields a partition of $$n$$ that has exactly one less number of distinct elements. We basically generate

$$\displaystyle\sum_P g_{n+1} (P) = p(n) + \displaystyle\sum_P g_{n} (P)$$, as desired.

Is there a way to solve this without induction? Elegant methods requiring generating functions are fine too, though I'd appreciate any solution that relies on construction and not recurrences/GFs.

• I'm unable to follow the second part of your proof. It seems flawed to me, but perhaps I just don't understand it. – joriki Dec 30 '19 at 18:36
• if $[a_1, a_2, \cdots, a_k]$ is a partition of $n$ (with $a_i \leq a_j$ for $i\leq j$), just make it $[a_1, a_2, \cdots, a_{k-1}, a_k +1]$ to get a partition of $n+1$ having one more distinct element. Do this for every partition of $n$. I'm sorry, perhaps the explanation isn't very clear. – charlesh Dec 30 '19 at 20:27
• Why does it have one more distinct element? $a_k$ could already have been distinct? – joriki Dec 30 '19 at 21:05

Let $$a_n$$ be the number of 1s occurring in all partitions of $$n$$, let $$b_n$$ be the number of distinct parts summed over all partitions of $$n$$, and let $$p_n$$ be the number of partitions of $$n$$. We show that $$a_n = \sum_{k=0}^{n-1} p_k = b_n$$.

First, we have \begin{align*} a_n &= \sum_{p \vdash n} \sum_{1 \in p} 1 = \sum_{\substack{p \vdash n \\ p \ni 1}} \sum_{1 \in p} 1 = \sum_{\substack{p \vdash n \\ p \ni 1}} \left(1 + \sum_{1 \in p-1} 1 \right) \\ &= \sum_{q \vdash n-1} \left(1 + \sum_{1 \in q} 1 \right) = \sum_{q \vdash n-1} 1 + \sum_{q \vdash n-1} \sum_{1 \in q} 1 = p_{n-1} + a_{n-1}, \end{align*} which immediately implies that $$a_n = \sum_{k=0}^{n-1} p_k$$. Now $$b_n = \sum_{p \vdash n} \sum_{\substack{\text{distinct} \\k \in p}} 1 %= \sum_{p \vdash n} \sum_{\substack{k \ge 1 \\ k \in p}} 1 = \sum_{k=1}^n \sum_{\substack{p \vdash n \\ p \ni k}} 1 = \sum_{k=1}^n p_{n-k} = \sum_{k=0}^{n-1} p_k,$$ as desired.

A constructive proof

We will consider two different one-to-many mappings between the partitions of a number $$N$$ and the partitions of numbers smaller than $$N$$. It is convenient to adopt the convention that $$P(0)=1.$$

FIRST METHOD

Let the given partition of $$N$$ contain $$k$$ copies of $$1$$. Map this partition onto the $$k$$ partitions obtained by deleting one $$1$$, two $$1$$s, ...

E.G. $$9=1+1+2+5$$ maps to $$1+2+5$$ and $$2+5$$.

SECOND METHOD

Let the given partition of $$N$$ contain $$l$$ distinct numbers. Map this partition onto the $$l$$ partitions obtained by deleting one of each distinct number in turn.

E.G. $$9=1+1+2+5$$ maps to $$1+2+5$$,$$1+1+5$$ and $$1+1+2$$.

Each partition of a number smaller than $$N$$ (including $$0$$) is mapped onto by precisely one partition of $$N$$ for each of these methods and so $$\sum l=\sum k$$.

The generating function $$f(x,y)=\sum_{n,k}f_{nk}x^ny^k$$ that counts the partitions of $$n$$ with $$k$$ parts $$1$$ is

$$\begin{eqnarray} f(x,y) &=&\sum_{j=0}^\infty(xy)^j\prod_{m=2}^\infty\sum_{j=0}^\infty x^{jm} \\ &=& \frac1{1-xy}\prod_{m=2}^\infty\frac1{1-x^m}\;. \end{eqnarray}$$

The generating function $$g(x,y)=\sum_{n,k}g_{nk}x^ny^k$$ that counts the partitions of $$n$$ with $$k$$ distinct parts is

$$\begin{eqnarray} g(x,y) &=& \prod_{m=1}^\infty\left(1+y\sum_{j=1}^\infty x^{jm}\right) \\ &=& \prod_{m=1}^\infty\frac{1-x^m(1-y)}{1-x^m}\;. \end{eqnarray}$$

We can extract the desired sums from these generating functions:

$$\begin{eqnarray} \sum_Pf_n(P) &=& \left[x^n\right]\left.\frac\partial{\partial y}f(x,y)\right|_{y=1} \\ &=& \left[x^n\right]\left.\frac x{(1-xy)^2}\prod_{m=2}^\infty\frac1{1-x^m}\right|_{y=1} \\ &=& \left[x^n\right]\frac x{1-x}\prod_{m=1}^\infty\frac1{1-x^m} \end{eqnarray}$$

and likewise

$$\begin{eqnarray} \sum_Pg_n(P) &=& \left[x^n\right]\left.\frac\partial{\partial y}g(x,y)\right|_{y=1} \\ &=& \left[x^n\right]\left.\sum_{m=1}^\infty\frac{x^m}{1-x^m}\prod_{m'\ne m}\frac{1-x^m(1-y)}{1-x^m}\right|_{y=1} \\ &=& \left[x^n\right]\left(\sum_{m=1}^\infty x^m\right)\left(\prod_{m=1}^\infty\frac1{1-x^m}\right) \\ &=& \left[x^n\right]\frac x{1-x}\prod_{m=1}^\infty\frac1{1-x^m}\;. \end{eqnarray}$$

Sorry about the generating functions ;-)

• Could you please tell me what you did by $[x^n]$? – charlesh Dec 30 '19 at 20:32
• @charlesh: $\left[x^n\right]$ is meant to denote the extraction of the coefficient of $x^n$. Since $y=1$ is substituted, the resulting function is a function of $x$ only, and $\left[x^n\right]$ extracts the coefficient of $x^n$ in that function. – joriki Dec 30 '19 at 20:37