Let $m \geqslant 1$ be a fixed integer.


Let $f(n)$ be [A007814](https://oeis.org/A007814), exponent of highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.


Then we have an integer sequence given by
\begin{align}
a\_1(0)& = 1\\
a\_1(2n+1)& = a\_1(n)\\
a\_1(2n)& = a\_1(n-2^{f(n)})+a\_1(2n-2^{f(n)})
\end{align}
Here $a\_1(n)$ is [A243499](https://oeis.org/A243499), product of parts of integer partitions as enumerated in the table [A125106](https://oeis.org/A125106).


Let
$$a\_m(n) = \sum\limits\_{k=0}^{n}(\binom{n}{k}\operatorname{mod} 2)a\_{m-1}(k)$$
Also
$$s\_m(n)=\sum\limits\_{k=0}^{2^n-1}a\_m(k)$$
I conjecture that $s\_m(n)$ is Stirling transform of
$$1, m, m^2, m^3, \cdots$$
In other words
$$s\_m(n)=\exp(-m)\sum\limits\_{k=0}^{\infty}(k + 1)^n\frac{m^k}{k!}=\sum\limits\_{k=0}^{n}{n+1\brace k+1}m^k$$
Is there a way to prove it?



Modulo $2$ binomial transform of A243499 applied $k$ times
The definition of $a\_1$ given in OEIS is based on a bijection between integer partitions and natural numbers. A partition $\lambda\_1\geq\lambda\_2\geq\dots\geq\lambda\_m>0$ with exactly $m$ parts corresponds to the number
$$2^{\lambda\_1+m-2}+2^{\lambda\_2+m-1}+\dots+2^{\lambda\_m-1}.$$
The definition of $a\_1$ can then be written as
\begin{equation}\label{a1d}(1)\qquad a\_1\left(2^{\lambda\_1+m-2}+2^{\lambda\_2+m-1}+\dots+2^{\lambda\_m-1}\right)=\lambda\_1\dotsm\lambda\_m.\end{equation}


When $n$ is a natural number, I will write $\|n\|$ for the number of ones in the binary expansion of $n$, and $n\preceq m$ if all binary digits in $n$ are smaller than or equal to those in $m$. It is well-known that $\binom nk\,\operatorname{mod}\,2=1$ if and only if $k\preceq n$. It is easy to see from this that
$$a\_m(n)=\sum\_{k\preceq n}(m-1)^{\|n-k\|}a\_1(k).$$
Roughly speaking, we go from $k$ to $n$ by changing zeroes to ones, and for each of the $\|n-k\|$ zeroes we can choose to change it in any one of $m-1$ binomial transforms.


The final ingredient is the identity
$$\left\{\array{k+l\\l}\right\}=\sum\_{l\geq \lambda\_1\geq\lambda\_2\geq\dots\geq\lambda\_k> 0}\lambda\_1\lambda\_2\dotsm\lambda\_k.$$
Probably this is well-known. I verified it using induction; just let me know if you need more explanation. By (1), this can be written
\begin{equation}\label{sa}(2)\qquad\left\{\array{k+l\\l}\right\}=\sum\_{0\leq j<2^{l+k-1},\,\|j\|=k}a\_1(j).\end{equation}


We now have all ingredients we need. We have
$$s\_m(n)=\sum\_{0\leq k<2^n}a\_m(k)=\sum\_{0\leq k<2^n}\sum\_{l\preceq k}(m-1)^{\|k-l\|}a\_1(l).$$
For fixed $l$ and $j=\|k-l\|$, we obtain $k$ by choosing $j$ from $n-\|l\|$ zeroes in $l$ and changing them to ones. Thus, we can write
$$s\_m(n)=\sum\_{0\leq l<2^n}a\_1(l)\sum\_{j}\binom{n-\|l\|}{j}(m-1)^{j}
=\sum\_{0\leq l<2^n}a\_1(l)m^{n-\|l\|}.$$
Writing this as a sum over $k=n-\|l\|$ and using (2) gives indeed
$$s\_m(n)=\sum\_{k=0}^n m^k\left\{\array{n+1\\k+1}\right\}.
$$


