- Let
$$ T(n,k,p,q,r,s) = (q(k-1)+1)T(n-1,k,p,q,r,s) + s(n+r(k-1)+p-2)T(n-1,k-1,p,q,r,s), \\ T(n,1,p,q,r,s) = 1, \\ T(n,0,p,q,r,s) = T(0,k,p,q,r,s) = 0 $$
- Let
$$ \ell(n) = \left\lfloor\log_2 n\right\rfloor $$
- Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). Here
$$ \operatorname{wt}(2n+1) = \operatorname{wt}(n) + 1, \\ \operatorname{wt}(2n) = \operatorname{wt}(n), \\ \operatorname{wt}(0) = 0 $$
- Let
$$ R(n,k) = \left\lfloor\frac{n}{2^k}\right\rfloor\bmod 2 $$
Here $R(n,k)$ is the $(k+1)$-th bit from the right side in the binary expansion of $n$.
- Let
$$ b(n,p,q,r,s) = s(\ell(n)+r\operatorname{wt}(n)+p)b(n-2^{\ell(n)},p,q,r,s) + q\sum\limits_{k=0}^{\ell(n)-1} (1-R(n,k))b(n-2^{\ell(n)}+2^k(1-R(n,k)),p,q,r,s), \\ b(0,p,q,r,s) = 1 $$
I conjecture that
$$ \sum\limits_{i=0}^{2^n-1}b(i,p,q,r,s) = \sum\limits_{k=1}^{n+1} T(n+1,k,p,q,r,s). $$
Here is the PARI/GP program to check it numerically:
upto1(n,p,q,r,s) = my(v1); v1 = vector(2^n, i, 0); v2 = vector(n, i, 0); v1[1] = 1; for(i=1, 2^n-1, my(L = logint(i,2), A = i - 1 << L); v1[i+1] = s*(L+r*hammingweight(i)+p)*v1[A+1] + q*sum(j=0, L-1, my(B = !bittest(i, j)); B*v1[A + B << j + 1])); for(i=1, n, v2[i] = sum(j=2^(i-1), 2^i - 1, v1[j+1])); v2[1]++; for(i=2, n, v2[i] += v2[i-1]); v2 = concat(1, v2)
upto2(n,p,q,r,s) = my(v1); v1 = vector(n+1, i, 0); v1[1] = 1; v2 = v1; for(i=2, n+1, v1 = vector(n+1, j, if(j==1, 1, (q*(j-1)+1)*v1[j] + s*(i+r*(j-1)+p-2)*v1[j-1])); v2[i] = vecsum(v1)); v2
test(n,p,q,r,s) = upto1(n,p,q,r,s) == upto2(n,p,q,r,s)
Is there a way to prove it?
