Let $a(n)$ be A002720, i.e., number of partial permutations of an $n$-set; number of $n \times n$ binary matrices with at most one $1$ in each row and column. $$a(n)=\sum\limits_{k=0}^{n} k!\binom{n}{k}^2$$ Now we need to introduce some functions which are related to binary expansion of $n$:
Let $\operatorname{wt}(n)$ be A000120, i.e., number of $1$'s in binary expansion of $n$ (or the binary weight of $n$). Here $$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1,\operatorname{wt}(2n)=\operatorname{wt}(n),\operatorname{wt}(0)=0$$ Let $$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$ Let $$f(n)=n-2^{\ell(n)}$$ Let $$g(2^k)=k, g(n)=g(\left\lfloor\frac{n}{2}\right\rfloor)$$ Let $$h(2^k-1)=0, h(n)=h(\left\lfloor\frac{n}{2}\right\rfloor)+1$$ Let $$s(n)=n+[h(n)>0]2^{h(n)-1}$$ Then we have an integer coefficients $T(n,k)$ given by $$T(0,1)=T(0,2)=1$$ $$T(0,k)=0, k>2$$ $$T(n,1)=1, n>0$$ $$T(n,k)=(\operatorname{wt}(f(n))+2)(g(n)+1)T(f(n),k-1)+T(s(f(n)),k)$$ I conjecture that $$\sum\limits_{k=0}^{2^n-1}\sum\limits_{j=1}^{\operatorname{wt}(k)+2}T(k,j)=2(n+1)a(n)$$ Is there a way to prove it?
