2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm unable to follow the second part of your proof. It seems flawed to me, but perhaps I just don't understand it. $\endgroup$ – joriki Dec 30 '19 at 18:36
  • $\begingroup$ 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. $\endgroup$ – charlesh Dec 30 '19 at 20:27
  • $\begingroup$ Why does it have one more distinct element? $a_k$ could already have been distinct? $\endgroup$ – joriki Dec 30 '19 at 21:05
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please tell me what you did by $[x^n]$? $\endgroup$ – charlesh Dec 30 '19 at 20:32
  • $\begingroup$ @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. $\endgroup$ – joriki Dec 30 '19 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.