Algorithm for the sum with binomial coefficients and Bell numbers

Question

• Let $a(n)$ be A000110 (i.e., Bell or exponential numbers: number of ways to partition a set of $n$ labeled elements).
• Let $b(n)$ be A355247 (i.e., expansion of exponential generating function $\exp(2(\exp(x) + x - 1))$). Here $$ b(n) = \sum\limits_{k=0}^{n}\binom{n}{k}a(k+1)a(n-k+1). $$
• Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = z^{i-1}$ (that is, $\nu = \{1, z, z^2, \dotsc, z^{m-1}\}$) and for $i$ from $1$ to $m-1$ and for $j$ from $i+1$ to $m$ apply $$ \nu_j := \nu_j + \sum\limits_{k=0}^{j-1}z^k[z^{j-k-1}](\nu_j + (j-i)z\nu_{j-1}). $$

I conjecture that after the whole transform we have $$ [z^n]\nu_{n+1} = b(n-1). $$

Here is the PARI/GP program to check it numerically:

upto1(n) = my(v1); v1 = vector(n+1, i, sum(j=1, i, stirling(i, j, 2))); v2 = vector(n+1, i, 0); v2[1] = 1; for(i=1, n, v2[i+1] = sum(k=0, i, binomial(i, k)*v1[k+1]*v1[i-k+1])); v2
upto2(n) = my(A, v1); v1 = vector(n, i, z^(i-1)); for(i=1, n-1, for(j=i+1, n, A = v1[j] + z*(j-i)*v1[j-1]; v1[j] += sum(k=0, j-1, z^k*polcoeff(A, j-k-1, z)))); v1
upto3(n) = my(v1); v1 = upto2(n+1); v1 = vector(n, i, polcoeff(v1[i+1], i, z))
test1(n) = upto1(n) == upto3(n+1)

Is there a way to prove it?

Answer 1

It is convenient to view the sum $\sum_{k=0}^{j-1} z^k[z^{j-1-k}] f(z)$ as the linear "reciprocal" operator $R_{j-1}(f(z)) := z^{j-1} f(z^{-1})$, which turns a polynomial of degree $j-1$ into its reciprocal polynomial. In our process, each $R_{j-1}$ is applied to a polynomial of degree $j-1$ and results in a polynomial of degree $j-1$.

Ultimately we concern only the coefficient of the highest degree $z^n$ in $v_{n+1}$, which depends only the coefficients of $z^{j-1}$ and $z^0$ (ie. highest and lowest terms) in $v_j$ for $j<n$. Hence, we can focus only on those coefficients.

Let $c_{i,j} + b_{i,j}z^{j-1}$ be the sum of the constant and the leading terms of $v_j$ after round $i$. We have $c_{0,j} = 0$ and $b_{0,j}=1$.

From the transformation in the round $i$, we have $(b_{i,j},c_{i,j})=(b_{i-1,j},c_{i-1,j})$ for $j\leq i$, while for $j>i$ \begin{cases} b_{i,j} = c_{i-1,j}+b_{i-1,j},\\ c_{i,j} = c_{i-1,j}+b_{i-1,j} + (j-i) b_{i,j-1} \end{cases} It implies that for $i\geq 2$ $$b_{i,j} = 2b_{i-1,j} + (j-i+1) b_{i-1,j-1}.$$

Correspondingly, for the generating function $$B(x,y) := \sum_{i\geq 1} \frac{x^{i-1}}{(i-1)!} \sum_{j\geq i+1} \frac{y^{j-i-1}}{(j-i-1)!}b_{i,j}$$ we have a PDE: $$y\frac{\partial}{\partial x}B(x,y) = 2y\frac{\partial}{\partial y}B(x,y) + \frac{\partial}{\partial y}\big(y^2B(x,y)\big)$$ with the boundary condition $B(0,y)=\exp(y)$. Its solution is $$B(x, y) = \exp((y + 2) \exp(x) + 2 x - 2).$$ Hence, $$B(x, 0) = \exp(2\exp(x) + 2 x - 2),$$ which matches the generating function for A355247. QED