- Let $T(n,k)$ be an integer coefficients (A358612) such that
$$ T(2n+1, k) = kT(n, k) + T(n, k-1), \\ T(2n, k) = kT(n, k) + T(n, k-1) - \frac{T(2n, k-1) + T(n, k-1)}{k-1}, \\ T(n, 1) = T(0, 2) = 1 $$
- Let
$$ \ell(n) = \left\lfloor\log_2 n\right\rfloor, \\ \ell(0) = -1 $$
- Let
$$ f(n) = \ell(n) - \ell(n-2^{\ell(n)}) - 1 $$
Here $f(n)$ is A290255.
Let $g(n)$ be A059893 (i.e., reverse the order of all but the most significant bit in binary expansion of n: if $n = 1ab\cdots yz$ then $g(n) = 1zy\cdots ba$).
Let
$$ R(n, k) = (k-1)^{f(n)}R(n-2^{\ell(n)}, k-1) + k^{f(n)+1}R(n-2^{\ell(n)}, k), \\ R(n, 1) = R(0, 2) = 1 $$
I conjecture that
$$ T(n, k) = R(g(n), k). $$
Note that it requires number of ones in the binary expansion of $n$ operations to compute $R(g(n), k)$ instead of length of binary expansion of $n$ operations to compute $T(n, k)$.
Here is the PARI/GP program to check it numerically:
row1(n) = my(A, v1, v2); v1 = [1, 1]; if(n == 0, v1, forstep(i=logint(n, 2), 0, -1, A = bittest(n, i); v2 = vector(#v1+A, i, 0); v2[1] = 1; for(j=2, #v2, v2[j] = j*if(j==#v1+1, 0, v1[j]) + v1[j-1] - if(A, 0, (v2[j-1] + v1[j-1])/(j-1))); v1 = v2); v1)
row2(n) = if(n == 0, [1, 1], my(L = logint(n, 2), A = n - 1 << L, B = L - if(A == 0, -1, logint(A, 2)) - 1, v1); v1 = row2(A); v1 = vector(#v1+1, j, if(j==1, 0, (j-1)^B*v1[j-1]) + if(j==(#v1+1), 0, j^(B+1)*v1[j])))
g(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2)
test(n) = row1(n) == row2(g(n))
Is there a way to prove it?
