Elegant recursion for A301897

Question

Let $a(n)$ be A301897, i.e., number of permutations $b$ of length $n$ that satisfy the Diaconis-Graham inequality $I_n(b) + EX_n(b) \leqslant D_n(b)$ with equality. Here $$a(n)=\frac{1}{n+1}\binom{2n}{n}+\sum\limits_{k=1}^{n-2}\sum\limits_{j=1}^{n-k-1}\binom{n}{k-1}\binom{n-1}{k+j}\binom{n-k+j-1}{j-1}\frac{1}{j}$$ Let $$R(n,q)=\sum\limits_{j=0}^{q+q\operatorname{mod}3+1}R(n-1,j),$$ $$R(0,q)=1$$ I conjecture that $$R(n,0)=a(n+1)$$ Here is the PARI/GP prog to check it numerically:

R2_upto(n)=my(v1, v2, v3); v1=vector(3*n+1, i, 1); v2=v1; v3=vector(n+1, i, 0); v3[1]=1; for(i=1, n, for(q=0, 3*(n-i), v2[q+1]=sum(j=0, q+q%3+1, v1[j+1])); v1=v2; v3[i+1]=v1[1];); v3
a(n)=binomial(2*n,n)/(n+1)+sum(k=1,n-2,sum(j=1,n-k-1,binomial(n,k-1)*binomial(n-1,k+j)*binomial(n-k+j-1,j-1)*(1/j)))
test(n)=R2_upto(n)==vector(n+1,i,a(i))

Is there a way to prove it?

Answer 1

Here is an expanded version of the generating function argument I sketched in a comment.

For $i=1,2,3$, define the generating functions $F_i(x,y) := \sum_{n=0}^\infty \sum_{q=0}^\infty R(n,3q+i) x^n y^q$, which are well defined for $x,y$ small. If one starts with the recursive identities \begin{align*} R(n,3q) &= \sum_{0 \leq r \leq q} R(n-1,3r) + \sum_{0 \leq r \leq q} R(n-1,3r+1) \\ &\quad + \sum_{0 \leq r \leq q-1} R(n-1,3r+2)\\ R(n,3q+1) &= \sum_{0 \leq r \leq q+1} R(n-1,3r) + \sum_{0 \leq r \leq q} R(n-1,3r+1) \\ &\quad + \sum_{0 \leq r \leq q} R(n-1,3r+2)\\ R(n,3q+2) &= \sum_{0 \leq r \leq q+1} R(n-1,3r) + \sum_{0 \leq r \leq q+1} R(n-1,3r+1) \\ &\quad + \sum_{0 \leq r \leq q+1} R(n-1,3r+2) \end{align*} for $n \geq 1$, multiplies by $x^n y^q$, and then sums using the geometric series formula and the initial condition $R(0,3q+i)=1$, one obtains after some calculation the equations \begin{align*} F_0(x,y) &= \frac{1}{1-y} + \frac{x}{1-y}(F_0(x,y) + F_1(x,y) + y F_2(x,y))\\ F_1(x,y) &= \frac{1}{1-y} + \frac{x}{1-y}\left(\frac{F_0(x,y)}{y} + F_1(x,y) + F_2(x,y)\right) - \frac{x\alpha(x)}{y}\\ F_2(x,y) &= \frac{1}{1-y} + \frac{x}{1-y}\left(\frac{F_0(x,y)}{y} + \frac{F_1(x,y)}{y} + \frac{F_2(x,y)}{y}\right) - \frac{x\beta(x)}{y} \end{align*} for almost all small $x,y$, where $$ \alpha(x) := \sum_{n=0}^\infty R(n,0) x^n$$ and $$ \beta(x) := \sum_{n=0}^\infty (R(n,0)+R(n,1)+R(n,2)) x^n.$$ Note that it is $\alpha$ that we want to understand. So the strategy will be to eliminate the other unknowns $F_0,F_1,F_2,\beta$ to isolate a formula for $\alpha$.

We have a linear system of three equations in three unknowns $F_0,F_1,F_2$. Solving this system using a standard symbolic algebra package, one can eliminate these unknowns, obtaining for instance $$ F_1(x,y) = \frac{(x^3-yx^2 - y^2 x + yx)\alpha(x) +yx^2 \beta(x) - y^2+x^2}{P(x,y)}$$ for almost all small $x,y$, where $P$ is the (irreducible) cubic $$ P(x,y) := y^3 - (1-2x) y^2 + xy - x^3;$$ there are similar formulae for $F_0$ and $F_2$ that we shall discard (they give equivalent constraints to the one (1) we will end up using). Since $F_1$ is analytic at the origin, we conclude the constraint $$ (x^3-yx^2 - y^2 x + yx)\alpha(x) +yx^2 \beta(x) - y^2+x^2 = 0 \quad (1)$$ whenever $x,y$ are small and $P(x,y)=0$. So now the main challenge is to use this relation (1) to eliminate $\beta$.

When $x=0$, the equation $P(x,y)$ has a double zero at $y=0$. Thus for small $x$, there are two small solutions $y_1,y_2$ to $P(x,y)=0$ and one large solution $y_3$ (which is near $y=1$, since $P(0,1)=0$). Since (1) holds for $y=y_1$ and $y=y_2$, we may eliminate $\beta(x)$ to conclude after some algebra that $$ \alpha(x) = -\frac{x^2 + y_1 y_2}{x (x^2 + y_1 y_2 - x)}.$$ However, as $y_1,y_2,y_3$ are the roots of $P(x,y)=0$ we have $y_1 y_2 y_3 = x^3$, so we can simplify to $$ \alpha(x) = \frac{y_3+x}{y_3 - xy_3 - x^2}.$$ From the implicit function theorem $y_3$ is an analytic function of $x$ for $x$ small, so this in fact describes $\alpha$ completely as an element of ${\bf Q}(x,y_3) \equiv {\bf Q}(x,y)/(P(x,y))$, which is a cubic extension of ${\bf Q}(x)$ and should therefore obey a cubic equation with coefficients in ${\bf Q}(x)$. Indeed, using a symbolic algebra package, one can verify the identity $$ x^3 \alpha(x)^3 + (4x^2-3x+1) \alpha(x)^2 + (5x-3) \alpha(x) + 2 = \frac{x P(x,y_3)}{(y_3 - xy_3 - x^2)^3};$$ but $P(x,y_3)$ vanishes, hence $$ x^3 \alpha(x)^3 + (4x^2-3x+1) \alpha(x)^2 + (5x-3) \alpha(x) + 2 = 0.$$ Writing $A(x) := x\alpha(x)$, we then get the generating function identity $$ x^2 A(x)^3 + (4x^2-3x+1) A(x)^2 + (5x^2-3x) A(x) + 2x^2 = 0$$ for the sequence $a(n)$ in A301897. This uniquely specifies $A$ if we enforce the asymptotics $A(x) = x + O(x^2)$, so we obtain $R(n,0)=a(n+1)$ as claimed. With a similar effort one could obtain explicit formulae for $\beta, F_0, F_1, F_2$ which would lead eventually to some combinatorial formula for $R(n,q)$; one could also analyze the singularities of these generating functions to obtain asymptotics for these sequences using standard analytic combinatorics methods (e.g., the residue theorem).

EDIT: I have some further commentary regarding the means I arrived at this answer here.