Let $wt(n)$ be [A000120](https://oeis.org/A000120), number of $1$'s in binary expansion of $n$ (or the binary weight of $n$)
and
$$n=2^{t\_1}(1+2^{t\_2+1}(1+\dots(1+2^{t\_{wt(n)}+1}))\dots)$$
Then we have an integer sequence given by
$$a(n)=\sum\limits\_{j=0}^{2^{wt(n)}-1}m^{wt(n)-wt(j)}\prod\limits\_{k=0}^{wt(n)-1}(1+wt(\left\lfloor\frac{j}{2^k}\right\rfloor))^{t\_{k+1}+1}, a(0)=1$$
Let
$$s(n,m)=\sum\limits\_{k=0}^{2^n-1}a(k)$$
then I conjecture that for any $m$
$$s(n,m)=\sum\limits\_{k=0}^{n+1}k!{n+1\brace k}(m+1)^{n-k+1}$$
Is there a way to prove it?


Similar questions:


* [Recurrence for the sum](https://mathoverflow.net/questions/405174/recurrence-for-the-sum)
* [Pair of recurrence relations with $a(2n+1)=a(2f(n))$](https://mathoverflow.net/questions/406902/pair-of-recurrence-relations-with-a2n1-a2fn)
* [Sequence that sums up to INVERTi transform applied to the ordered Bell numbers](https://mathoverflow.net/questions/407290/sequence-that-sums-up-to-inverti-transform-applied-to-the-ordered-bell-numbers)
* [Sequences that sums up to second differences of Bell and Catalan numbers](https://mathoverflow.net/questions/407758/sequences-that-sums-up-to-second-differences-of-bell-and-catalan-numbers)



Sum with Stirling numbers of the second kind
The [same idea](https://mathoverflow.net/q/405210) of grouping terms by the number of unit bits, as well as grouping by the value of $\mathrm{wt}(j)$ (representing $j$ via individual bits) works here:
\begin{split}
s(n,m) &= \sum\_{\ell=0}^n \sum\_{t\_1 + \dots + t\_\ell \leq n-\ell} \sum\_{j\_1,\dots,j\_\ell\in\{0,1\}} m^{\ell-\sum\_{i=1}^\ell j\_i} \prod\_{k=1}^{\ell} (1+\sum\_{i=1}^k j\_i)^{t\_k+1} \\
&=[x^{n+1}]\ \sum\_{\ell=0}^n \sum\_{j\_1,\dots,j\_\ell\in\{0,1\}} m^{\ell-\sum\_{i=1}^\ell j\_i} \prod\_{k=0}^{\ell} \frac{(1+\sum\_{i=1}^k j\_i)x}{1-(1+\sum\_{i=1}^k j\_i)x} \\
&=[x^{n+1}]\ \sum\_{\ell=0}^n \sum\_{J=0}^\ell \sum\_{j\_1,\dots,j\_\ell\in\{0,1\}\atop j\_1+\dots+j\_\ell=J} m^{\ell-J} \prod\_{k=0}^{\ell} \frac{(1+\sum\_{i=1}^k j\_i)x}{1-(1+\sum\_{i=1}^k j\_i)x} \\
&=[x^{n+1}]\ \sum\_{\ell=0}^n \sum\_{J=0}^\ell m^{\ell-J} \sum\_{d\_0,d\_1,\dots,d\_J\geq 1\atop d\_0+d\_1+\dots+d\_J=\ell+1}\prod\_{k=1}^{J+1} \left(\frac{kx}{1-kx}\right)^{d\_k} \\
&=[x^{n+1}]\ \sum\_{\ell=0}^n m^{\ell+1}[y^{\ell+1}]\ \sum\_{J=0}^\ell \prod\_{k=1}^{J+1} \frac{kxy}{(1-kx-kxy)m} \\
&=[x^{n+1}]\ \sum\_{J=0}^n \prod\_{k=1}^{J+1} \frac{kx}{1-kx-kmx} \\
&=\sum\_{J=0}^n (J+1)!\ [x^{n-J}]\ \prod\_{k=1}^{J+1} \frac{1}{1-k(m+1)x} \\
&=\sum\_{J=0}^n (J+1)!\ (m+1)^{n-J} \left\{n+1\atop J+1\right\}.
\end{split}
It also shows that the summands in the last formula corresponds to fixed values of $\mathrm{wt}(j)=J$.


