# Elegant recursion for A301897

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?

• Nice question. How did you come up with this conjecture? Commented Jun 23, 2023 at 11:45
• $R(n,0)$ is the number of sequences $q_1,\dots, q_n$ of nonnegative integers with $q_1=0$ and $q_{i+1} \leq q_i+ q_i \bmod 3 +1$. Maybe this could be used to give a bijective proof or one could find a different formula to enumerate such sequences and compare. Commented Jun 23, 2023 at 12:12
• As observed in the OEIS, the generating function $A(x)$ for $a$ solves a cubic equation $x^2A(x)^3 + (4x^2-3x+1) A(x)^2 + (5x^2-3x) A(x) + 2 x^2 = 0$. It appears that there is a system of three linear equations relating the three generating functions $F_i(x,y) := \sum_{n=0}^\infty \sum_{q \geq 0: q = i \hbox{ mod } 3} R(n,q) x^n y^q$, $i=0,1,2$ to each other; solving for this and then evaluating $F_0(x,0)$ should in principle recover the above cubic equation if your conjecture is correct (possibly after solving an integral or differential equation). It's a lengthy calculation though. Commented Jun 23, 2023 at 15:07
• You can use findstat to find statistics that refine @WillSawin's observation. For example, it seems that the number of 0's in a Sawin-sequence is equidistributed with findstat.org/StatisticsDatabase/St000056. There might be better statistics, however. Commented Jun 23, 2023 at 15:09
• It is a bit surprising to me, but it seems that the generating function for "connected" such permutations satisfies a slightly simpler cubic: $x C(x)^3 - (3x+1) C(x)^2 + (x+3) C(x) - 2 = 0$. Commented Jun 23, 2023 at 16:14

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.

• Fair enough; I have moved these comments to a different location. Commented Jun 25, 2023 at 0:48
• @DavidRoberts, re, while acknowledging the particular point about ChatGPT that affects this situation, with respect to the more general claim "people don't generally report on their methods on how they arrive at an answer"—it's probably true, but I'm not sure it's such a good thing. I daresay that, outside of particular politically sensitive points, it's probably not a bad idea for us to defer to super-experienced expositors like Tao on how much technically extra-mathematical exposition is appropriate for what venues. Commented Jun 25, 2023 at 0:55
• @TerryTao thank you, that's a big help. I think your usage was in fact an exemplar of how it should be done, just at this present time the optics are difficult. Commented Jun 25, 2023 at 1:03
• I think it is healthy to keep discussing this issue. In my opinion, the situation is actually not so dissimilar to when Wikipedia became popular, and there were debates on how to use it in answering questions on the internet. Clearly, blindly pasting in content from Wikipedia pages would be an absolutely terrible MO answer, but using Wikipedia for initial leads, and providing Wikipedia links as secondary support for one's primary argument, are now socially acceptable. I believe that a similar consensus will eventually emerge regarding GPT. Commented Jun 25, 2023 at 1:07
• A generating function identity similar to your last one (in the OEIS as you note in your initial comment) can be found on p. 33 just below eqn. 2.1 in the book Patterns in Permutations and Words by Sergey Kitaev. Commented Jun 26, 2023 at 16:38