Let $a(n,k)$ be the sequence of $k$-Dowling numbers (for more information see 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.

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)))

Is there a way to prove it?


1 Answer 1


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)$$


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.