Let $a(n)$ be [A301897](https://oeis.org/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?



Elegant recursion for A301897
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](https://oeis.org/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](https://mathstodon.xyz/@tao/110601051375142142).


