Let $a(n,k)$ be the sequence of $k$-Dowling numbers (for more information see [A007405](https://oeis.org/A007405) and its *CROSSREFS* section) with e.g.f.
$$\operatorname{exp}\left(x + \frac{\operatorname{exp}(kx) - 1}{k}\right)$$
Let
$$\ell(n)=\left\lfloor\log\_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$
$$T(n,k)=\left\lfloor\frac{n}{2^k}\right\rfloor\operatorname{mod}2$$
Here $f(n)$ is the same as $n$ without the most significant bit and $T(n,k)$ is the $(k+1)$-th bit from the right side in the binary representation of $n$.


Let $b(n,m,k)$ be an integer sequence such that
$$b(n,m,k)=mb(f(n),m,k)+\sum\limits\_{j=0}^{\ell(n)} k(1-T(n,j))b(f(n)+2^j(1-T(n,j)),m,k)$$
Here $b(n,1,1)$ is [A341392](https://oeis.org/A341392).


Let $s(n,m,k)$ be an integer sequence such that
$$s(n,m,k)=\sum\limits\_{j=0}^{2^n-1}b(j,m,k)$$
I conjecture that
$$s(n,1,k)=a(n,k)$$
I also conjecture that e.g.f. for $s(n,m,k)$ is
$$\operatorname{exp}(x + m\frac{\operatorname{exp}(kx) - 1}{k})$$
Here is the PARI prog to verify these conjectures:



```
s(n, m, k)=my(v, v1); v=vector(2^n, i, 0); v[1]=1; for(i=1, #v-1, my(L=logint(i, 2), A=i-2^L); v[i+1]=m*v[A+1] + sum(j=0, L, my(B=bittest(i, j)); k*(1-B)*v[A + 2^j*(1-B) + 1])); v1=[1]; for(i=1, n, v1=concat(v1, sum(j=0, 2^i-1, v[j+1]))); v1
[n, m, k]=[10, 1, 2]
x=s(n, m, k)
z='z+O('z^(n+1)); x1=Vec(serlaplace(exp(z + m*(exp(k*z) - 1)/k)))
test=x==x1

```

Is there a way to prove it?



Sequences that sum up to Dowling numbers
Cleaning up the notation a bit,


$$b\_{m,k}(n) = m\, b\_{m,k}(n-2^{\ell(n)}) + k \sum\_{j=0}^{\ell(n)-1} [n \,\&\, 2^j = 0] \,b\_{m,k}(n - 2^{\ell(n)} + 2^j)$$ where $\&$ is bitwise AND.
$$s\_{m,k}(n) = \sum\_{j=0}^{2^n-1} b\_{m,k}(j)$$




---


Let $\operatorname{wt}(n)$ be the Hamming weight of $n$, and for an arbitrary polynomial $p(z)$ define $$s\_{m,k}^p(n) = \sum\_{j=0}^{2^n-1} p(\operatorname{wt}(j)) b\_{m,k}(j)$$ This generalises $s\_{m,k} = s\_{m,k}^{z^0}$. The differences reduce nicely:


$$\begin{eqnarray\*}s\_{m,k}^p(n) - s\_{m,k}^p(n-1)
&=& \sum\_{j=2^{n-1}}^{2^n-1} p(\operatorname{wt}(j)) b\_{m,k}(j) \\
%&=& \sum\_{j=0}^{2^{n-1}-1} p(\operatorname{wt}(2^{n-1} + j)) b\_{m,k}(2^{n-1} + j) \\
&=& \sum\_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b\_{m,k}(2^{n-1} + j) \\
%&=& \sum\_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \left( m\, b\_{m,k}(j) + k \sum\_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b\_{m,k}(j + 2^i) \right) \\
&=& m \sum\_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) b\_{m,k}(j) + k \sum\_{j=0}^{2^{n-1}-1} p(1 + \operatorname{wt}(j)) \sum\_{i=0}^{n-2} [j \,\&\, 2^i = 0] \,b\_{m,k}(j + 2^i) \\
%&=& m s\_{m,k}^{E\_z p}(n-1) + k \sum\_{j=0}^{2^{n-1}-1} \sum\_{i=0}^{n-2} [j \,\&\, 2^i = 0] p(\operatorname{wt}(j + 2^i)) b\_{m,k}(j + 2^i) \\
%&=& m s\_{m,k}^{E\_z p}(n-1) + k \sum\_{j=0}^{2^{n-1}-1} \operatorname{wt}(j) p(\operatorname{wt}(j)) b\_{m,k}(j) \\
&=& m s\_{m,k}^{E\_z p}(n-1) + k s\_{m,k}^{zp}(n-1) \\
\end{eqnarray\*}$$ where $E\_z$ is the raising operator $(E\_z p)(z) = p(z+1)$.


With the base case $s\_{m,k}^p(0) = p(0)$, we get $s\_{m,k}(n) = (1 + mE\_z + kz)^n z^0 \mid\_{z=0}$.




---


Two useful subresults towards the main proof:


**Theorem**: $(mE\_z + kz)^d z^0 \mid\_{z=0} = \sum\_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$ where $\genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$ is a Stirling number of the second kind.


By induction.


* In the base case, $d=0$, we have $1 = \genfrac{\lbrace}{\rbrace}{0pt}{}{0}{0}$.
* Note that by repeated application of $E\_z z = (z+1)E\_z$ we can rewrite $(mE\_z + kz)^d$ as $\sum\_{i=0}^d k^{d-i} m^i q\_{k,m}(z) E\_z^m$ where the $q\_{k,m}$ are polynomials. Then $(mE\_z + kz)^d z^0 \mid\_{z=0} = \sum\_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i$ is equivalent to $\forall i \in [0,d]: q\_{d-i,i}(0) = \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i}$. Now we multiply on the right to get $$\begin{eqnarray\*}(mE\_z + kz)^{d+1}
&=& \sum\_{i=0}^d k^{d-i} m^i q\_{k,m}(z) E\_z^m (mE\_z + kz) \\
&=& \sum\_{i=0}^d k^{d-i} m^{i+1} q\_{k,m}(z) E\_z^{m+1} + k^{d-i+1} m^i q\_{k,m}(z)(z+m) E\_z^m \\
\end{eqnarray\*}$$ so $q\_{k,m}(0) = q\_{k,m-1}(0) + k q\_{k-1,m}(0)$ $= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m-1} + k \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m-1}{m}$ $= \genfrac{\lbrace}{\rbrace}{0pt}{}{k+m}{m}$.


**Theorem**: $(\exp(z)-1)^i = \sum\_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n$


Surely standard. By induction: $(\exp(z)-1)^0 = 1 = \sum\_{n \ge 0} \frac{0!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{0} z^n$ checks out, and $$\begin{eqnarray\*}\left(\sum\_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)(\exp(z)-1)
&=& \left(\sum\_{n \ge i} \frac{i!}{n!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i} z^n\right)\left( \sum\_{j \ge 1} \frac{1}{j!} z^j\right) \\
&=& \sum\_{n \ge i+1} z^n \sum\_{j=1}^n \frac{i!}{(n-j)!j!} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\
&=& \sum\_{n \ge i+1} \frac{i!}{n!} z^n \sum\_{j=1}^n \binom{n}{j} \genfrac{\lbrace}{\rbrace}{0pt}{}{n-j}{i} \\
\end{eqnarray\*}$$


The inner sum counts pointed partitions of $n$ items into $i+1$ sets, so equals $(i+1) \genfrac{\lbrace}{\rbrace}{0pt}{}{n}{i+1}$, completing the proof.




---


**Theorem**: $\sum\_{n \ge 0} \frac{s\_{m,k}(n)x^n}{n!} =
\exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$


For the LHS we have $$\begin{eqnarray\*}\sum\_{n \ge 0} \frac{s\_{m,k}(n)x^n}{n!}
&=& \sum\_{n \ge 0} \frac{x^n}{n!} \sum\_{d=0}^n \binom{n}{d} \sum\_{i=0}^d \genfrac{\lbrace}{\rbrace}{0pt}{}{d}{i} k^{d-i} m^i \\
&=& \sum\_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j
\end{eqnarray\*}$$


For the RHS we have \begin{eqnarray\*}\exp\left(x + m\frac{\exp(kx) - 1}{k}\right)
&=& \exp\left(x + mx\frac{\exp(kx) - 1}{kx}\right) \\
&=& \sum\_{u \ge 0} \frac{x^u}{u!} \left(1 + m\frac{\exp(kx) - 1}{kx}\right)^u \\
&=& \sum\_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i (\exp(kx) - 1)^i \\
&=& \sum\_{u,i \ge 0} \frac{x^u}{u!} \binom{u}{i} \left(\frac{m}{kx} \right)^i \sum\_{v \ge i} \frac{i!}{v!} \genfrac{\lbrace}{\rbrace}{0pt}{}{v}{i} (kx)^v \\
&=& \sum\_{n,i,j \ge 0} \frac{1}{n!} \binom{n}{i+j} \genfrac{\lbrace}{\rbrace}{0pt}{}{i+j}{i} x^n m^i k^j 
\end{eqnarray\*}
where the final line uses the substitutions $j = v-i$ and $n = u+j$.




---


Finally, note that the operator expression for $s\_{m,k}$ gives the elegant formulation of the main theorem as $$\exp(x(1 + mE\_z + kz)) z^0 \mid\_{z=0} = \exp\left(x + m\frac{\exp(kx) - 1}{k}\right)$$


