Recursión elegante para A301897

Question

Sea $a(n)$ la A301897, es decir, el número de permutaciones $b$ de longitud $n$ que satisfacen la desigualdad de Diaconis-Graham $I_n(b) + EX_n(b) \leqslant D_n(b)$ con igualdad. Aquí $$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}$$ Sea $$R(n,q)=\sum\limits_{j=0}^{q+q\operatorname{mod}3+1}R(n-1,j),$$ $$R(0,q)=1$$ Conjeturo que $$R(n,0)=a(n+1)$$ Aquí está el programa PARI/GP para verificarlo numéricamente:

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))

¿Hay alguna forma de probarlo?

Answer 1

Aquí hay una versión expandida del argumento de la función generadora que esbocé en un comentario.

Para $i=1,2,3$, define las funciones generadoras $F_i(x,y) := \sum_{n=0}^\infty \sum_{q=0}^\infty R(n,3q+i) x^n y^q$, que están bien definidas para $x,y$ pequeños. Si se comienza con las identidades recursivas \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*} para $n \geq 1$, se multiplica por $x^n y^q$, y luego se suman usando la fórmula de la serie geométrica y la condición inicial $R(0,3q+i)=1$, se obtienen después de algunos cálculos las ecuaciones \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*} para casi todos los $x,y$ pequeños, donde $$ \alpha(x) := \sum_{n=0}^\infty R(n,0) x^n$$ y $$ \beta(x) := \sum_{n=0}^\infty (R(n,0)+R(n,1)+R(n,2)) x^n.$$ Nótese que es $\alpha$ lo que queremos entender. Así que la estrategia será el...

Tenemos un sistema lineal de tres ecuaciones en tres incógnitas $F_0,F_1,F_2$. Al resolver este sistema utilizando un paquete de álgebra simbólica estándar, se pueden eliminar estas incógnitas, obteniendo por ejemplo $$ 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)}$$ para casi todos los $x,y$ pequeños, donde $P$ es el cúbico (irreducible) $$ P(x,y) := y^3 - (1-2x) y^2 + xy - x^3;$$ hay fórmulas similares para $F_0$ y $F_2$ que descartaremos (dan restricciones equivalentes a la que (1) terminaremos usando). Como $F_1$ es analítica en el origen, concluimos la restricción $$ (x^3-yx^2 - y^2 x + yx)\alpha(x) +yx^2 \beta(x) - y^2+x^2 = 0 \quad (1)$$ cuando $x,y$ son pequeños y $P(x,y)=0$. Entonces el desafío principal es usar esta relación (1) para eliminar $\beta$.

Cuando $x=0$, la ecuación $P(x,y)$ tiene una raíz doble en $y=0$. Así que para $x$ pequeño, hay dos soluciones pequeñas $y_1,y_2$ a $P(x,y)=0$ y una solución grande $y_3$ (que está cerca de $y=1$, ya que $P(0,1)=0$). Dado que (1) se cumple para $y=y_1$ y $y=y_2$, podemos eliminar $\beta(x)$ para concluir después de algunos cálculos que $$ \alpha(x) = -\frac{x^2 + y_1 y_2}{x (x^2 + y_1 y_2 - x)}.$$ Sin embargo, como $y_1,y_2,y_3$ son las raíces de $P(x,y)=0$ tenemos $y_1 y_2 y_3 = x^3$, por lo que podemos simplificar a $$ \alpha(x) = \frac{y_3+x}{y_3 - xy_3 - x^2}.$$ Desde el teorema de la función implícita $y_3$ es una función analítica de $x$ para $x$ pequeño, por lo que de hecho esto describe completamente a $\alpha$ como un elemento de ${\bf Q}(x,y_3) \equiv {\bf Q}(x,y)/(P(x,y))$, que es una extensión cúbica de ${\bf Q}(x)$ y por lo tanto debe cumplir una ecuación cúbica con coeficientes en ${\bf Q}(x)$. De hecho, utilizando un paquete de álgebra simbólica, se puede verificar la identidad $$ 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};$$ pero $P(x,y_3)$ se anula, por lo tanto $$ x^3 \alpha(x)^3 + (4x^2-3x+1) \alpha(x)^2 + (5x-3) \alpha(x) + 2 = 0.$$ Escribiendo $A(x) := x\alpha(x)$, entonces obtenemos la identidad de la función generadora $$ x^2 A(x)^3 + (4x^2-3x+1) A(x)^2 + (5x^2-3x) A(x) + 2x^2 = 0$$ para la secuencia $a(n)$ en A301897. Esto especifica de manera única a $A$ si imponemos la asintótica $A(x) = x + O(x^2)$, por lo que obtenemos $R(n,0)=a(n+1)$ como se afirma. Con un esfuerzo similar se podrían obtener fórmulas explícitas para $\beta, F_0, F_1, F_2$ que eventualmente llevarían a alguna fórmula combinatoria para $R(n,q)$; también se podrían analizar las singularidades de estas funciones generadoras para obtener asintóticas para estas secuencias utilizando métodos estándar de combinatoria analítica (por ejemplo, el teorema del residuo).

EDITAR: Tengo algunos comentarios adicionales sobre los medios por los que llegué a esta respuesta aquí.