• 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?


1 Answer 1


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}.$$

  • $\begingroup$ 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? $\endgroup$ Commented Jul 12, 2023 at 13:03
  • 7
    $\begingroup$ 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! $\endgroup$ Commented Jul 12, 2023 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.