# generating function for Dyck paths avoiding a pattern

This is a follow up to Counting QF-1 algebras inside quotient algebras of upper triangular matrices via Dyck paths. For $k\geq 1$ let $P_k=x+O(x^{k+2})$ be the formal power series that satisfies $$P_k = \frac{x}{1-P_{k+1}} - \frac{x^2(1-x^k)}{1-x}.$$ I am interested in $P_1$, is there a nicer formula?

Here is one possible expression. I have not tried to simplify it, maybe there actually is much simpler formula, I don't know.

$$P_k(q)=1-(1-q)\frac{H(q^{k+2})}{H(q^{k+3})}$$ with $$H(z)={}_1\phi_1\left(\begin{smallmatrix}0\\\left(\frac q{1-q}\right)^2\end{smallmatrix},q,\frac z{(1-q)^2}\right),$$ where $_1\phi_1$ is the basic hypergeometric function; thus \begin{align*} H(z)&=1-\frac1{(1-q)((1-q)^2-q^2)}z\\ &+\frac q{(1-q)(1-q^2)((1-q)^2-q^2)((1-q)^2-q^3)}z^2\\ &-\frac{q^3}{(1-q)(1-q^2)(1-q^3)((1-q)^2-q^2)((1-q)^2-q^3)((1-q)^2-q^4)}z^3\\ &\cdots\\ &+(-1)^n\frac{q^{\binom n2}}{(1-q)\cdots(1-q^n)((1-q)^2-q^2)\cdots((1-q)^2-q^{n+1})}z^n\\ &\pm\cdots \end{align*}

Here is a plot of the modulus for $P_1(q)$ inside the unit disc (color $=$ phase); I decided to add it because of a suggestive feature: strings of alternating poles and zeros along lines converging to $1$. It hints at a possible infinite product maybe somehow related to theta-functions. At any rate the plot shows the pole nearest to the origin at $q=0.46305364318045766...$, so the leading asymptotics for coefficients must be of base reciprocal to this, i.e. $2.159577005228934...$. Indeed empirically the $n$th coefficient seems to be $\sim0.02700488448532407\times2.159577005228934^n$

What follows is not so much a proof, but rather sort of a heuristic explanation of how did I arrive at this; still I believe it is reasonably reliable.

From $$P_k(x)=-\frac{1-x^k}{1-x}x^2+\frac x{1-P_{k+1}(x)}$$ we get $$P_k(x)= -\frac{1-x^k}{1-x}x^2+\cfrac x{1+\frac{1-x^{k+1}}{1-x}x^2-\cfrac x{1+\frac{1-x^{k+2}}{1-x}x^2-\cfrac x{1+\frac{1-x^{k+3}}{1-x}x^2-\cfrac x{\qquad\ddots}}}}.$$

Let us introduce $$F_k(z,q)=-\frac{1-q^kz}{1-q}q^2+\cfrac q{1+\frac{1-q^{k+1}z}{1-q}q^2-\cfrac q{1+\frac{1-q^{k+2}z}{1-q}q^2-\cfrac q{1+\frac{1-q^{k+3}z}{1-q}q^2-\cfrac q{\qquad\ddots}}}},$$ so that $P_k(q)=F_k(1,q)$. Then we get the functional equation $$F_k(z,q)=-\frac{1-q^kz}{1-q}q^2+\frac q{1-F_k(qz,q)}.$$ To linearize this, let us introduce another function $A_k(z)$ given by $$\frac{1-q}{1-F_k(z,q)}=\frac{A_k(qz)}{A_k(z)},$$ so that $P_k(q)=1-(1-q)\frac{A_k(1)}{A_k(q)}$. The above functional equation then becomes $$(1-q)\frac{A_k(z)}{A_k(qz)}=1+\frac{1-q^kz}{1-q}q^2-\frac q{1-q}\frac{A_k(q^2z)}{A_k(qz)},$$ so $$(1-q)^2A_k(z)=(1-q+(1-q^kz)q^2)A_k(qz)-qA_k(q^2z).$$

If $A_k(z)=1+a_1z+a_2z^2+...$, then for the coefficients $a_n$ (with $a_0=1$) we get $$a_n=-\frac{q^{k+n+1}}{(1-q^n)((1-q)^2-q^{n+1})}a_{n-1}.$$

This gives $$A_k(z)={}_1\phi_1\left(\begin{smallmatrix}0\\\left(\frac q{1-q}\right)^2\end{smallmatrix},q,\left(\frac q{1-q}\right)^2q^kz\right),$$ or in our notation $A_k(z)=H(q^{k+2}z)$. Then the above equality $P_k(q)=1-(1-q)\frac{A_k(1)}{A_k(q)}$ gives the claimed expression.

PS And here is the Mathematica code that produced the plot, in case somebody would like to play with it

P1[q_]:=With[{c=(q/(1-q))^2},
1-(1-q) QHypergeometricPFQ[{0},{c},q,q c]/QHypergeometricPFQ[{0},{c},q,q^2 c]]
ListPlot3D[Flatten[Table[
With[{q=r E^(I a)},{r Cos[a],r Sin[a],Abs[P1[q]]}],
{r,Table[1-1/n^2,{n,1.01,10,.01}]},{a,-\[Pi],\[Pi],\[Pi]/180}
],1],
ColorFunction->(Hue[(\[Pi]+Arg[P1[#1+I #2]])/(2\[Pi])]&),
ColorFunctionScaling->False, MeshFunctions->{(#3&)},Mesh->20]

• Could you possibly contact me by email? Jan 15 '17 at 16:34
• @MartinRubey Just did it :D Jan 15 '17 at 16:45