# Remarkable recursions for the A204262

• Let $$a(n)$$ be A204262 i.e. permanent of the matrix $$n\times n$$ with elements $$\min(i,j)$$.
• Let $$f_{n,\ell}(x)=g_{n,\ell}(x)+f_{n,\ell-1}(\ell)-g_{n,\ell}(\ell), \\ g_{n,\ell}(x)=\int (n-\ell)^2 f_{n-1,\ell}(x)\,dx, \\ f_{n,0}(x)=n!x^n$$
• Let $$R(n,q)=\sum\limits_{j=0}^{q+1}\binom{q+1}{j}(j+1)R(n-1,j), \\ R(0,q)=1$$

I conjecture that $$R(n,0)=f_{n+1,n+1}(0)=a(n+1).$$

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

a(n)=matpermanent(matrix(n, n, i, j, min(i, j)))
f_upto(n)=my(v1); v1=vector(n+1, i, i--; i!*x^i); for(i=1, n, for(j=i, n, my(A=intformal((j-i)^2*v1[j])); v1[j+1] = A + subst(v1[j+1] - A, x, i))); v1
R_upto(n)=my(v1, v2, v3, v4); v1=vector(n+1, i, 1); v2=v1; v3=vector(n+1, i, 0); v3[1]=1; v4=vector(n, i, vector(i+1, j, binomial(i, j-1)*j)); for(i=1, n, for(q=0, n-i, v2[q+1]=sum(j=0, q+1, v4[q+1][j+1]*v1[j+1])); v1=v2; v3[i+1]=v1[1];); v3
test1(n)=f_upto(n)==concat(1, R_upto(n-1))
test2(n)=f_upto(n)==vector(n+1, i, a(i-1))


Is there a way to prove it?

I can show the first identity $$R(n,0) = f_{n+1,n+1}(0)$$, as a consequence of the more general identity

$$R(n,q) = \frac{1}{(q+1)!} f_{n+q+1,n}(n+1)\tag{1}\label{1}$$ for $$n,q \geq 0$$. Indeed, note that $$g_{n+1,n+1} \equiv 0$$ and thus $$f_{n+1,n+1}(0) = f_{n+1,n}(n+1)$$, so $$R(n,0) = f_{n+1,n+1}(0)$$ is basically a special case of \eqref{1}.

One can prove \eqref{1} by induction on $$n$$. For $$n=0$$ we have $$R(0,q) = 1 = \frac{1}{(q+1)!} f_{q+1,0}(1)$$ by hypothesis. For $$n>0$$, we see from Taylor expansion (and noting from induction that $$f_{n+q+1,n}$$ is a polynomial of degree $$q+1$$) that $$\frac{1}{(q+1)!} f_{n+q+1,n}(n+1) = \sum_{j=0}^{q+1} \frac{1}{(q+1)! j!} f_{n+q+1,n}^{(j)}(n).$$ But from the recursive definition of $$f_{n,\ell}$$ and the fundamental theorem of calculus one has $$f_{n,\ell}'(x) = (n-\ell)^2 f_{n-1,\ell}(x)$$ and hence on iterating $$f_{n+q+1,n}^{(j)}(x) = \left(\frac{(q+1)!}{(q+1-j)!}\right)^2 f_{n+q+1-j,n}(x)$$ so that $$\frac{1}{(q+1)!} f_{n+q+1,n}(n+1) = \sum_{j=0}^{q+1} \frac{(q+1)!}{(q+1-j)! (q+1-j)! j!} f_{n+q+1-j,n}(n).$$ But from the recursive definition of $$f_{n,\ell}$$ and the induction hypothesis we have $$f_{n+q+1-j,n}(n) = f_{n+q+1-j,n-1}(n) = (q+2-j)! R(n-1,q+1-j)$$ and hence $$\frac{1}{(q+1)!} f_{n+q+1,n}(n+1) = \sum_{j=0}^{q+1} \frac{(q+1)!}{(q+1-j)! j!} (q+2-j) R(n-1,q+1-j).$$ Replacing $$j$$ by $$q+1-j$$ we obtain $$\frac{1}{(q+1)!} f_{n+q+1,n}(n+1) = \sum_{j=0}^{q+1} \binom{q+1}{j} (j+1) R(n-1,j)$$ recovering \eqref{1} by the recursive definition of $$R$$.

I discovered \eqref{1} by working backwards from the desired identity $$R(n,0) = f_{n+1,n+1}(0)$$ to try to write $$R(n,1) = \frac{1}{2} (R(n+1,0) - R(n,0))$$ and then $$R(n,2) = \frac{1}{3} (R(n+1,1) - R(n,0) - 4 R(n,1))$$ in terms of the $$f_{n,\ell}$$ in as simple a fashion as possible (using the ODE form $$f_{n,\ell}' = (n-\ell)^2 f_{n-1,\ell}$$, $$f_{n,\ell}(\ell) = f_{n,\ell-1}(\ell)$$ of the recursion for $$f$$ to eliminate the role of the indefinite integral $$g$$), at which point the general pattern became clear. Presumably a similar technique, using the multilinearity and symmetry properties of the permanent to express $$R(n,1)$$, then $$R(n,2)$$, etc., as a suitable permanent starting from the hypothesis $$R(n,0) = a(n+1)$$, will then give a similar identity relating $$R(n,q)$$ with the permanent of a suitable matrix which can then be established by induction to complete the proof, but I will leave this for someone else to try. EDIT: actually it may he easier to try to discover how $$f_{n,\ell}(x)$$ can be expressed neatly as a permanent, as it has a simpler recursion.

SECOND EDIT: OK, I have found the permanental formula for $$f_{n,\ell}$$:

$$f_{n,\ell}(x) = \mathrm{per}( A_{n,\ell} + x B_{n,\ell} ) \tag{2} \label{2}$$ where $$A_{n,\ell}$$ is the $$n \times n$$ matrix with entries $$\min(i,j) 1_{\min(i,j) \leq \ell}$$, and $$B_{n,\ell}$$ is the $$n \times n$$ matrix with entries $$1_{\min(i,j) > \ell}$$. (Guessing this formula for $$\ell=n$$ and $$\ell = n-1$$ was not too difficult, but it took a while to realize that $$f_{n,\ell}$$ could be placed in this form for $$\ell = n-2$$. Again, at this point the pattern became clear.)

Indeed, one has $$f_{n,0}(x) = x^n \mathrm{per}( B_{n,0} ) = n! x^n$$ (since $$B_{n,0}$$ is the all $$1$$'s matrix), and from the identity $$A_{n,\ell} + \ell B_{n,\ell} = A_{n,\ell-1} + \ell B_{n,\ell-1}$$ we have $$f_{n,\ell}(\ell) = f_{n,\ell-1}(\ell)$$. Finally, from multilinearity, cofactor expansion and the fact that the $$n-1 \times n-1$$ minor formed by deleting the $$i^{th}$$ row and $$j^{th}$$ column from $$A_{n,\ell} + x B_{n,\ell}$$ is equal to $$A_{n-1,\ell} + x B_{n-1,\ell}$$ when $$\min(i,j) > \ell$$, we have $$f'_{n,\ell}(x) = (n-\ell)^2 f_{n-1,\ell}(x)$$ (the factor $$(n-\ell)^2$$ coming from the number of 1's appearing in $$B_{n,\ell}$$) and this is all we need to verify \eqref{2} recursively. Replacing $$n,\ell$$ by $$n+1$$ we obtain $$f_{n+1,n+1}(0) =a(n+1)$$ as conjectured.

Combining \eqref{1}, \eqref{2} we also have the nice identity $$R(n,q) = \frac{1}{(q+1)!} \mathrm{per}( \min( i, j, n+1 ) )_{1 \leq i,j \leq n+q+1}.$$

• Thank you for answer! If we take $s_{n,\ell,m}(x)=t_{n,\ell,m}(x)+s_{n,\ell-1,m}(m-\ell+1)-t_{n,\ell,m}(m-\ell+1), t_{n,\ell,m}(x)=\int (n-\ell)^2 s_{n-1,\ell,m}(x)\,dx, s_{n,0,m}(x)=n!x^n$, then $s_{n,n,n}(0)$ is A204264. Is it possible to get something like $R(n,q)$ here? Commented Jul 12, 2023 at 13:03
• The OP failed to mention that the polynomials $f_{n,\ell}(x)$ were originally defined as permanents in the discussion at dxdy.ru, from which their recurrence followed. You have essentially reverse-engineered that definition. Nice job nevertheless! Commented Jul 12, 2023 at 15:45