On a number of compositions of $n$ into positive triangular numbers

Question

• Let $a(n)$ be A023361 (i.e., number of compositions of $n$ into positive triangular numbers). Here $$ a(n) = \sum\limits_{i \geqslant 1, \frac{i(i+1)}{2}\leqslant n} a(n-\frac{i(i+1)}{2}), \\ a(0) = 1. $$
• Start with vector $\nu$ of fixed length $m$ with elements $\nu_i=1$ (that is, $\nu = \{1, 1, \dotsc, 1\}$) and for $i$ from $1$ to $m-1$ and for $j$ from $i+1$ to $m$ apply $\nu_j := \nu_i + z^{j-i}\nu_j$.
• Let $T(n, k)$ be a triangle read by rows for $0 \leqslant k \leqslant \frac{n(n-1)}{2}$ with $n$-th row polynomial equals $\nu_n$.

I conjecture that antidiagonal sums of $T(n,k)$ equal $a(n)$. In other words, $$a(n) = \sum\limits_{k \geqslant 0} T(n-k, k).$$

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

upto1(n) = my(v1); v1 = vector(n, i, 1); for(i=1, n-1, for(j=i+1, n, v1[j] = v1[i] + z^(j-i)*v1[j])); v1
upto2(n) = my(v1); v1 = vector(n+1, i, 0); v1[1] = 1; for(i=1, n, my(A = 1, B = 1, C = 0); while(B<=i, C += v1[i-B+1]; A++; B += A); v1[i+1] = C); v1
upto3(n) = my(v1, v2); v1 = upto1(n); v1 = vector(n, i, Vecrev(v1[i])); v2 = vector(n+1, i, 0); v2[1] = 1; for(i=1, n, my(A = 1, B = 0); until((i-A+1)<1 || #v1[i-A+1]<A, B += v1[i-A+1][A]; A++); v2[i+1] = B); v2
test1(n) = upto2(n) == upto3(n)

Is there a way to prove it?

Answer 1

Let $v_{i,j}(z)$ be the value of $\nu_j$ after round $i$, with initial values $v_{0,j}(z) = 1$ for all $j\geq 1$. Consider the generating function: $$F(x,y,z) := \sum_{i\geq 0} x^i \sum_{j\geq i+1} y^{j-i-1} v_{i,j}(z).$$ The rounds of updating values of $\nu_j$ translates into the following functional equation: $$F(x,y,z) = \frac1{1-y} + \frac{x(2y-1)}{y(1-y)} F(x,0,z) + \frac{x}{y}F(x,yz,z).$$ We have $T(n,k) = [x^{n-1} y^0 z^k] F(x,y,z)$, and thus $$\sum_{n\geq 1} x^{n-1} \sum_{k\geq 0} T(n-k,k) = G(x,0),$$ where $G(x,y) := F(x,y,x)$. Correspondingly, it satisfies the equation: $$G(x,y) = \frac1{1-y} + \frac{x(2y-1)}{y(1-y)} G(x,0) + \frac{x}{y}G(x,xy).$$

Extracting the coefficient of $y^k$ for any $k\geq 0$, we have $$[y^k]\ G(x,y) = 1 + x G(x,0) + x^{k+2} [y^{k+1}]\ G(x,y),$$ which enables iterative unrolling \begin{split} G(x,0) &= [y^0]\ G(x,y) = 1 + x G(x,0) + x^2 [y^1]\ G(x,y) \\ & = (1+x^2) (1 + x G(x,0)) + x^{2+3} [y^2]\ G(x,y) \\ & = (1+x^2 + x^{2+3}) (1 + x G(x,0)) + x^{2+3+4} [y^3]\ G(x,y) \\ & = (1+xG(x,0))\sum_{k\geq 1} x^{T_k-1}, \end{split} where $T_k:=\frac{k(k+1)}2$ is the $k$-th triangular number. Then $$G(x,0) = \frac{\sum_{k\geq 1} x^{T_k-1}}{1-\sum_{k\geq 1} x^{T_k}} = \frac1x\sum_{\ell\geq 1} \bigg(\sum_{k\geq 1} x^{T_k}\bigg)^\ell,$$ implying that $[x^{n-1}]\ G(x,0) = a(n)$. QED