13
$\begingroup$

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

$\endgroup$
3

2 Answers 2

18
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you, as always. I enjoyed this. $\endgroup$ Nov 11, 2021 at 15:13
  • 1
    $\begingroup$ I have added a remark to help the reader. Hope it is okay with you. If not, you may delete it. $\endgroup$ Nov 12, 2021 at 17:11
6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Possibly these generating function manipulations could be made bijective, but I'll leave that task to someone else... $\endgroup$ Nov 10, 2021 at 23:46
  • $\begingroup$ By the way, another interesting partition identity obtained by differentiation of generating functions is discussed here: mathoverflow.net/questions/127000/…. It has a nice bijective proof due to Erdös (see the link). $\endgroup$ Nov 11, 2021 at 0:58
  • $\begingroup$ Thank you, Sam, for your continual prompt responses. Upvoted. $\endgroup$ Nov 11, 2021 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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