betaFeedback

WorksMathematics

Two families of Young tableaux with periodic walls: Counting formulas and differential transcendence

Abstract

Banderier, Marchal, and Wallner studied the enumeration problem for Young tableaux with walls. These are similar to standard Young tableaux, except that local decreases are allowed at some walls. In 2021, Banderier and Wallner counted Young tableaux with periodic walls, in which the elementary blocks are Young diagrams of shape (2,2)(2,2). They obtained exact counting formulas for 3030 of the 3232 classes up to symmetry. In this paper, we first derive recurrences for counting the remaining two classes of Young tableaux with periodic walls. We then prove that their counting exponential generating functions are differentially transcendental. Consequently, they are neither D-algebraic nor D-finite. This disproves a conjecture of Banderier and Wallner.

2020 Mathematics subject classification: Primary 05A15; Secondary 06A07, 34M15.

Introduction

Banderier, Marchal, and Wallner [1, 2] considered a variation of standard Young tableaux, called Young tableaux with walls. It is very difficult to find a counting formula for such Young tableaux. We now introduce the necessary definitions.

Let λ=(λ1,λ2,…)\lambda= (\lambda_1, \lambda_2, \ldots) be a partition of mm, denoted λ⊢m\lambda\vdash m. The Young diagram of λ\lambda is obtained by drawing a collection of left-justified arrays of mm cells, where row ii has λi\lambda_i cells reading from bottom to top. We also denoted the Young diagram of λ\lambda by λ\lambda. A standard Young tableau of λ\lambda is an assignment of 1,2,…,m1, 2, \ldots, m to the cells of the Young diagram, each number appearing once, such that rows are increasing from left to right, and columns are increasing from bottom to top. We refer to [12 Section 1.7] for details of these definitions.

A Young building B\mathcal{B} of shape λ\lambda is a pair B=(λ,W)\mathcal{B} = (\lambda, \mathcal{W}), where W\mathcal{W} is a subset of the edges of Young diagram of λ\lambda. The elements of W\mathcal{W} are called walls. A Young tableau with walls over B\mathcal{B} is a filling of the cells of λ\lambda by labels 1,2,…,m=∣λ∣1,2,\ldots,m=|\lambda|, such that each label appears exactly once and the labels are increasing along each row and column (conditions for standard Young tableaux), but two labels separated by a wall in WW need not be increasing. Denote by YT⁡(λ,W)\operatorname{YT}(\lambda,W) (or YT⁡(B)\operatorname{YT}(\mathcal{B})) the set of all such tableaux. It reduces to the set of standard Young tableaux of shape λ\lambda when WW is empty. See Figure 1 for an example of Young tableaux with walls of shape λ=(5,4,2)\lambda=(5,4,2) in YT⁡(λ,W)\operatorname{YT}(\lambda,W). The walls in WW are depicted as bold red edges.

Figure 1. A Young building and a Young tableau with walls.

Banderier, Marchal, and Wallner [1] studied the enumeration of certain rectangular Young tableaux with walls using density methods and bijections. Through the enumeration of two classes of Young tableaux with walls, Lin et al. [5] proved the well-known tree-child network conjecture of Pons and Batle [9]. The solution of this conjecture was facilitated by the connection established by Chang et al. [4 Remark 3.3] between tree-child networks and Young tableaux with walls.

Banderier and Wallner [2] considered Young tableaux with periodic walls and obtained several counting formulas. By employing the kernel method and the lattice path enumeration theory, Liu and Xin [7] obtained the generating function for a class of two-row Young tableaux with periodic walls.

Let B=(λ,W)\mathcal{B}=(\lambda,W) be a building of rectangular shape. Define Bn\mathcal{B}^n to be the Young building formed by connecting nn blocks of B\mathcal{B} horizontally. Then Young tableaux with walls over Bn\mathcal{B}^n are called Young tableaux with periodic walls. Let YT⁡(Bn)\operatorname{YT}(\mathcal{B}^n) denote the set of all such tableaux. Note that WW is allowed to contain the rightmost edges of λ\lambda. Figure 2 illustrates a Young building B\mathcal{B} on the left and a Young building B3\mathcal{B}^3 with periodic walls on the right.

Figure 2. A Young building B\mathcal{B} (denoted by Z2\mathbb{Z}_2) on the left and a Young building B3=(Z2)3\mathcal{B}^3=(\mathbb{Z}_2)^3 with periodic walls on the right.

Banderier and Wallner [2] counted Young tableaux with periodic walls by the density method and bijection with binary trees. Let λ=(2,2)\lambda=(2,2). They considered a classification of 2×22\times2 periodic shapes (a total of 26=642^6=64 different models). In other words, there are 64 distinct sets WW. Two of them are shown in Figure 2 and Figure 3. From the perspective of counting ∣YT⁡(Bn)∣|\operatorname{YT}(\mathcal{B}^n)|, there are actually 32 models in total by symmetry. Based on their counting formulas, Banderier and Wallner classified these 32 counting models into the following four classes: (P) simple products, (A) algebraic, (H) hypergeometric, (Z) zig-zag. They also obtained exact counting formulas for 30 of these 32 counting models; see [2 Table 1]. The formulas for the remaining counting models in Figure 2 and Figure 3 are unknown. They are denoted by Z2 and Z3, respectively.

Figure 3. A Young building B\mathcal{B} (denoted by Z3\mathbb{Z}_3) on the left and a Young building B3=(Z3)3\mathcal{B}^3=(\mathbb{Z}_3)^3 with periodic walls on the right.

Let ana_n and bnb_n count the Young tableaux with periodic walls of types Z2 and Z3 with nn blocks. That is

an=∣YT⁡((Z2)n)∣andbn=∣YT⁡((Z3)n)∣.a_n=|\operatorname{YT}((\mathrm{Z2})^n)| \qquad\text{and} \qquad b_n=|\operatorname{YT}((\mathrm{Z3})^n)|.

Each such tableau has 4n4n cells, and the empty tableau has counts a0=b0=1a_0=b_0=1. We first specify the normalization, since the number of blocks and the number of cells give different series. Define

A(z)=∑n≥0an(4n)!zn,B(z)=∑n≥0bn(4n)!zn.(1)A(z)=\sum_{n\geq0}\frac{a_n}{(4n)!}z^n,\qquad B(z)=\sum_{n\geq0}\frac{b_n}{(4n)!}z^n. \tag*{(1)}

The exponential generating functions in which the variable marks cells are therefore A(t4)A(t^4) and B(t4)B(t^4). The usual exponential generating series of the sequences indexed by the number of blocks are

F2(t)=∑n≥0ann!tn,F3(t)=∑n≥0bnn!tn.(2)F_2(t)=\sum_{n\geq0}\frac{a_n}{n!}t^n,\qquad F_3(t)=\sum_{n\geq0}\frac{b_n}{n!}t^n. \tag*{(2)}

In particular, Banderier and Wallner proposed the following conjecture.

Conjecture 1.1. (Banderier and Wallner [2]) The exponential generating functions F2(t)F_2(t) and F3(t)F_3(t) are D-algebraic but not D-finite.

The main motivation of this paper is to resolve Conjecture 1.1. We give counting formulas for both families and prove that their exponential generating functions are in fact differentially transcendental. These series require a separate analysis: changing a factorial normalization does not in general preserve differential algebraicity.

A function F(z)F(z) is differentially algebraic (or D-algebraic) over C(z)\mathbb{C}(z) if it satisfies

P(z,F(z),F′(z),…,F(k)(z))=0P\left(z,F(z),F'(z),\ldots,F^{(k)}(z)\right)=0

for some integer k≥0k\geq0 and some nonzero polynomial P∈C(z)[Y0,…,Yk]P\in\mathbb{C}(z)[Y_0,\ldots,Y_k]. It is differentially transcendental if no such polynomial exists. It is D-finite if it satisfies a nonzero linear differential equation with coefficients in C(z)\mathbb{C}(z). These definitions also apply to formal series. A sequence (un)n≥0(u_n)_{n\geq0} is P-recursive if, for some d≥0d\geq0, there are polynomials p0,…,pd∈C[n]p_0,\ldots,p_d\in\mathbb{C}[n], not all zero, such that

∑j=0dpj(n)un+j=0\sum_{j=0}^{d}p_j(n)u_{n+j}=0

for every sufficiently large integer nn. Equivalently, its ordinary generating series is D-finite; see [10 Theorem 1.5]. For further details on the definitions, we refer the reader to [13 Chapters 5 and 6].

Theorem 1.2. The generating functions A(z)A(z) and B(z)B(z) are defined in (1). Then neither A(z)A(z) nor B(z)B(z) is D-finite over C(z)\mathbb{C}(z). Equivalently, the sequences (an)n≥0(a_n)_{n\geq0} and (bn)n≥0(b_n)_{n\geq0} are not P-recursive. Moreover,

lim⁡n→∞((2n)!(4n)!an)1/n=lim⁡n→∞((2n)!(4n)!bn)1/n=π232.\lim_{n\to\infty}\left(\frac{(2n)!}{(4n)!}a_n\right)^{1/n} = \lim_{n\to\infty}\left(\frac{(2n)!}{(4n)!}b_n\right)^{1/n} = \frac{\pi^2}{32}.

and the associated auxiliary series has radius of convergence 32/π232/\pi^2, which is not an algebraic number.

Theorem 1.3. The series F2(t)F_2(t) and F3(t)F_3(t) in (2) have radius of convergence zero. As formal power series, each is differentially transcendental over C(t)\mathbb{C}(t). Consequently, neither series is D-algebraic, and neither is D-finite. More precisely,

lim⁡n→∞an+1n(n+1)an=lim⁡n→∞bn+1n(n+1)bn=2π2\lim_{n\to\infty}\frac{a_{n+1}}{n(n+1)a_n} = \lim_{n\to\infty}\frac{b_{n+1}}{n(n+1)b_n} = 2\pi^2

and

lim⁡n→∞(an(n!)2)1/n=lim⁡n→∞(bn(n!)2)1/n=2π2.\lim_{n\to\infty}\left(\frac{a_n}{(n!)^2}\right)^{1/n} = \lim_{n\to\infty}\left(\frac{b_n}{(n!)^2}\right)^{1/n} = 2\pi^2.

We also obtained two recurrences for ana_n and bnb_n; see Theorem 2.3. This allows us to compute certain concrete values quickly. Computing all counts with 0≤n≤N0 \leq n \leq N requires O(N2)O(N^2) arithmetic operations and O(N)O(N) entries of working memory. As a byproduct, non-recursive formulas for ana_n and bnb_n are given in Proposition A.1. However, they are not convenient for computation.

The rest of this paper is organized as follows. In § 2, we associate Z2\mathbb{Z}_2 and Z3\mathbb{Z}_3 with their corresponding posets, and then obtain recurrences for ana_n and bnb_n. § 3 is mainly devoted to proving Theorem 1.2. § 4 mainly concerns the proof of Theorem 1.3. Section A is a byproduct; it mainly contains the non-recursive formulas for ana_n and bnb_n.

Two posets and their counting formulas

This section gives the details of the two families of posets, denoted by Z2\mathbb{Z}_2 and Z3\mathbb{Z}_3, and the counts ana_n and bnb_n of their linear extensions with nn blocks. These objects were introduced in the Introduction. We describe the order relations in each family. We then express ana_n and bnb_n as integrals over order polytopes. These integral formulas are the basis for the later analysis. We also record a polynomial recursion, which gives single sums with integer coefficients. This recursion is useful for computation, but the later arguments do not rely on it.

Order relations and order polytopes

We describe Z2\mathbb{Z}_2 and Z3\mathbb{Z}_3 by their order relations. In this way, the objects do not depend on a diagram convention.

Write x1,…,x2nx_1,\ldots,x_{2n} for the bottom-row cells and y1,…,y2ny_1,\ldots,y_{2n} for the top-row cells, read from left to right. In both families the bottom row is a chain:

x1<x2<⋯<x2n.x_1 < x_2 < \cdots< x_{2n}.

For Z2\mathbb{Z}_2, the additional generating relations are

y2j−1<y2j,x2j<y2j(1≤j≤n).(3)y_{2j-1} < y_{2j}, \qquad x_{2j} < y_{2j} \quad(1 \leq j \leq n). \tag*{(3)}

For Z3, they are

x2j−1<y2j−1(1≤j≤n),y2j<y2j+1(1≤j<n).(4)x_{2j-1} < y_{2j-1}\quad(1 \le j \le n),\qquad y_{2j} < y_{2j+1}\quad(1 \le j < n). \tag*{(4)}

The orders are the transitive closures of the stated relations. No other adjacent-cell relations are imposed. In particular, in (4), y2ny_{2n} is isolated. Also, y1y_1 has only its attachment to x1x_1.

A legal labeling is a bijection from the cells to {1,…,4n}\{1,\ldots,4n\} that preserves these orders. Thus it is a linear extension of the corresponding poset.

Figure 4 shows the two orders for n=2n=2. Every arrow points from a smaller element to a larger one. The isolated element in the second diagram is part of the counting problem and contributes to the factorial (4n)!(4n)!.

Figure 4. The two posets with two blocks. Only generating order relations are drawn.

For a finite poset PP with NN elements, its order polytope is

O(P)={(uv)v∈P∈[0,1]N:uv≤uw whenever v≤Pw}.\mathcal{O}(P)=\{(u_v)_{v\in P}\in[0,1]^N:u_v\le u_w\text{ whenever }v\le_P w\}.

The volume formula

#{linear extensions of P}=N!vol⁡O(P)(5)\#\{\text{linear extensions of }P\}=N!\operatorname{vol}\mathcal{O}(P) \tag*{(5)}

is due to Stanley [11 Corollary 4.2]. For completeness, the hyperplanes on which two coordinates coincide have measure zero. Off these hyperplanes, each ordering of all NN coordinates describes an open simplex of volume 1/N!1/N!. Such a simplex belongs to O(P)\mathcal{O}(P) exactly when the ordering is a linear extension. These simplices have disjoint interiors. They cover the order polytope up to measure zero. This proves (5).

Set

q(x)=1−x22,0≤x≤1.q(x)=\frac{1-x^2}{2},\qquad0\le x\le1.

We use the same symbols for cells and their coordinates in the order polytope. Once the bottom-row coordinates are fixed, the coordinates in different top-row components can be integrated independently.

Proposition 2.1. For n≥1n\ge1, we have

an(4n)!=∫0<x1<⋯<x2n<1∏j=1nq(x2j) dx1⋯dx2n,(6)\frac{a_n}{(4n)!}=\int_{0<x_1<\cdots<x_{2n}<1}\prod_{j=1}^{n}q(x_{2j})\,\mathrm{d}x_1\cdots\mathrm{d}x_{2n}, \tag*{(6)}
bn(4n)!=∫0<x1<⋯<x2n<1(1−x1)∏j=2nq(x2j−1) dx1⋯dx2n.(7)\frac{b_n}{(4n)!}=\int_{0<x_1<\cdots<x_{2n}<1}(1-x_1)\prod_{j=2}^{n}q(x_{2j-1})\,\mathrm{d}x_1\cdots\mathrm{d}x_{2n}. \tag*{(7)}

Proof. For (3), fix the bottom-row coordinates. For each jj, the coordinates y2j−1y_{2j-1} and y2jy_{2j} only interact with x2jx_{2j}. The relations are y2j−1<y2jy_{2j-1}<y_{2j} and x2j<y2jx_{2j}<y_{2j}. Thus, for fixed x2jx_{2j}, we have x2j<y2j<1x_{2j}<y_{2j}<1 and 0<y2j−1<y2j0<y_{2j-1}<y_{2j}. Their integral is

∫x2j1∫0y2jdy2j−1dy2j=∫x2j1y2jdy2j=q(x2j).\int_{x_{2j}}^{1}\int_{0}^{y_{2j}}\mathrm{d}y_{2j-1}\mathrm{d}y_{2j} =\int_{x_{2j}}^{1}y_{2j}\mathrm{d}y_{2j} =q(x_{2j}).

The pairs for different jj are independent. Multiplying over all jj and then integrating over the bottom chain gives (6) by (5).

For (4), again fix the bottom-row coordinates. The coordinate y1y_1 only interacts with x1x_1. The relation is x1<y1x_1 < y_1. Thus its integral is

∫x11dy1=1−x1.\int_{x_1}^{1} dy_1 = 1-x_1.

For 2≤j≤n2 \le j \le n, the pair (y2j−2,y2j−1)(y_{2j-2},y_{2j-1}) only interacts with x2j−1x_{2j-1}. The relations are y2j−2<y2j−1y_{2j-2} < y_{2j-1} and x2j−1<y2j−1x_{2j-1} < y_{2j-1}. For fixed x2j−1x_{2j-1}, the integral is

∫x2j−11∫0y2j−1dy2j−2dy2j−1=∫x2j−11y2j−1dy2j−1=q(x2j−1).\int_{x_{2j-1}}^{1}\int_{0}^{y_{2j-1}}dy_{2j-2}dy_{2j-1} =\int_{x_{2j-1}}^{1}y_{2j-1}dy_{2j-1} =q(x_{2j-1}).

The isolated coordinate y2ny_{2n} contributes a factor 1. These are all the top-row components. Multiplying them and integrating over the bottom chain gives (7).

A polynomial recursion

To write the density formulas in (6) and (7) in iterative form, we introduce an integral operator. Define

(Tf)(x)=∫0x(x−u)q(u)f(u) du.(8)(Tf)(x)=\int_0^x(x-u)q(u)f(u)\,du. \tag*{(8)}

For k≥0k \ge0, direct integration gives

T(xk)=xk+22(k+1)(k+2)−xk+42(k+3)(k+4).(9)T(x^k)=\frac{x^{k+2}}{2(k+1)(k+2)}-\frac{x^{k+4}}{2(k+3)(k+4)}. \tag*{(9)}

Thus TT maps Q[x]\mathbb{Q}[x] into itself.

In the following proposition, subscripts denote partial derivatives with respect to xx. Thus Sx=∂S/∂xS_x=\partial S/\partial x and Sxx=∂2S/∂x2S_{xx}=\partial^2S/\partial x^2. The same convention applies to VV.

Proposition 2.2. The counts can be evaluated by

an(4n)!=∂∂x(Tnx)∣x=1,bn(4n)!=Tn−1(x22−x36)∣x=1(n≥1).(10)\frac{a_n}{(4n)!}=\left.\frac{\partial}{\partial x}(T^n x)\right|_{x=1}, \qquad \frac{b_n}{(4n)!}=\left.T^{n-1}\left(\frac{x^2}{2}-\frac{x^3}{6}\right)\right|_{x=1} \qquad(n\ge1). \tag*{(10)}

Let S,VS,V be the solutions of

Sxx(x,z)=zq(x)S(x,z),S(0,z)=0,Sx(0,z)=1,(11)S_{xx}(x,z)=zq(x)S(x,z),\qquad S(0,z)=0,\qquad S_x(0,z)=1, \tag*{(11)}
Vxx(x,z)=zq(x)V(x,z)+z(1−x),V(0,z)=0,Vx(0,z)=0.(12)V_{xx}(x,z)=zq(x)V(x,z)+z(1-x),\qquad V(0,z)=0,\qquad V_x(0,z)=0. \tag*{(12)}

Then

A(z)=Sx(1,z),B(z)=1+V(1,z).(13)A(z)=S_x(1,z),\qquad B(z)=1+V(1,z). \tag*{(13)}

The functions in (13) are entire in zz.

Proof. We first record two properties of TT. From (8), we have

(Tf)(0)=0,(Tf)′(0)=0,(Tf)′′(x)=q(x)f(x).(Tf)(0)=0,\qquad(Tf)'(0)=0,\qquad(Tf)''(x)=q(x)f(x).

We use these properties below. The polynomial TnxT^n x is the integral over 0<u1<⋯<u2n+1<x0<u_1<\cdots<u_{2n+1}<x with weight ∏j=1nq(u2j)\prod_{j=1}^{n}q(u_{2j}). This statement follows by induction. For n=0n=0, the integral is ∫0xdu1=x\int_0^x du_1=x. To pass from n−1n-1 to nn, applying TT adds the coordinate u2nu_{2n} with weight q(u2n)q(u_{2n}). The factor x−u2nx-u_{2n} can be rewritten as the integral over the last coordinate u2n+1u_{2n+1}. Thus

Tnx=∫0<u1<⋯<u2n+1<x∏j=1nq(u2j) du1⋯du2n+1.T^n x=\int_{0<u_1<\cdots<u_{2n+1}<x}\prod_{j=1}^{n}q(u_{2j})\,du_1\cdots du_{2n+1}.

Differentiating this integral with respect to the upper limit xx removes the last integration. By the Leibniz rule, the derivative is

∂∂x(Tnx)=∫0<u1<⋯<u2n<x∏j=1nq(u2j) du1⋯du2n.\frac{\partial}{\partial x}(T^n x)=\int_{0<u_1<\cdots<u_{2n}<x}\prod_{j=1}^{n}q(u_{2j})\,du_1\cdots du_{2n}.

At x=1x=1, the result is (6).

Similarly,

x22−x36=∫0<u1<u2<x(1−u1) du1 du2.\frac{x^2}{2}-\frac{x^3}{6}=\int_{0<u_1<u_2<x}(1-u_1)\,du_1\,du_2.

Each further application of TT appends two coordinates and puts a factor qq at the first appended coordinate. The weight obtained in this way is exactly the integrand in (7). Hence (10) follows.

The relevant series are

S(x,z)=∑n≥0znTnxandV(x,z)=∑n≥1znTn−1(x22−x36).S(x,z)=\sum_{n\geq0}z^nT^n x \quad\text{and}\quad V(x,z)=\sum_{n\geq1}z^nT^{n-1}\left(\frac{x^2}{2}-\frac{x^3}{6}\right).

They satisfy S=x+zTSS=x+zTS, and V=z(x2/2−x3/6)+zTVV=z(x^2/2-x^3/6)+zTV. Differentiating twice in xx gives (11)–(12), including the initial values. Equation (10) gives (13).

For convergence, we use the multiple-integral form of TnT^n. Since 0≤q(u)≤1/20\leq q(u)\leq1/2 on [0,1][0,1], we obtain the following estimate. For f∈C([0,1])f\in C([0,1]) and n≥0n\geq0, set

∥f∥∞=sup⁡x∈[0,1]∣f(x)∣.\lVert f\rVert_\infty=\sup_{x\in[0,1]}|f(x)|.

Then

∣(Tnf)(x)∣=∣∫0<u1<⋯<u2n<x∏j=0n−1q(u2j+1)f(u1) du1⋯du2n∣≤∥f∥∞12n∫0<u1<⋯<u2n<xdu1⋯du2n=∥f∥∞x2n2n(2n)!,0≤x≤1.\begin{aligned} |(T^n f)(x)| &=\left|\int_{0<u_1<\cdots<u_{2n}<x}\prod_{j=0}^{n-1}q(u_{2j+1})f(u_1)\,du_1\cdots du_{2n}\right|\\ &\leq\lVert f\rVert_\infty\frac{1}{2^n}\int_{0<u_1<\cdots<u_{2n}<x}du_1\cdots du_{2n}\\ &=\lVert f\rVert_\infty\frac{x^{2n}}{2^n(2n)!},\qquad0\leq x\leq1. \end{aligned}

Hence the displayed series converge locally uniformly in zz. The convergence is uniform for x∈[0,1]x\in[0,1]. Their first xx-derivatives have analogous bounds obtained by differentiating (8). Their second derivatives are controlled by the integral equations. This justifies the differentiations. Alternatively, the density integrals give

0<an(4n)!≤12n(2n)!,0<bn(4n)!≤12n−1(2n)!(n≥1).0<\frac{a_n}{(4n)!}\leq\frac{1}{2^n(2n)!},\qquad 0<\frac{b_n}{(4n)!}\leq\frac{1}{2^{n-1}(2n)!}\quad(n\geq1).

These inequalities prove directly that AA and BB are entire.

Single sums with integer coefficients

The operator formula already gives a short exact calculation. The following form avoids polynomial integration during the calculation. It uses integer coefficients throughout the recurrence. For a positive integer parameter ss, define

c0,0(s)=1,cn+1,k(s)=cn,k(s)+(s+2n+2k−1)(s+2n+2k)cn,k−1(s).(14)c^{(s)}_{0,0}=1,\qquad c^{(s)}_{n+1,k}=c^{(s)}_{n,k}+(s+2n+2k-1)(s+2n+2k)c^{(s)}_{n,k-1}. \tag*{(14)}

Here cn,k(s)=0c^{(s)}_{n,k}=0 when k<0k<0 or k>nk>n. The recurrence is used for n≥0n\geq0 and 0≤k≤n+10\leq k\leq n+1. For each positive integer ss, every nonzero entry is a positive integer. In this paper we only need the cases s=1,2,3s=1,2,3. The initial polynomials in (10) are linear combinations of xs/s!x^s/s! for s=1,2,3s=1,2,3.

Theorem 2.3. For n≥0n\geq0, we have

an=(4n)!2n∑k=0n(−1)kcn,k(1)(2n+2k)!.(15)a_n=\frac{(4n)!}{2^n}\sum_{k=0}^{n}\frac{(-1)^k c^{(1)}_{n,k}}{(2n+2k)!}. \tag*{(15)}

For n≥1n\geq1, we have

bn=(4n)!2n−1∑k=0n−1(−1)k(cn−1,k(2)(2n+2k)!−cn−1,k(3)(2n+2k+1)!).(16)b_n=\frac{(4n)!}{2^{n-1}}\sum_{k=0}^{n-1}(-1)^k\left(\frac{c^{(2)}_{n-1,k}}{(2n+2k)!}-\frac{c^{(3)}_{n-1,k}}{(2n+2k+1)!}\right). \tag*{(16)}

The coefficients are determined by (14). Computing all counts with 0≤n≤N0\leq n\leq N requires O(N2)O(N^2) arithmetic operations and O(N)O(N) entries of working memory.

Proof. The factorial basis makes the calculation explicit. For m≥0m\geq0, (9) becomes

2T(xmm!)=xm+2(m+2)!−(m+1)(m+2)xm+4(m+4)!.2T\left(\frac{x^m}{m!}\right)=\frac{x^{m+2}}{(m+2)!}-(m+1)(m+2)\frac{x^{m+4}}{(m+4)!}.

We claim that

2nTn(xss!)=∑k=0n(−1)kcn,k(s)xs+2n+2k(s+2n+2k)!.(17)2^nT^n\left(\frac{x^s}{s!}\right)=\sum_{k=0}^{n}(-1)^k c^{(s)}_{n,k}\frac{x^{s+2n+2k}}{(s+2n+2k)!}. \tag*{(17)}

At n=0n=0, the claim is the trivial identity xs/s!=xs/s!x^s/s!=x^s/s!. Assume it holds at nn. Applying 2T2T, the first term in the preceding monomial formula contributes cn,k(s)c^{(s)}_{n,k} to the coefficient with index kk at level n+1n+1. The second term with old index k−1k-1 has degree m=s+2n+2k−2m=s+2n+2k-2 before applying TT. Its extra minus sign changes (−1)k−1(-1)^{k-1} to (−1)k(-1)^k. Its integer multiplier is

(m+1)(m+2)=(s+2n+2k−1)(s+2n+2k).(m+1)(m+2)=(s+2n+2k-1)(s+2n+2k).

There are no other contributions to this degree. Thus its total coefficient is exactly (14). This proves (17) by induction.

For ana_n, use s=1s=1 in (17), differentiate in xx, and evaluate at x=1x=1. The differentiation changes x2n+2k+1/(2n+2k+1)!x^{2n+2k+1}/(2n+2k+1)! into x2n+2k/(2n+2k)!x^{2n+2k}/(2n+2k)!. The first identity in (10) gives (15).

For bnb_n, write the initial polynomial as x2/2!−x3/3!x^2/2!-x^3/3!. Use (17) with n−1n-1 in place of nn, first with s=2s=2 and then with s=3s=3. Evaluation at x=1x=1 and the second identity in (10) give (16).

There are n+1n+1 entries in row nn of each triangle. Each entry requires a bounded number of integer additions and multiplications. Hence the rows through NN require O(N2)O(N^2) arithmetic operations. Consecutive factorials up to (4N+1)!(4N+1)! can be computed in O(N)O(N) further operations. The displayed sums use O(n)O(n) rational operations at index nn. Therefore they use O(N2)O(N^2) operations in total. Each new row needs only the preceding row. Retaining the current rows and factorials uses O(N)O(N) entries. No bound on the number of bits in an entry is asserted.

For example, the first three rows for s=1s=1 are

(c0,k(1))=(1),(c1,k(1))=(1,6),(c2,k(1))=(1,26,252).(c^{(1)}_{0,k})=(1),\qquad(c^{(1)}_{1,k})=(1,6),\qquad(c^{(1)}_{2,k})=(1,26,252).

Thus (15) gives

a1=4!2(12!−64!)=3,a2=8!4(14!−266!+2528!)=119.a_1=\frac{4!}{2}\left(\frac{1}{2!}-\frac{6}{4!}\right)=3,\qquad a_2=\frac{8!}{4}\left(\frac{1}{4!}-\frac{26}{6!}+\frac{252}{8!}\right)=119.

For b1b_1, the two initial entries c0,0(2)=c0,0(3)=1c^{(2)}_{0,0}=c^{(3)}_{0,0}=1 give b1=4!(1/2!−1/3!)=8b_1=4!(1/2!-1/3!)=8.

Expanding the integrands directly also gives the subset sums in Section A. Those formulas contain 2n2^n terms; (15) and (16) collect the calculation into rows of the integer recurrence.

The formulas yield the following values. They also agree with direct enumeration of linear extensions for all entries displayed.

nnana_nbnb_n
011
138
2119416
313,76156,136
43,178,78514,433,600
51,226,341,0356,042,488,040
6711,310,157,2713,743,684,613,216

Table 1.

The elementary proof of thm:ABnotDfinite

In this section we prove Theorem 1.2. The theorem states the exponential growth of the normalized counts and the non-PP-recursiveness of (an)(a_n) and (bn)(b_n). Our proof uses the integral formulas from § 2 and a standard fact about DD-finite series. We begin with the normalization.

Let

L=∫01q(x) dx=π42,dn=(2n)!(4n)!an,en=(2n)!(4n)!bn.L=\int_0^1\sqrt{q(x)}\,\mathrm{d}x=\frac{\pi}{4\sqrt{2}},\qquad d_n=\frac{(2n)!}{(4n)!}a_n,\qquad e_n=\frac{(2n)!}{(4n)!}b_n.

We first prove the limits

lim⁡n→∞dn1/n=lim⁡n→∞en1/n=L2=π232.\lim_{n\to\infty}d_n^{1/n}=\lim_{n\to\infty}e_n^{1/n}=L^2=\frac{\pi^2}{32}.

Since qq decreases on [0,1][0,1], we have q(x2j)≤q(x2j−1)q(x2j)q(x_{2j})\le\sqrt{q(x_{2j-1})q(x_{2j})}. The product ∏k=12nq(xk)\prod_{k=1}^{2n}\sqrt{q(x_k)} is symmetric. Its integral over the ordered simplex is therefore 1/(2n)!1/(2n)! times its integral over the cube. By (6),

dn≤L2n.(18)d_n\le L^{2n}. \tag*{(18)}

For a lower bound, fix c∈(0,1)c\in(0,1) and restrict the integral to x2n<cx_{2n}<c. This avoids the zero of qq at 11. On that simplex,

∏j=1nq(x2j)q(x2j−1)=q(x2n)q(x1)∏j=1n−1q(x2j)q(x2j+1)≥q(c)q(0).\prod_{j=1}^{n}\frac{q(x_{2j})}{q(x_{2j-1})} =\frac{q(x_{2n})}{q(x_1)}\prod_{j=1}^{n-1}\frac{q(x_{2j})}{q(x_{2j+1})} \ge\frac{q(c)}{q(0)}.

It follows that

dn≥q(c)q(0)(∫0cq(x) dx)2n.(19)d_n\ge\sqrt{\frac{q(c)}{q(0)}}\left(\int_0^c\sqrt{q(x)}\,\mathrm{d}x\right)^{2n}. \tag*{(19)}

Taking the nn-th roots in (18) and (19) gives

lim sup⁡n→∞dn1/n≤L2andlim inf⁡n→∞en1/n≥sup⁡0<c<1(∫0cq(x) dx)2=L2.\limsup_{n\to\infty} d_n^{1/n} \le L^2 \qquad\text{and}\qquad\liminf_{n\to\infty} e_n^{1/n} \ge\sup_{0<c<1} \left(\int_0^c \sqrt{q(x)}\,\mathrm{d}x\right)^2 = L^2.

Hence dn1/n→L2d_n^{1/n} \to L^2.

For the second family, we compare the integrands. Since 1−x1≥q(x1)≥q(x2)1-x_1 \ge q(x_1) \ge q(x_2) and q(x2j−1)≥q(x2j)q(x_{2j-1}) \ge q(x_{2j}) for j≥2j \ge2, the integrand in (7) is at least the integrand in (6). Hence en≥dne_n \ge d_n. Consequently,

lim inf⁡n→∞en1/n≥lim⁡n→∞dn1/n=L2.\liminf_{n\to\infty} e_n^{1/n} \ge\lim_{n\to\infty} d_n^{1/n} = L^2.

For the reverse inequality, use 1−x1≤11-x_1 \le1 and, for j≥2j \ge2,

q(x2j−1)≤q(x2j−2)q(x2j−1).q(x_{2j-1}) \le\sqrt{q(x_{2j-2})q(x_{2j-1})}.

Therefore

(1−x1)∏j=2nq(x2j−1)≤∏k=22n−1q(xk).(1-x_1)\prod_{j=2}^{n}q(x_{2j-1}) \le\prod_{k=2}^{2n-1}\sqrt{q(x_k)}.

For n≥2n \ge2, integrate x1x_1 and x2nx_{2n} first. The resulting lengths x2x_2 and 1−x2n−11-x_{2n-1} are at most 11. Thus

bn(4n)!≤L2n−2(2n−2)!.\frac{b_n}{(4n)!} \le\frac{L^{2n-2}}{(2n-2)!}.

For n=1n=1, the same inequality holds because b1/4!=1/3≤1b_1/4! = 1/3 \le1. Hence

dn≤en≤(2n)(2n−1)L2n−2.d_n \le e_n \le(2n)(2n-1)L^{2n-2}.

Taking nnth roots gives

lim sup⁡n→∞en1/n≤L2.\limsup_{n\to\infty} e_n^{1/n} \le L^2.

Together with the lower bound, this yields en1/n→L2e_n^{1/n} \to L^2. In particular,

an=(4n)!(2n)!(π232)neo(n),bn=(4n)!(2n)!(π232)neo(n).a_n = \frac{(4n)!}{(2n)!}\left(\frac{\pi^2}{32}\right)^n e^{o(n)}, \qquad b_n = \frac{(4n)!}{(2n)!}\left(\frac{\pi^2}{32}\right)^n e^{o(n)}.

Next we show that the generating functions are not DD-finite. Recall that a formal power series is DD-finite if it satisfies a linear differential equation with polynomial coefficients. We use the following standard fact. See, for instance, [13 Chapter 6] or [8].

Lemma 3.1. A DD-finite series with rational coefficients and finite positive radius of convergence has an algebraic radius of convergence.

Proof. First, an equation with coefficients in C[z]\mathbb{C}[z] can be replaced by one with coefficients in Q[z]\mathbb{Q}[z]. To see this, fix the order and degree bounds of the given equation, and regard its finitely many coefficients as unknowns. Equating coefficients of powers of zz gives a homogeneous linear system over Q\mathbb{Q}. The row space of this possibly infinite system is spanned by finitely many rows. Its kernel has the same dimension over Q\mathbb{Q} as after scalar extension to C\mathbb{C}. Thus a nonzero complex solution implies a nonzero rational solution.

We now use the equation with rational coefficients. Let

pm(z)F(m)(z)+⋯+p0(z)F(z)=0,pj∈Q[z],pm≠0,p_m(z)F^{(m)}(z)+\cdots+p_0(z)F(z)=0,\qquad p_j\in\mathbb{Q}[z],\qquad p_m\ne0,

be such an equation. A germ of a solution continues analytically through an ordinary point. Indeed, after division by pmp_m, this follows from the existence theorem for an analytic first-order linear system applied to (F,…,F(m−1))(F,\ldots,F^{(m-1)}). Hence every singular point of the germ on its finite circle of convergence is a zero of pmp_m. At least one such singular point exists; otherwise finitely many neighborhoods covering that circle would extend FF to a larger disk. Its radius is therefore ∣α∣|\alpha| for a zero α\alpha of pmp_m. Both α\alpha and its complex conjugate are algebraic, and ∣α∣2=αα‾|\alpha|^2=\alpha\overline{\alpha}. Thus ∣α∣|\alpha| is algebraic.

The ordinary series ∑dnzn\sum d_nz^n and ∑enzn\sum e_nz^n have radius L−2=32/π2L^{-2}=32/\pi^2, because dn1/n→L2d_n^{1/n}\to L^2 and en1/n→L2e_n^{1/n}\to L^2. This number is transcendental by the transcendence of π\pi [6]. By Lemma 3.1, neither series is DD-finite. Thus neither (dn)(d_n) nor (en)(e_n) is PP-recursive.

For each fixed j≥0j\geq0, the ratio

(2n+2j)!/(4n+4j)!(2n)!/(4n)!\frac{(2n+2j)!/(4n+4j)!}{(2n)!/(4n)!}

is a rational function of nn. If a polynomial-coefficient recurrence existed for (an)(a_n), substitute an=dn(4n)!/(2n)!a_n=d_n(4n)!/(2n)! and clear denominators. The result would be a nonzero polynomial-coefficient recurrence for (dn)(d_n), a contradiction. The same argument applies to (bn)(b_n) and (en)(e_n). Using the factorial factor (4n)!(4n)! instead, we also find that neither an/(4n)!a_n/(4n)! nor bn/(4n)!b_n/(4n)! is PP-recursive. Hence AA and BB are not DD-finite. This proves Theorem 1.2.

Section 3 proved that AA and BB are not DD-finite. The next section disproves the Banderier–Wallner conjecture. That is, we show that the block-counted series F2F_2 and F3F_3 are differentially transcendental. The method is different: a coefficient criterion based on ratio limits, combined with a probabilistic representation of the normalized counts.

Disproving the Banderier–Wallner conjecture

We prove Theorem 1.3 for the block-counted exponential generating functions F2(t),F3(t)F_2(t),F_3(t) in (2). Both are differentially transcendental as formal series, and their coefficient ratios tend to 2π22\pi^2 after division by nn. Their radii of convergence are zero, while their ordinary Borel transforms, obtained by dividing the coefficient of tnt^n by one further factor n!n!, have radius 1/(2π2)1/(2\pi^2). The differential-algebraic classification of F2,F3F_2,F_3 is understood coefficient by coefficient in C[[t]]\mathbb{C}[[t]].

Radius zero alone does not imply differential transcendence. For example, the Euler series E(t)=∑n≥0n!tnE(t)=\sum_{n\geq0}n!t^n has radius zero and satisfies

t2E′(t)+(t−1)E(t)+1=0.t^2E'(t)+(t-1)E(t)+1=0.

Differentiation gives the homogeneous linear equation

t2E′′(t)+(3t−1)E′(t)+E(t)=0.t^2E''(t)+(3t-1)E'(t)+E(t)=0.

so EE is DD-finite. The obstruction used here is the transcendental value of the coefficient ratio, together with rationality and positivity of the coefficients.

In the Euler example, cn=n!c_n=n! and cn+1/(ncn)=(n+1)/n→1c_{n+1}/(nc_n)=(n+1)/n\to1. The limit 11 is algebraic, so Theorem 4.2 below does not exclude differential algebraicity. The obstruction in our application is that the limit 2π22\pi^2 is transcendental.

A coefficient criterion for differential transcendence

We first prove the factorial convolution estimates needed for the criterion.

Lemma 4.1. Let (un)n≥0(u_n)_{n\ge0} be a sequence of positive real numbers such that

lim⁡n→∞un+1nun=K,0<K<∞.\lim_{n\to\infty}\frac{u_{n+1}}{n u_n}=K,\qquad0<K<\infty.

For every fixed nonnegative integer MM, we have

∑j=Mn−Mujun−j=O(unn−M).\sum_{j=M}^{n-M}u_j u_{n-j}=O(u_n n^{-M}).

For every fixed integer q≥2q\ge2, the corresponding restricted qq-fold convolution also satisfies

∑n1+⋯+nq=nn1,…,nq≥Mun1⋯unq=O(unn−M).\sum_{\substack{n_1+\cdots+n_q=n\\n_1,\ldots,n_q\ge M}}u_{n_1}\cdots u_{n_q}=O(u_n n^{-M}).

The constants in these estimates may depend on MM and qq.

Proof. Choose δ∈(0,1)\delta\in(0,1) sufficiently small that

γ=1+δ1−δ<2.\gamma=\frac{1+\delta}{1-\delta}<2.

Since n/(n+1)→1n/(n+1)\to1, there is an integer n0n_0 such that

K(1−δ)(j+1)uj≤uj+1≤K(1+δ)(j+1)uj(j≥n0).K(1-\delta)(j+1)u_j\le u_{j+1}\le K(1+\delta)(j+1)u_j\qquad(j\ge n_0).

After enlarging the constant to cover the finitely many indices 0≤j<n00\le j<n_0, the upper inequality gives

uj≤CKj(1+δ)jj!(j≥0).u_j\le CK^j(1+\delta)^j j!\qquad(j\ge0).

If 0≤j≤n/20\le j\le n/2 and n≥2n0n\ge2n_0, telescoping the lower inequality from n−jn-j to nn gives

un−jun≤(n−j)!n![K(1−δ)]−j.\frac{u_{n-j}}{u_n}\le\frac{(n-j)!}{n!}[K(1-\delta)]^{-j}.

Combining these bounds yields

ujun−jun≤Cγj(nj)(0≤j≤n/2).\frac{u_j u_{n-j}}{u_n}\le C\frac{\gamma^j}{\binom{n}{j}}\qquad(0\le j\le n/2).

We estimate the sum on the right beginning at any fixed MM. For M≤j≤n/4M\le j\le n/4, the ratio of consecutive terms is

γj+1/(nj+1)γj/(nj)=γj+1n−j.\frac{\gamma^{j+1}/\binom{n}{j+1}}{\gamma^j/\binom{n}{j}} =\gamma\frac{j+1}{n-j}.

For all sufficiently large nn, this ratio is bounded by a fixed number less than 11, uniformly in that range. Hence this part of the sum is bounded by a constant times γM/(nM)=O(n−M)\gamma^M/\binom{n}{M}=O(n^{-M}). For n/4≤j≤n/2n/4\le j\le n/2, use

(nj)=∏k=0j−1n−kj−k≥(nj)j≥2j.\binom{n}{j}=\prod_{k=0}^{j-1}\frac{n-k}{j-k}\ge\left(\frac{n}{j}\right)^j\ge2^j.

The sum of γj/(nj)\gamma^j/\binom{n}{j} over this second range is therefore exponentially small, since γ/2<1\gamma/2<1. Symmetry in jj and n−jn-j proves the binary convolution estimate.

Taking M=0M=0 shows that the unrestricted binary convolution is bounded by a constant times unu_n. Increasing that constant to cover the finitely many small values of nn, induction gives

∑n1+⋯+nq=nun1⋯unq≤Cqun\sum_{n_1+\cdots+n_q=n} u_{n_1}\cdots u_{n_q}\le C_q u_n

for every fixed qq. In a restricted qq-tuple, choose an index whose value jj is smallest. Then M≤j≤n/q≤n/2M\le j\le n/q\le n/2. There are at most qq choices of that index. After fixing it, bound the convolution of the remaining q−1q-1 indices by the unrestricted estimate. The resulting upper bound is

qCq−1∑j=M⌊n/2⌋ujun−j=O(unn−M),qC_{q-1}\sum_{j=M}^{\lfloor n/2\rfloor}u_j u_{n-j}=O(u_n n^{-M}),

as required. For q=2q=2, the factor Cq−1C_{q-1} can be taken to be 1.

The coefficient linearization in the next theorem is related to Borinsky’s asymptotic linearization [3 Proposition 55 and Remark 57]. The argument given here requires only a positive coefficient ratio limit; it does not assume a complete asymptotic expansion.

Theorem 4.2. Let f(t)=∑n≥0cntn∈Q[[t]]f(t)=\sum_{n\ge0}c_n t^n\in\mathbb{Q}[[t]], where cn>0c_n>0 for all sufficiently large nn. Suppose that

lim⁡n→∞cn+1cn=K,0<K<∞.\lim_{n\to\infty}\frac{c_{n+1}}{c_n}=K,\qquad0<K<\infty.

If ff is differentially algebraic over C(t)\mathbb{C}(t), then KK is an algebraic number.

Proof. The proof has three steps. First, we reduce to a differential polynomial over Q[t]\mathbb{Q}[t] whose total degree dd in the YY variables is minimal. Second, we expand this relation in a Taylor expansion around the truncated series fNf_N. The linear part carries the dominant contribution cnnEc_n n^E, while the nonlinear remainder is smaller by Lemma 4.1. Third, comparing coefficients gives a nonzero polynomial equation for KK.

We first show that a differential polynomial relation can be chosen over Q[t]\mathbb{Q}[t]. Clear the denominators in a relation over C(t)\mathbb{C}(t) and retain the finitely many monomials in t,Y0,…,Yrt,Y_0,\ldots,Y_r that occur. Regard their coefficients as unknowns. Substitution of f,f′,…,f(r)f,f',\ldots,f^{(r)} and comparison of coefficients of tt gives a homogeneous linear system with rational entries and finitely many columns. Its row space has a basis consisting of finitely many rows. Consequently its kernel is already the kernel of a finite rational matrix, whose rank is the same over Q\mathbb{Q} and C\mathbb{C}. A nonzero complex solution therefore implies a nonzero rational solution.

Among all nonzero polynomials P∈Q[t,Y0,…,Yr]P\in\mathbb{Q}[t,Y_0,\ldots,Y_r] satisfying

P(t,f,f′,…,f(r))=0,P(t,f,f',\ldots,f^{(r)})=0,

choose one whose total degree in the YY variables is smallest. Denote that degree by dd. It is positive, since a nonzero polynomial in tt alone cannot vanish as a formal series. For every index ii on which PP depends, its partial derivative with respect to YiY_i is a nonzero polynomial of smaller total degree. Minimality of dd therefore implies that

Hi(t)=∂P∂Yi(t,f,f′,…,f(r))H_i(t)=\frac{\partial P}{\partial Y_i}(t,f,f',\ldots,f^{(r)})

is a nonzero formal series. Write its first term as

Hi(t)=hitνi+O(tνi+1),hi∈Q∖{0},νi≥0,H_i(t)=h_i t^{\nu_i}+O(t^{\nu_i+1}),\qquad h_i\in\mathbb{Q}\setminus\{0\},\quad\nu_i\ge0,

and set E=max⁡i(2i−νi)E = \max_i(2i-\nu_i), where the maximum is over the indices on which PP depends. The choice of E=max⁡i(2i−νi)E = \max_i(2i-\nu_i) records the dominant power of nn in the linear term below. The truncation index MM will be chosen large enough to make the nonlinear remainder negligible compared with cnnEc_n n^E.

The ratio hypothesis implies, by a finite product of consecutive ratios, that for every fixed integer ss,

cn+scn∼Ksns.\frac{c_{n+s}}{c_n} \sim K^s n^s.

Negative shifts follow by taking reciprocals of the corresponding positive-shift products. In particular, for fixed nonnegative integers i,ki,k,

[tn−k]f(i)cn=(n−k+i)!(n−k)!cn−k+icn∼Ki−kn2i−k.\frac{[t^{n-k}]f^{(i)}}{c_n} = \frac{(n-k+i)!}{(n-k)!}\frac{c_{n-k+i}}{c_n} \sim K^{i-k}n^{2i-k}.

Choose a large fixed integer NN, and set

fN(t)=∑j=0N−1cjtj,R(t)=f(t)−fN(t),M=N−r.f_N(t)=\sum_{j=0}^{N-1}c_jt^j,\qquad R(t)=f(t)-f_N(t),\qquad M=N-r.

Taylor expansion of the polynomial PP in its YY variables is an exact finite identity:

0=P(t,fN,fN′,…,fN(r))+∑iHi,N(t)R(i)+QN(t,R,R′,…,R(r)),0=P(t,f_N,f'_N,\ldots,f_N^{(r)})+\sum_i H_{i,N}(t)R^{(i)}+Q_N(t,R,R',\ldots,R^{(r)}),
Hi,N(t)=∂P∂Yi(t,fN,fN′,…,fN(r)).H_{i,N}(t)=\frac{\partial P}{\partial Y_i}(t,f_N,f'_N,\ldots,f_N^{(r)}).

Here each Hi,NH_{i,N} is a polynomial, and every monomial of QNQ_N has at least two factors among R,R′,…,R(r)R,R',\ldots,R^{(r)}. The coefficients of those monomials are polynomials in tt.

Every difference f(i)−fN(i)f^{(i)}-f_N^{(i)} is divisible by tMt^M for 0≤i≤r0\le i\le r. Substitution in a polynomial thus shows that Hi−Hi,NH_i-H_{i,N} is divisible by tMt^M. Choose NN so large that

M>max⁡iνi,M>2rd−E,M>\max_i\nu_i,\qquad M>2rd-E,

and so that all coefficients cjc_j with j≥Mj\ge M are positive. It follows that Hi,NH_{i,N} has first term hitνih_it^{\nu_i}. If PP does not depend on YiY_i, then both HiH_i and Hi,NH_{i,N} are identically zero.

For sufficiently large nn, the coefficient of P(t,fN,fN′,…,fN(r))P(t,f_N,f'_N,\ldots,f_N^{(r)}) is zero, since it is a polynomial. Likewise, in the linear part, the relevant coefficients of R(i)R^{(i)} equal those of f(i)f^{(i)}. Each Hi,NH_{i,N} contains only finitely many terms. Applying the fixed-shift estimate to these terms gives

[tn]∑iHi,NR(i)=cnnE(∑2i−νi=EhiKi−νi+o(1)).[t^n]\sum_i H_{i,N}R^{(i)}=c_n n^E\left(\sum_{2i-\nu_i=E}h_iK^{i-\nu_i}+o(1)\right).

Indeed, the first term of Hi,NH_{i,N} contributes hiKi−νicnn2i−νi(1+o(1))h_iK^{i-\nu_i}c_n n^{2i-\nu_i}(1+o(1)), and every later term has a smaller power of nn.

We now bound the nonlinear remainder. Replace any nonpositive initial coefficients of (cn)(c_n) by positive numbers, obtaining a sequence (un)(u_n) that agrees with (cn)(c_n) at all sufficiently large indices. It has the same ratio limit, so Lemma 4.1 applies. Enlarge NN if necessary so that uj=cju_j=c_j for j≥Mj\ge M. The fixed-shift estimate also gives

∣[tj]R(i)∣=(j+i)!j!cj+i≤Ciujj2i.\left|[t^j]R^{(i)}\right|=\frac{(j+i)!}{j!}c_{j+i}\le C_i u_jj^{2i}.

whenever this coefficient is nonzero. All such indices satisfy j≥N−i≥Mj \ge N-i \ge M, so the constants can be chosen uniformly over the relevant indices.

Consider a remainder monomial containing q≥2q \ge2 factors, with derivative orders i1,…,iqi_1,\ldots,i_q. Its coefficient of degree nn is bounded in absolute value by a constant times

n2(i1+⋯+iq)∑n1+⋯+nq=nn1,…,nq≥Mun1⋯unq=O(cnn2(i1+⋯+iq)−M).n^{2(i_1+\cdots+i_q)} \sum_{\substack{n_1+\cdots+n_q=n\\n_1,\ldots,n_q\ge M}} u_{n_1}\cdots u_{n_q}=O(c_n n^{2(i_1+\cdots+i_q)-M}).

There are at most dd factors, each of derivative order at most rr, so this is O(cnn2rd−M)O(c_n n^{2rd-M}). Multiplication by a fixed power tpt^p, with p≥0p \ge0, preserves that bound: the coefficient is shifted from nn to n−pn-p, and un−p/cn=O(n−p)u_{n-p}/c_n=O(n^{-p}). Since the remainder contains only finitely many such terms,

[tn]QN(t,R,R′,…,R(r))=O(cnn2rd−M)=o(cnnE).[t^n]Q_N(t,R,R',\ldots,R^{(r)})=O(c_n n^{2rd-M})=o(c_n n^E).

The exact Taylor identity therefore gives

∑2i−νi=EhiKi−νi=0.\sum_{2i-\nu_i=E} h_iK^{i-\nu_i}=0.

This is a nonzero Laurent polynomial equation over Q\mathbb{Q}. To check that its polynomial is nonzero, observe that νi=2i−E\nu_i=2i-E in this sum, so the exponent i−νi=E−ii-\nu_i=E-i is different for each index ii. Every coefficient hih_i is nonzero. Multiplying by a sufficiently large power of KK produces a nonzero ordinary polynomial over Q\mathbb{Q} satisfied by KK. Thus KK is algebraic. □

Proof of Theorem 1.3 by ratio limits

The criterion Theorem 4.2 requires the limit of the consecutive ratio cn+1/(ncn)c_{n+1}/(n c_n). Our growth estimates in Theorem 1.2 give only the nn-th root limits of the normalized counts. We therefore need a passage from root limits to ratio limits. The passage uses the following properties of dnd_n and Mn=en+1/((2n+2)(2n+1))M_n=e_{n+1}/((2n+2)(2n+1)).

Lemma 4.3. The sequences dnd_n and MnM_n are moment sequences of positive finite measures supported on [0,L2][0,L^2], and en+1=(2n+2)(2n+1)Mne_{n+1}=(2n+2)(2n+1)M_n. Moreover, both sequences are log-convex:

dn2≤dn−1dn+1,Mn2≤Mn−1Mn+1(n≥1).d_n^2\le d_{n-1}d_{n+1},\qquad M_n^2\le M_{n-1}M_{n+1}\qquad(n\ge1).

The proof of Lemma 4.3 is given in § 4.3. It uses a probabilistic representation of dnd_n and MnM_n as moments of positive measures, which is independent of the coefficient criterion above.

Now we are ready to give the proof of Theorem 1.3 as follows.

Log-convexity implies that the ratios dn+1/dnd_{n+1}/d_n and Mn+1/MnM_{n+1}/M_n increase with nn. Since the representing measures are supported on [0,L2][0,L^2], we have dn≤L2nd_n\le L^{2n} and Mn≤L2nM_n\le L^{2n}, so these ratios are bounded above by L2L^2. Hence both limits exist. For a positive sequence (mn)(m_n) with mn=m0∏j=0n−1(mj+1/mj)m_n=m_0\prod_{j=0}^{n-1}(m_{j+1}/m_j), the root limit mn1/nm_n^{1/n} equals the ratio limit whenever the latter exists. The root limits are known by Theorem 1.2: dn1/n→L2d_n^{1/n}\to L^2, and Mn1/n→L2M_n^{1/n}\to L^2 follows from en+1=(2n+2)(2n+1)Mne_{n+1}=(2n+2)(2n+1)M_n and en1/n→L2e_n^{1/n}\to L^2. Therefore

dn+1dn⟶L2,MnMn−1⟶L2.\frac{d_{n+1}}{d_n}\longrightarrow L^2,\qquad\frac{M_n}{M_{n-1}}\longrightarrow L^2.

Consequently

en+1en=(2n+2)(2n+1)(2n)(2n−1)MnMn−1⟶L2.\frac{e_{n+1}}{e_n}=\frac{(2n+2)(2n+1)}{(2n)(2n-1)}\frac{M_n}{M_{n-1}}\longrightarrow L^2.

For the coefficients cn=an/n!c_n=a_n/n! of F2F_2, the factorial normalization gives the exact ratio

cn+1ncn=dn+1dn(4n+1)(4n+2)(4n+3)(4n+4)(2n+1)(2n+2)n(n+1)⟶64L2=2π2.\frac{c_{n+1}}{n c_n}=\frac{d_{n+1}}{d_n}\frac{(4n+1)(4n+2)(4n+3)(4n+4)}{(2n+1)(2n+2)n(n+1)}\longrightarrow64L^2=2\pi^2.

For cn=bn/n!c_n=b_n/n!, the same calculation uses ene_n in place of dnd_n and gives the same limit. Both coefficient sequences consist of positive rational numbers. Since 2π22\pi^2 is transcendental by the transcendence of π\pi (see [6]), Theorem 4.2 proves that F2F_2 and F3F_3 are differentially transcendental. Every DD-finite series satisfies a differential polynomial equation, so neither series is DD-finite.

It remains to verify the stated convergence properties. For either coefficient sequence, the ratio just proved implies

cn+1/(n+1)!cn/n!=cn+1(n+1)cn⟶2π2.\frac{c_{n+1}/(n+1)!}{c_n/n!}=\frac{c_{n+1}}{(n+1)c_n}\longrightarrow2\pi^2.

Taking a finite product of these ratios and then taking the nn-th roots gives

(cnn!)1/n⟶2π2.\left(\frac{c_n}{n!}\right)^{1/n}\longrightarrow2\pi^2.

The Cauchy–Hadamard formula therefore gives radius 1/(2π2)1/(2\pi^2) for each ordinary Borel transform. For any A>2π2A>2\pi^2, the same limit gives cn≤CAnn!c_n\le CA^n n! after increasing CC to cover the initial indices. Finally,

cn1/n=(cnn!)1/n(n!)1/n⟶∞,c_n^{1/n}=\left(\frac{c_n}{n!}\right)^{1/n}(n!)^{1/n}\longrightarrow\infty,

because (n!)1/n⟶∞(n!)^{1/n}\longrightarrow\infty. Thus the radii of convergence of F2F_2 and F3F_3 are zero. This completes the proof of Theorem 1.3 modulo the proof of Lemma 4.3 in § 4.3.

Positive moment representations

Recall the normalized counts and their exponential growth limits:

dn=(2n)!(4n)!an,en=(2n)!(4n)!bn,dn1/n, en1/n⟶L2,L=π42.d_n=\frac{(2n)!}{(4n)!}a_n,\qquad e_n=\frac{(2n)!}{(4n)!}b_n,\qquad d_n^{1/n},\ e_n^{1/n}\longrightarrow L^2,\qquad L=\frac{\pi}{4\sqrt{2}}.

The limits were proved in Theorem 1.2. We strengthen them to ratio limits by representing the normalized counts as moments of positive measures.

The construction below applies to the equations for SS and VV. It uses three features that are specific to q(x)=(1−x2)/2q(x)=(1-x^2)/2 and to the initial-value problems (2.9) and (2.10). First, for SS, after the substitution z=w2z=w^2, the functions U=SxU=S_x and W=wvSW=wvS satisfy a 2×22\times2 linear system whose first equation has no zeroth-order term. For VV, the same system has an additional forcing term w2(1−x)w^2(1-x) in the first equation. Second, the coefficient

κ(x)=−q′(x)4q(x)=x2(1−x2)\kappa(x)=-\frac{q'(x)}{4q(x)}=\frac{x}{2(1-x^2)}

is nonnegative on [0,1)[0,1), so it can serve as a switching rate. Third, the integral ∫0xv(u) du\int_0^x v(u)\,du is bounded by LL, so the resulting random variable has bounded support. Under these three conditions, the 2×22\times2 system is the generator of a two-state Markov process, and its solution is the exponential moment of that process. No general differential equation admits such a representation.

Set

v(x)=q(x),κ(x)=x2(1−x2),0≤x<1.v(x)=\sqrt{q(x)},\qquad\kappa(x)=\frac{x}{2(1-x^2)},\qquad0\le x<1.

In particular, v′/v=−2κv'/v=-2\kappa, and κ\kappa is nonnegative and continuous on every compact subinterval of [0,1)[0,1). We give the switching-process construction and the elementary differential equations for its weighted probabilities explicitly.

Let Π(u)\Pi(u), u≥0u\ge0, be a Poisson process of rate 1, starting at Π(0)=0\Pi(0)=0 and having right-continuous counting paths: its increments on disjoint intervals are independent, and

Pr⁡{Π(u+h)−Π(u)=j}=e−hhjj!(j≥0).\Pr\{\Pi(u+h)-\Pi(u)=j\}=e^{-h}\frac{h^j}{j!}\qquad(j\ge0).

Let ε\varepsilon be independent of this process, with values 1 and −1-1, each of probability 1/21/2. Define the common time-changed process

N(x)=Π(∫0xκ(u) du),0≤x<1.N(x)=\Pi\left(\int_0^x\kappa(u)\,\mathrm{d}u\right),\qquad0\le x<1.

For 0≤s≤x<10\le s\le x<1, set

σs,x=ε(−1)N(x)−N(s),Xs,x=∫sxv(u)σs,u du.\sigma_{s,x}=\varepsilon(-1)^{N(x)-N(s)},\qquad X_{s,x}=\int_s^x v(u)\sigma_{s,u}\,\mathrm{d}u.

This common construction makes the random integrals jointly measurable in s,xs,x, as required for the double integrals below. On each compact interval [s,c][s,c] with c<1c<1, the cumulative Poisson time is finite. Thus σs,x\sigma_{s,x} switches sign a finite number of times almost surely on that interval, and its switching rate at xx is κ(x)\kappa(x). The time change is explicit:

∫sxκ(u) du=14log⁡1−s21−x2.\int_s^x\kappa(u)\,\mathrm{d}u=\frac{1}{4}\log\frac{1-s^2}{1-x^2}.

Although this quantity tends to infinity as x→1x\to1, the integral defining Xs,xX_{s,x} has a pathwise limit Xs,1X_{s,1}, because

∣Xs,x′−Xs,x∣≤∫xx′v(u) du(s≤x≤x′≤1).|X_{s,x'}-X_{s,x}|\le\int_x^{x'}v(u)\,\mathrm{d}u\qquad(s\le x\le x'\le1).

Moreover,

∣Xs,x∣≤∫sxv(u) du≤L.|X_{s,x}|\le\int_s^xv(u)\,\mathrm{d}u\le L.

No value of the terminal sign σs,1\sigma_{s,1} is needed.

For w∈Cw\in\mathbb{C} and s≤x<1s\le x<1, define

p±(s,x;w)=E[ewXs,x1{σs,x=±1}],p_{\pm}(s,x;w)=\mathbb{E}\left[e^{wX_{s,x}}\mathbf{1}_{\{\sigma_{s,x}=\pm1\}}\right],

where E\mathbb{E} denotes expectation and 1\mathbf{1} an indicator. Their initial values are p±(s,s;w)=1/2p_{\pm}(s,s;w)=1/2. We claim that

∂xp+=(wv−κ)p++κp−,∂xp−=κp++(−wv−κ)p−.(20)\begin{aligned} \partial_xp_+&=(wv-\kappa)p_++\kappa p_-,\\ \partial_xp_-&=\kappa p_++(-wv-\kappa)p_-. \tag*{(20)} \end{aligned}

To verify this, fix xx in a compact interval below 1 and condition on the sign at xx and the Poisson increments over [x,x+h][x,x+h]. The probabilities of no switch, one switch, and at least two switches are, respectively,

1−κ(x)h+O(h2),κ(x)h+O(h2),O(h2).1-\kappa(x)h+O(h^2),\qquad\kappa(x)h+O(h^2),\qquad O(h^2).

On a path with no switch, the extra exponential weight is 1±wv(x)h+O(h2)1\pm wv(x)h+O(h^2), according to the sign. On a path with one switch it is 1+O(h)1+O(h); its O(h)O(h) correction is multiplied by a switching probability of order hh. The weights already accumulated before xx are bounded by e∣w∣Le^{|w|L}. Independent Poisson increments therefore give

p+(s,x+h;w)=p+(s,x;w)+h((wv−κ)p++κp−)+O(h2),p_+(s,x+h;w)=p_+(s,x;w)+h\left((wv-\kappa)p_++\kappa p_-\right)+O(h^2),
p−(s,x+h;w)=p−(s,x;w)+h(κp++(−wv−κ)p−)+O(h2),p_-(s,x+h;w)=p_-(s,x;w)+h\left(\kappa p_++(-wv-\kappa)p_-\right)+O(h^2),

with the coefficients on the right evaluated at xx. Division by hh and passage to the limit proves (20).

Proposition 4.4. The first normalized count is the moment

dn=EX0,12n(n≥0).d_n=\mathbb{E}X_{0,1}^{2n}\qquad(n\geq0).

For the second family, set

Mj=∫0<s<x<1(1−s)EXs,x2j ds dx(j≥0).M_j=\int_{0<s<x<1}(1-s)\mathbb{E}X_{s,x}^{2j}\,\mathrm{d}s\,\mathrm{d}x\qquad(j\geq0).

Then

en=(2n)(2n−1)Mn−1(n≥1).e_n=(2n)(2n-1)M_{n-1}\qquad(n\geq1).

Both (dn)(d_n) and (Mn)(M_n) are moment sequences of positive finite measures supported on [0,L2][0,L^2].

Proof. For the first family, evaluate (11) at z=w2z=w^2 and set U=SxU=S_x and W=wvSW=wvS, with dependence on x,wx,w understood. The differential equation for SS and the identity v′/v=−2κv'/v=-2\kappa give

U′=wvW,W′=wvU−2κW.U'=wvW,\qquad W'=wvU-2\kappa W.

Consequently U+WU+W and U−WU-W satisfy the same system as 2p+(0,x;w)2p_+(0,x;w) and 2p−(0,x;w)2p_-(0,x;w) in (20). Their initial values are also the same, since U(0)=1U(0)=1 and W(0)=0W(0)=0. Uniqueness for the linear system on each compact interval below 11 gives

Sx(x,w2)=U(x)=p+(0,x;w)+p−(0,x;w)=EewX0,x.S_x(x,w^2)=U(x)=p_+(0,x;w)+p_-(0,x;w)=\mathbb{E}e^{wX_{0,x}}.

The solution SxS_x is continuous at x=1x=1 by (11). The random integral converges pathwise there, and its exponential is bounded by e∣w∣Le^{|w|L}. Dominated convergence and (13) therefore yield

A(w2)=EewX0,1.A(w^2)=\mathbb{E}e^{wX_{0,1}}.

Changing the independent initial sign ε\varepsilon to −ε-\varepsilon changes X0,1X_{0,1} to −X0,1-X_{0,1} without changing its distribution. Thus all odd moments vanish. The exponential series converges uniformly for ∣X0,1∣≤L|X_{0,1}|\leq L on bounded sets of ww, so expectation can be taken term by term:

A(w2)=∑n≥0EX0,12n(2n)!w2n.A(w^2)=\sum_{n\geq0}\frac{\mathbb{E}X_{0,1}^{2n}}{(2n)!}w^{2n}.

Comparison with the definition of AA proves the asserted formula for dnd_n.

For the second family, evaluate (12) at z=w2z=w^2 and set U=VxU=V_x and W=wvVW=wvV. This time the equations are

U′=wvW+w2(1−x),W′=wvU−2κW.U'=wvW+w^2(1-x),\qquad W'=wvU-2\kappa W.

Hence U+WU+W and U−WU-W satisfy (20) with the same extra term w2(1−x)w^2(1-x) in both equations, and with zero initial values. It follows that

U(x)±W(x)=2w2∫0x(1−s)p±(s,x;w) ds.U(x)\pm W(x)=2w^2\int_0^x(1-s)p_\pm(s,x;w)\,\mathrm{d}s.

This identity can be checked directly: differentiation of the right side gives the homogeneous system under the integral, and its upper endpoint contributes 2w2(1−x)p±(x,x;w)=w2(1−x)2w^{2}(1-x)p_{\pm}(x,x;w)=w^{2}(1-x); its value at x=0x=0 is zero. Linear-system uniqueness then proves the identity. Adding the two signs and dividing by 2 gives

Vx(x,w2)=w2∫0x(1−s)EewXs,x ds.V_x(x,w^2)=w^2\int_0^x(1-s)\mathbb{E}e^{wX_{s,x}}\,\mathrm{d}s.

Integrate over 0<x<10<x<1 and use (13):

B(w2)−1=w2∫0<s<x<1(1−s)EewXs,x ds dx.B(w^2)-1=w^2\int_{0<s<x<1}(1-s)\mathbb{E}e^{wX_{s,x}}\,\mathrm{d}s\,\mathrm{d}x.

All weights are bounded by e∣w∣Le^{|w|L}, and the integration domain has finite area. The same symmetry and uniform convergence argument as before therefore gives

B(w2)−1=∑j≥0Mj(2j)!w2j+2.B(w^2)-1=\sum_{j\geq0}\frac{M_j}{(2j)!}w^{2j+2}.

For n≥1n\geq1, comparison of coefficients yields

bn(4n)!=Mn−1(2n−2)!.\frac{b_n}{(4n)!}=\frac{M_{n-1}}{(2n-2)!}.

which is equivalent to the asserted formula for ene_n. In particular, M0=∫01(1−s)2 ds=1/3M_0=\int_0^1(1-s)^2\,\mathrm{d}s=1/3, in agreement with b1/4!=1/3b_1/4!=1/3.

Finally, dnd_n is the nn-th moment of the distribution of X0,12X_{0,1}^2. The sequence MnM_n is the nn-th moment of the positive measure obtained by integrating the distributions of Xs,x2X_{s,x}^2 with weight (1−s) ds dx(1-s)\,\mathrm{d}s\,\mathrm{d}x. Their total masses are 1 and 1/3, respectively. The bound ∣Xs,x∣≤L|X_{s,x}|\leq L places both supports in [0,L2][0,L^2].

We also record the log-convexity used in § 4.2. For a positive finite measure supported on [0,L2][0,L^2], the Cauchy–Schwarz inequality gives

mn2=(∫xn dμ)2≤(∫xn−1 dμ)(∫xn+1 dμ)=mn−1mn+1.m_n^2=\left(\int x^n\,\mathrm{d}\mu\right)^2\leq\left(\int x^{n-1}\,\mathrm{d}\mu\right)\left(\int x^{n+1}\,\mathrm{d}\mu\right)=m_{n-1}m_{n+1}.

Applied to the measures representing dnd_n and MnM_n, this gives dn2≤dn−1dn+1d_n^2\leq d_{n-1}d_{n+1} and Mn2≤Mn−1Mn+1M_n^2\leq M_{n-1}M_{n+1} for n≥1n\geq1.

Subset sum formulas for ana_n and bnb_n

The elementary simplex integral used here is

∫0<u1<⋯<um<1u1r1⋯umrm du1⋯dum=∏k=1m1k+r1+⋯+rk,rk≥0.(21)\int_{0<u_1<\cdots<u_m<1}u_1^{r_1}\cdots u_m^{r_m}\,\mathrm{d}u_1\cdots\mathrm{d}u_m=\prod_{k=1}^{m}\frac{1}{k+r_1+\cdots+r_k},\qquad r_k\geq0. \tag*{(21)}

To verify it, integrate u1u_1 first. The factor (r1+1)−1(r_1+1)^{-1} is obtained, and the exponent of u2u_2 increases by r1+1r_1+1. The next integration gives the factor (r1+r2+2)−1(r_1+r_2+2)^{-1}. Repeating this operation through umu_m gives exactly the product in (A.1).

Proposition A.1. For every integer n≥0n \ge0,

an=(4n)!2n∑ε∈{0,1}n(−1)ε1+⋯+εn∏j=1n(2j−1+2∑k=1j−1εk)(2j+2∑k=1jεk).(22)a_n = \frac{(4n)!}{2^n} \sum_{\varepsilon\in\{0,1\}^n} \frac{(-1)^{\varepsilon_1+\cdots+\varepsilon_n}}{\prod_{j=1}^{n}\left(2j-1+2\sum_{k=1}^{j-1}\varepsilon_k\right)\left(2j+2\sum_{k=1}^{j}\varepsilon_k\right)}. \tag*{(22)}

For every integer n≥1n \ge1,

bn=(4n)!2n−1∑ε∈{0,1}n(−1)ε1+⋯+εn∏j=1n(2j−1+ε1+2∑k=2jεk)(2j+ε1+2∑k=2jεk).(23)b_n = \frac{(4n)!}{2^{n-1}} \sum_{\varepsilon\in\{0,1\}^n} \frac{(-1)^{\varepsilon_1+\cdots+\varepsilon_n}}{\prod_{j=1}^{n}\left(2j-1+\varepsilon_1+2\sum_{k=2}^{j}\varepsilon_k\right)\left(2j+\varepsilon_1+2\sum_{k=2}^{j}\varepsilon_k\right)}. \tag*{(23)}

Empty products are 1, and sums over empty index sets are 0. The value at n=0n=0 in (A.2) is interpreted using the single empty binary vector.

Proof. Expand the integrand in (6) as

2−n∏j=1n(1−x2j2)=2−n∑ε∈{0,1}n(−1)ε1+⋯+εn∏j=1nx2j2εj.2^{-n}\prod_{j=1}^{n}(1-x_{2j}^{2})=2^{-n}\sum_{\varepsilon\in\{0,1\}^{n}}(-1)^{\varepsilon_1+\cdots+\varepsilon_n}\prod_{j=1}^{n}x_{2j}^{2\varepsilon_j}.

In (A.1), the cumulative exponent at position 2j−12j-1 is 2∑k<jεk2\sum_{k<j}\varepsilon_k, and the cumulative exponent at position 2j2j is 2∑k≤jεk2\sum_{k\le j}\varepsilon_k. Substituting these values proves (A.2).

For (7), the expansion is

2−(n−1)(1−x1)∏j=2n(1−x2j−12)=2−(n−1)∑ε∈{0,1}n(−1)ε1+⋯+εnx1ε1∏j=2nx2j−12εj.2^{-(n-1)}(1-x_1)\prod_{j=2}^{n}(1-x_{2j-1}^{2})=2^{-(n-1)}\sum_{\varepsilon\in\{0,1\}^{n}}(-1)^{\varepsilon_1+\cdots+\varepsilon_n}x_1^{\varepsilon_1}\prod_{j=2}^{n}x_{2j-1}^{2\varepsilon_j}.

At positions 2j−12j-1 and 2j2j, the cumulative exponent is the same, namely ε1+2∑k=2jεk\varepsilon_1+2\sum_{k=2}^{j}\varepsilon_k. Equation (A.1) now gives (A.3). □

Data availability: Data availability is not applicable to this article as no new data were created or analyzed in this study.

Acknowledgments: We are also grateful to Dr. Zihao Zhang for many useful suggestions. Feihu Liu was partially supported by the Postdoctoral Fellowship Program and China Postdoctoral Science Foundation (No. BX2026002). Guoce Xin was partially supported by the National Natural Science Foundation of China (No. 12571355).

References

  1. [1]C. Banderier, P. Marchal, and M. Wallner, Rectangular Young tableaux with local decreases and the density method for uniform random generation, in GASCom 2018: Random and Exhaustive Generation of Combinatorial Structures, CEUR Workshop Proceedings 2113 (2018), 60–68. 1, 2
  2. [2]C. Banderier and M. Wallner, Young tableaux with periodic walls: counting with the density method, Séminaire Lotharingien de Combinatoire 85B (2021), Article #47. 1, 2, 3
  3. [3]M. Borinsky, Generating asymptotics for factorially divergent sequences, Electronic Journal of Combinatorics 25 (2018), no. 4, #P4.1. 13DOI
  4. [4]Y.-S. Chang, M. Fuchs, H. Liu, M. Wallner, and G.-R. Yu, Enumerative and distributional results for d-combining tree-child networks, Advances in Applied Mathematics 157 (2024), Article 102704. 2arxiv.org/abs/2209.03850
  5. [5]Z. Lin, F. Liu, J. Liu, J. Liu, and G. Xin, Proof of a conjecture on Young tableaux with walls, arXiv:2601.09551. (2026). 2arxiv.org/abs/2601.09551
  6. [6]F. Lindemann, Ueber die Zahl π, Mathematische Annalen 20 (1882), 213–225. 11, 16
  7. [7]F. Liu and G. Xin, Simple generating functions for certain Young tableaux with periodic walls, arXiv:2401.14627. (2024). 2arxiv.org/abs/2401.14627
  8. [8]L. Lipshitz, D-finite power series, Journal of Algebra 122 (1989), no. 2, 353–373. 10DOI
  9. [9]M. Pons and J. Batle, Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks, Scientific Reports 11 (2021), 21875. 2DOI
  10. [10]R. P. Stanley, Differentiably finite power series, European Journal of Combinatorics 1 (1980), no. 2, 175–188. 4DOI
  11. [11]R. P. Stanley, Two poset polytopes, Discrete & Computational Geometry 1 (1986), 9–23. 5DOI
  12. [12]R. P. Stanley, Enumerative Combinatorics (volume 1), second Edition. Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, (2012). 1
  13. [13]R. P. Stanley, Enumerative Combinatorics (volume 2), second Edition. Cambridge Studies in Advanced Mathematics, vol. 208, Cambridge University Press, (2023). 4, 10

Paper details

vlnc:W_wmfc8sjw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents