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

Question

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.

Answer 1

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.

Answer 2

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 ;-)

Answer 3

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