Partition numbers as the specific sums of the A161511

Question

• Let $p(n)$ be A000041 i.e. number of partitions of $n$ (the partition numbers).

• Let $$ \ell(n)=\left\lfloor\log_2 n\right\rfloor $$

• Let $a(n)$ be A161511 i.e. number of $1\cdots0$ pairs in the binary representation of $2n$.

The sequence begins with $$ 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 6, 5, 6, 4, 5, 5, 6, 5, 7, 6 $$

• Let $$ b(n) = a(n) + \ell(n) + 2, \\ b(0) = 0 $$

• Let $$ f(n) = 2^{\left\lfloor\frac{n}{2}\right\rfloor - 1} - 1, \\ f(1) = f(2) = f(3) = 1 $$

• Let $$ s(n) = \sum\limits_{i=0}^{f(n)}[b(i)<n](n-b(i)) $$

I conjecture that $$s(n) = p(n).$$

Here is the PARI/GP program to check it numerically:

b1(n) = my(b=binary(n)); b*-[-#b..-1]~;
a(n) = if(n == 0, 0, b1(n) - binomial(hammingweight(n), 2))
b(n) = if(n == 0, 0, a(n) + logint(n, 2) + 2)
f(n) = if(n \ 2 < 2, 1, 2 ^ (n \ 2 - 1) - 1)
s(n) = sum(i = 0, f(n), my(A = b(i)); if(A >= n, 0, n - A))
test(n) = s(n) == numbpart(n)

Is there a way to prove it?

Answer 1

If $2m=2^{j_1}+2^{j_2}+\ldots+2^{j_k}$ for $0<j_1<j_2<\ldots<j_k$, then $\ell(m)=j_k-1$, $a(m)=j_1+(j_2-1)+(j_3-2)+\ldots+(j_k-(k-1))$, as the $i$-th (from the left) 1 in the binary expansion of $2m$ participates in $j_i-(i-1)$ pairs $1\cdots 0$. Using the bound $j_i\geqslant i$ for all $i=1,2,\ldots,k-1$ we get $a(m)\geqslant j_k$ and therefore $b(m)=a(m)+\ell(m)+2\geqslant 2j_k+1.$ If $m>f(n)$, that is, $m\geqslant 2^{\left\lfloor\frac{n}{2}\right\rfloor - 1}$, then $2m\geqslant 2^{\left\lfloor\frac{n}{2}\right\rfloor}$, hence $j_k\geqslant \lfloor\frac{n}2\rfloor\geqslant \frac{n-1}2$ and $b(m)\geqslant 2j_k+1\geqslant n$. This shows that the summation up to $i=f(n)$ in the definition of $s(n)$ may be replaced to a summation up to infinity. Next, in above notations we have $$ n-b(m)=n-(j_1+(j_2-1)+(j_3-2)+\ldots+(j_k-(k-1)))-(j_k+1) \\=n-(w_1+\ldots+w_k)-(w_k+k), $$ where $w_i=j_i-(i-1)$ for $i=1,\ldots,k$ and $0<w_1\leqslant w_2\leqslant \ldots \leqslant w_k$. So, $w=(w_1,\ldots,w_k)$ is a partition, $k$ is the number of parts in $w$ (denote it $k=A(w)$), $w_k$ is the maximal part in $w$ (denote in $w_k=M(w)$). Thus, your claim reads as $$ \sum_w \max(n-|w|-A(w)-M(w),0)=p(n). $$ This has the following bijective proof. Take a partition $w$ for which $|w|+A(w)+M(w)\leqslant n-1$. Add 1 to all $A(w)$ parts (now the maximal part equals $M(w)+1$) and after that take an additional part equal to $M(w)+1$ (what happens is easier to understand drawing Young diagrams). You get a partition of the number $|w|+A(w)+M(w)+1$. To get a partition of $n$, add $n-|w|-A(w)-M(w)-1$ boxes arbitrarily to the first row or to the first column (so, you are allowed to add several 1's and increase the maximal part, so that the sum of parts becomes equal to $n$). There are exactly $n-|w|-A(w)-M(w)$ ways to do this. And you get each Young diagram with $n$ boxes exactly once.