2
$\begingroup$

$\DeclareMathOperator\wt{wt}$Let $\wt(n)$ be A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$).

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.

Also $$n=2^{t_1}(1+2^{t_2+1}(1+\dotsb(1+2^{t_{wt(n)}+1}))\dotsb).$$ Then we have an integer sequence given by $$a(n)=\sum\limits_{j=0}^{2^{\wt(n)}-1}(-1)^{\wt(n)-\wt(j)}\prod\limits_{k=0}^{\wt(n)-1}\left(1+f\left(\left\lfloor\frac{j}{2^k}\right\rfloor+1\right)\right)^{t_{k+1}+1},\quad a(0)=1.$$ Let $$s(n)=\sum\limits_{k=0}^{2^n-1}a(k).$$ Then I conjecture that $s(n)$ is A095989, INVERTi transform applied to the ordered Bell numbers.

I also conjecture that \begin{align} a(0)=a(1)&=1\\ a(2n+1) &= a(2n)\\ a(2n)& = a(n)+a(2n-2^{f(n)})+b(n-1)\\ b(2n+1) &= b(n)\\ b(2n) &= a(2n). \end{align} In other words \begin{align} a(2n) &= c(n)\\ c(0)&=1\\ c(n)& = c\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+c\left(\left\lfloor\frac{2n-2^{f(n)}}{2}\right\rfloor\right)+c(g(n-1)) \end{align} where $g(n)$ is A025480, $g(2n) = n$, $g(2n+1) = g(n)$.

Is there a way to prove it? Is it possible to at least get a closed form for $s(n)$?

Similar questions:

$\endgroup$

1 Answer 1

2
$\begingroup$

First, we let $P(j,k):=1+f(\lfloor\tfrac{j}{2^k}\rfloor+1)$ and sum over $n$ of fixed weight $\ell:=\mathrm{wt}(n)$ (like in this answer): \begin{split} s(n) &= \sum_{\ell=0}^n \sum_{t_1 + \dots + t_\ell \leq n-\ell} \sum_{j=0}^{2^\ell-1} (-1)^{\ell-\mathrm{wt}(j)} \prod_{k=0}^{\ell-1} P(j,k)^{t_k+1} \\ &= [x^{n+1}]\ \sum_{\ell=0}^n \sum_{j=0}^{2^\ell-1} (-1)^{\mathrm{wt}(j)+1} \prod_{k=0}^{\ell} \frac{-P(j,k)x}{1-xP(j,k)}. \end{split}

Now, we notice that $P(j,k)$ depends on runs of unit bits in $j$. Namely, each run of length $u-1$ contributes the term $$\prod_{v=1}^{u} \frac{-vx}{1-vx} = x^{u} (-1)^{u} u! \prod_{v=1}^{u} \frac1{1-vx}.$$ Hence, introducing the number $z$ of zero bits in $j$ padded with an extra zero at the beginning (and so $\mathrm{wt}(j)=\ell+1-z$), we have \begin{split} s(n) &= [x^{n+1}]\ \sum_{\ell=0}^n [y^{\ell+1}]\ \sum_{z\geq 0} (-1)^{\ell+2-z} \left(\sum_{u\geq 1} y^u (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^z\\ &= -[x^{n+1}]\ \sum_{\ell=0}^n (-1)^{\ell+1} [y^{\ell+1}]\ \left(1+\sum_{u\geq 1} y^{u} (-1)^u x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \prod_{v=1}^u \frac1{1-vx}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{u\geq 1} x^u u! \sum_{m\geq 0} S(m,u) x^{m-u}\right)^{-1}\\ &=- [x^{n+1}]\ \left(1+\sum_{m\geq 1} x^m B_m^o\right)^{-1}, \end{split} which can be recognized as INVERTi transform of ordered Bell numbers $B_m^o$.

$\endgroup$

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.