#Column formulas for A358628
This page is part of the OEIS proof collection.
The square array A358628 is defined by \[A(i,j)\coloneqq \sum_{\substack{X,Y\in\setN^j\\ |X|,|Y|\leq i}} \prod_{k=1}^j(1+X_k+Y_k).\] We prove the conjectured generating function for each column and the conjectured polynomial factorization in the first index.
Theorem
For \(i,j\geq0,\) \[A(i,j)=[x^iy^i]\frac{(1-xy)^j} {(1-x)^{2j+1}(1-y)^{2j+1}}.\] Consequently, the generating function of column \(j\) is \[\sum_{i\geq0}A(i,j)t^i =\frac{\displaystyle\sum_{k=0}^{2j}\binom{2j}{k}^2t^k} {(1-t)^{3j+1}}.\] Equivalently, \[\begin{aligned} A(i,j) &=\sum_{m=0}^j(-1)^m\binom jm \binom{i-m+2j}{2j}^2\\ &=\sum_{k=0}^{2j}\binom{2j}{k}^2 \binom{i+3j-k}{3j}. \end{aligned}\]
Proof
The summand factors over the coordinates, and \[\sum_{a,b\geq0}(1+a+b)x^ay^b =\frac{1-xy}{(1-x)^2(1-y)^2}.\] The two bounds \(|X|,|Y|\leq i\) contribute the partial-sum factor \(1/((1-x)(1-y)).\) Extracting \([x^iy^i]\) gives the first formula.
Expanding \((1-xy)^j\) and taking the diagonal gives \[\sum_{i\geq0}A(i,j)t^i =(1-t)^j\sum_{n\geq0}\binom{n+2j}{2j}^2t^n =(1-t)^j\,{}_2F_1(2j+1,2j+1;1;t).\] Euler’s hypergeometric transformation changes the last expression to \[(1-t)^{-3j-1}\,{}_2F_1(-2j,-2j;1;t) =\frac{\sum_{k=0}^{2j}\binom{2j}{k}^2t^k} {(1-t)^{3j+1}}.\] Coefficient extraction from the two displayed forms gives the alternating and subtraction-free formulas for \(A(i,j).\)
The subtraction-free formula has an Ehrhart interpretation. Let \[\mathcal P_j\coloneqq \left\{(x,y,s)\in\setR_{\geq0}^{3j}: \sum_kx_k\leq1,\quad \sum_ky_k\leq1,\quad s_k\leq x_k+y_k\text{ for all }k\right\}.\] For fixed lattice points \(X,Y\) in the two simplices, there are \(\prod_k(1+X_k+Y_k)\) choices of integers \(0\leq s_k\leq X_k+Y_k.\) Hence \[A(i,j)=\#(i\mathcal P_j\cap\setZ^{3j}).\] The defining matrix of \(\mathcal P_j\) is totally unimodular: after changing row signs, its nontrivial columns form a directed node-edge incidence matrix. Thus \(\mathcal P_j\) is a \(3j\)-dimensional lattice polytope, and its \(h^*\)-polynomial is \[N_{2j}(t)\coloneqq\sum_{k=0}^{2j}\binom{2j}{k}^2t^k.\] In particular, its normalized volume is \(N_{2j}(1)=\binom{4j}{2j}.\)
These numerator polynomials are transformed Legendre polynomials: \[N_m(t)=(1-t)^mP_m\!\left(\frac{1+t}{1-t}\right),\] where \(P_m\) is the \(m\)th Legendre polynomial. Their zeros are therefore negative and simple. Transporting the Legendre recurrence also gives \[(m+1)N_{m+1}(t) =(2m+1)(1+t)N_m(t)-m(1-t)^2N_{m-1}(t).\] Thus every column \(h^*\)-vector is real-rooted, log-concave, and unimodal.
Corollary
For every \(j\geq0\) there is a polynomial \(p_j(i)\) of degree \(j\) such that \[A(i,j)=\binom{i+j}{j}^2p_j(i).\] Its leading coefficient is \[\frac{\binom{4j}{2j}j!^2}{(3j)!},\] and it satisfies the reciprocity relation \[p_j(-i-j-1)=(-1)^jp_j(i).\]
Proof
Regard the alternating formula for \(A(i,j)\) as a polynomial in \(i.\) For \(1\leq s\leq j\) and \(0\leq m\leq j,\) the product \[\binom{i-m+2j}{2j} =\frac{\prod_{\ell=1}^{2j}(i-m+\ell)}{(2j)!}\] vanishes at \(i=-s,\) since \(1\leq s+m\leq2j.\) Every summand therefore has a double zero at each of \(-1,-2,\dotsc,-j.\) This proves divisibility by \(\binom{i+j}{j}^2.\)
The column generating function has numerator \(N_{2j}(1)=\binom{4j}{2j}\neq0\) at \(t=1.\) Hence \(A(i,j)\) has degree exactly \(3j,\) with leading coefficient \(\binom{4j}{2j}/(3j)!.\) Dividing by the leading coefficient \(1/j!^2\) of \(\binom{i+j}{j}^2\) gives the stated degree and leading coefficient of \(p_j.\)
Finally, \(N_{2j}(t)\) is palindromic of degree \(2j.\) Ehrhart reciprocity for the \(3j\)-dimensional polytope \(\mathcal P_j,\) whose codegree is \(j+1,\) gives \[A(-i-j-1,j)=(-1)^{3j}A(i,j)=(-1)^jA(i,j).\] Since \(\binom{-i-1}{j}^2=\binom{i+j}{j}^2,\) division gives the reciprocity relation for \(p_j.\)
The same calculation evaluates the bivariate generating function in the OEIS entry. Set \[\mathbf F(x,y)\coloneqq\sum_{i,j\geq0}A(i,j)x^iy^j, \qquad \xi=\frac{1+x}{1-x},\qquad w=\frac{y}{1-x}.\] Taking the even part of the Legendre generating function yields \[\mathbf F(x,y)=\frac{1}{2(1-x)}\left( \frac{1}{\sqrt{1-2\xi\sqrt w+w}} +\frac{1}{\sqrt{1+2\xi\sqrt w+w}} \right).\]