Two interpretations of a sequence: an opportunity for combinatorics

Question

The sequence that is addressed here is resourced from the most useful site OEIS, listed as A014153, with a generating function $$\frac1{(1-x)^2}\prod_{k=1}^{\infty}\frac1{1-x^k}.$$ In particular, look at these two interpretations mentioned there.

$a(n)=$ Number of partitions of $n$ with three kinds of $1$.

Example. $a(2)=7$ because we have $2, 1+1, 1+1', 1+1'', 1'+1', 1'+1'', 1''+1''$.

$b(n)=$ Sum of parts, counted without multiplicity, in all partitions of $n$.

Example. $b(3)=7$ because the partitions are $3, 2+1, 1+1+1$ and removing repetitions leaves $3, 2+1, 1$. Adding these shows $b(3)=7$.

I could not resist asking:

QUESTION. Can you provide a combinatorial proof for $a(n)=b(n+1)$ for all $n$.

Answer 1

Here is a bijective proof that equates both $a(n)$ and $b(n+1)$ to the quantity $$p(n)+2p(n-1)+\cdots+np(1)+(n+1)p(0) \tag1$$ where $p(n)$ is the number of partitions of $n$.

For $a(n)$: each partition with three types of $1$'s corresponds to a partition of $k$ together with $(n-k)$ parts from $\{1',1''\}$. This second gadget can be chosen in $(n-k+1)$ ways, so we get $a(n)=\sum_{k=0}^n p(k)(n-k+1)$.

For $b(n+1)$: Let us count the number of times that a summand "$k$" appears, for $1\le k\le n+1$. It only appears in partitions that have at least one part equal to $k$. The number of such partitions is $p(n+1-k)$. So the total sum calculating $b(n+1)$ is $\sum_{k=1}^{n+1}kp(n+1-k)$.

Remark. The origin of (1) is this: $\frac1{1-x}\prod_{k\geq1}\frac1{1-x^k}=\sum_{m\geq0}\sum_{k=0}^mp(k)x^n$ and hence $\frac1{(1-x)^2}\prod_{k\geq}\frac1{1-x^k}=\sum_{n\geq0}\sum_{m=0}^n\sum_{k=0}^mp(k)x^n$. Furthermore, $$\sum_{m=0}^n\sum_{k=0}^mp(k)=(1).$$

Answer 2

For what it's worth, here is a non-combinatorial proof.

That $\frac{1}{(1-x)^2}\prod_{k=1}^{\infty} \frac{1}{1-x^k}$ is the generating function for partitions of $n$ with three flavors of $1$'s is clear.

So I will focus on the sum of all the irredundant parts of partitions of $n$. Let me use $||\lambda||$ to denote this sum of irredundant parts (in contrast to $|\lambda|$ which is the usual size).

By basic combinatorial reasoning we have $$\begin{align}\sum_{\lambda} q^{||\lambda||} x^{|\lambda|} &= (1+qx+qx^2+\cdots)(1+q^2x^2+q^2x^4+\cdots)(1+q^3x^3+q^3x^6+\cdots)\cdots \\ &= \left(\frac{q}{1-x}+(1-q)\right)\left(\frac{q^2}{(1-x^2)}+(1-q^2)\right)\left(\frac{q^3}{(1-x^3)}+(1-q^3)\right)\cdots \\ &= \frac{1+x(q-1)}{(1-x)} \cdot \frac{1+x^2(q^2-1)}{(1-x^2)} \cdot \frac{1+x^3(q^3-1)}{(1-x^3)} \cdots \\ &= \frac{\prod_{k=1}(1+x^k(q^k-1))}{\prod_{k=1}^{\infty}(1-x^k)}. \end{align} $$

Hence $\sum_{\lambda} ||\lambda|| \cdot x^{|\lambda|} $ is what we get from the above generating function by taking the derivative with respect to $q$ and setting $q:=1$. So let $f_k(q,x)=1+x^k(q^k-1)$. Being a little fast and loose with analytic issues, we can apply the "infinite product rule" to conclude $$ \begin{align} \sum_{\lambda} ||\lambda|| \cdot x^{|\lambda|} &= \frac{\sum_{k=1}^{\infty} \partial/\partial q f_k(x,q) \mid_{q=1} \cdot \prod_{i\neq k}f_i(x,q)\mid_{q=1}}{\prod_{k=1}^{\infty}(1-x^k)} \\ &=\frac{\sum_{k=1}^{\infty} (kx^kq^{k-1}) \mid_{q=1} \cdot \prod_{i\neq k}(1+x^i(q^i-1))\mid_{q=1}}{\prod_{k=1}^{\infty}(1-x^k)}\\ &= \frac{\sum_{k=1}^{\infty} kx^k}{\prod_{k=1}^{\infty}(1-x^k)} \\ &= \frac{x}{(1-x)^2} \cdot \prod_{k=1}^{\infty}\frac{1}{(1-x^k)}, \end{align}$$ exactly as claimed (with the extra power of $x$ reflecting the $n+1$ in $b(n+1)$).