# Modulo $2$ binomial transform of A243499 applied $k$ times

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

Let $$f(n)$$ be 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, product of parts of integer partitions as enumerated in the table 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?

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 $$$$\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.$$$$
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 $$$$\label{sa}(2)\qquad\left\{\array{k+l\\l}\right\}=\sum_{0\leq j<2^{l+k-1},\,\|j\|=k}a_1(j).$$$$
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\}.$$