Functional equation conjecture for well-aligned pairs

A complete proof of the functional equation for well-aligned pairs

Problem. MathDB #382424, “Functional equation conjecture for well-aligned pairs.”

Primary source. Hunter Spink and Vasu Tewari, Richardson tableaux and Schubert positivity, arXiv:2510.12391v2, revised July 29, 2026, Definition 2.1 and Conjecture 6.1. The source verifies the proposed identity through permutation size seven. OEIS A234289 specifies the conjectured sequence and its differential equation but does not identify or enumerate well-aligned pairs.

Theorem

Let $\mathcal W_n$ denote the set of well-aligned ordered pairs of permutations in $S_n$, including the unique empty pair in $\mathcal W_0$. Then the exponential generating function

$$W(t)=\sum_{n\geq 0}|\mathcal W_n|\frac{t^n}{n!}$$

satisfies the exact formal differential equation

$$\boxed{\displaystyle W'(t)=\frac{W(t)^2}{2-W(t)},\qquad W(0)=1.}$$

Consequently, the conjecture holds in every permutation size. More strongly, the complete ascent-run refinement of the enumeration satisfies an explicitly solvable formal transport equation.

1. The source definition and insertion of the minimum

For a permutation $v\in S_n$, write $\delta(v)\in S_{n-1}$ for the permutation obtained by deleting its entry $1$ and decreasing all remaining entries by one. The source calls $(v,w)$ aligned when, writing

$$i=v^{-1}(1),\qquad j=w^{-1}(1),$$

one has

$$i\leq j \quad\text{and}\quad v(i)<v(i+1)<\cdots<v(j). \tag{1}$$

The pair is well-aligned if it is aligned and $(\delta(v),\delta(w))$ is well-aligned. The empty pair is the initial object.

Fix an existing pair $(v,w)\in\mathcal W_n$. Increase every entry of both permutations by one. To construct an element of $\mathcal W_{n+1}$, insert the new entry $1$ independently into the two resulting words. Every well-aligned extension arises uniquely in this manner: deleting the new minimum recovers the old pair, and the only additional condition is (1).

Decompose $v$ into its maximal consecutive increasing runs. Suppose one such run has length $\ell\geq 1$, and insert the new minimum immediately before its $(p+1)$-st entry, where

$$0\leq p\leq \ell-1.$$

The insertion splits this run into a prefix of length $p$, omitted when $p=0$, and an increasing run of length

$$q=\ell-p+1\geq 2 \tag{2}$$

beginning with the new minimum. If the minimum is in position $i$ of the new first permutation, the permitted positions $j$ in the second permutation are precisely

$$j=i,i+1,\ldots,i+q-1. \tag{3}$$

Indeed, these and only these positions satisfy (1), because the increasing run beginning at position $i$ has exactly $q$ entries. Crucially, the number $q$ of permitted insertion positions is independent of $w$.

Every insertion gap except the final gap is uniquely the gap immediately before an entry in some increasing run. The remaining final gap appends the minimum to $v$; in this case condition (1) forces it to be appended to $w$ as well. This creates one new singleton run and gives exactly one extension.

2. The ascent-run derivation

Introduce commuting variables $u_1,u_2,\ldots$, put $u_0=1$, and assign weight $\deg u_j=j$. For a permutation $v$ whose increasing runs have lengths $\ell_1,\ldots,\ell_r$, let

$$\operatorname{run}(v)=\prod_{a=1}^{r}u_{\ell_a}.$$

Define the weighted counting polynomial

$$F_n(\boldsymbol u) =\sum_{(v,w)\in\mathcal W_n}\operatorname{run}(v), \qquad F_0=1. \tag{4}$$

On the polynomial ring $\mathbb Q[u_1,u_2,\ldots]$, define the derivation $D$ by $D(u_0)=0$, the Leibniz rule, and

$$D(u_\ell) =\sum_{p=0}^{\ell-1}(\ell-p+1)u_pu_{\ell-p+1} =\sum_{\substack{p\geq 0,\ q\geq 2\p+q=\ell+1}} q\,u_pu_q. \tag{5}$$

The term indexed by $(p,q)$ replaces an increasing run of length $\ell$ by the runs of lengths $p$ and $q$ described in (2), and its coefficient $q$ is exactly the number of second-permutation insertion positions in (3). The Leibniz rule selects which existing run is changed. The final-gap insertion contributes multiplication by $u_1$. Therefore the preceding insertion bijection proves, with no omission or overcount,

$$F_{n+1}=(D+u_1)F_n. \tag{6}$$

In particular, for the refined exponential generating function

$$F(t;\boldsymbol u) =\sum_{n\geq0}F_n(\boldsymbol u)\frac{t^n}{n!},$$

we obtain

$$\frac{\partial F}{\partial t}=DF+u_1F, \qquad F(0;\boldsymbol u)=1. \tag{7}$$

Every polynomial $F_n$ is homogeneous of weight $n$; hence all formal operations below are well-defined coefficientwise in the weight-completed polynomial ring.

3. Integrating the derivation

Let

$$a(t)=e^{tD}u_1, \qquad J(t)=\int_0^t a(s)\,ds.$$

Because $D$ commutes with its exponential,

$$DJ(t) =\int_0^t D e^{sD}u_1\,ds =\int_0^t\frac{\partial}{\partial s} \bigl(e^{sD}u_1\bigr)\,ds =a(t)-u_1. \tag{8}$$

Consequently $e^{J(t)}$ satisfies (7):

$$\begin{aligned} \frac{\partial}{\partial t}e^{J(t)} &=a(t)e^{J(t)},\\ De^{J(t)}+u_1e^{J(t)} &=\bigl(DJ(t)+u_1\bigr)e^{J(t)} =a(t)e^{J(t)}. \end{aligned}$$

The formal initial-value problem (7) has a unique solution, so

$$F(t;\boldsymbol u) =\exp\left(\int_0^t e^{sD}u_1\,ds\right). \tag{9}$$

To determine the integrand, introduce the auxiliary series

$$X(t,z)=\sum_{\ell\geq0}\bigl(e^{tD}u_\ell\bigr)z^\ell. \tag{10}$$

Equation (5) gives the exact generating-series identity

$$\begin{aligned} D\left(\sum_{\ell\geq0}u_\ell z^\ell\right) &=\sum_{p\geq0}\sum_{q\geq2} q\,u_pu_qz^{p+q-1}\\ &=\left(\sum_{p\geq0}u_pz^p\right) \left(\sum_{q\geq2}q\,u_qz^{q-1}\right). \end{aligned}$$

Since the exponential of a derivation preserves products,

$$\boxed{\displaystyle \frac{\partial X}{\partial t} =X\left(\frac{\partial X}{\partial z}-a(t)\right), \qquad a(t)=[z]X(t,z). } \tag{11}$$

The constant term of $X$ is always $e^{tD}u_0=1$.

4. Specialization and the formal Burgers equation

Now specialize every run variable to one. Write $X(t,z)$ and $a(t)$ again for their specialized series, and set

$$W(t)=F(t;1,1,\ldots).$$

By (9),

$$W'(t)=a(t)W(t), \qquad W(0)=1. \tag{12}$$

Since $u_\ell=1$ for every $\ell\geq0$, equation (10) has initial data

$$X(0,z)=\sum_{\ell\geq0}z^\ell=\frac{1}{1-z}. \tag{13}$$

Introduce

$$Y(t,z)=W(t)X(t,z), \qquad \tau(t)=\int_0^t\frac{ds}{W(s)}. \tag{14}$$

Equations (11) and (12) imply

$$\begin{aligned} \frac{\partial Y}{\partial t} &=W'X+W\frac{\partial X}{\partial t}\\ &=aWX+WX\left(\frac{\partial X}{\partial z}-a\right)\\ &=\frac{Y}{W}\frac{\partial Y}{\partial z}. \end{aligned} \tag{15}$$

Because $\tau'(0)=1$, the series $\tau(t)$ has a compositional inverse. Regarding $Y$ as a function of $(\tau,z)$, (15) becomes the formal inviscid Burgers equation

$$\frac{\partial Y}{\partial\tau} =Y\frac{\partial Y}{\partial z}, \qquad Y(0,z)=\frac{1}{1-z}. \tag{16}$$

Its unique formal solution is characterized by

$$Y(\tau,z)=\frac{1}{1-z-\tau Y(\tau,z)}. \tag{17}$$

Indeed, the right-hand side determines coefficients recursively in $\tau$, has the required initial condition, and implicit differentiation gives $Y_\tau=Y Y_z$. Equivalently,

$$Y(\tau,z) =\frac{1-z-\sqrt{(1-z)^2-4\tau}}{2\tau}. \tag{18}$$

5. Recovering the conjectured differential equation

The constant term of $X(t,z)$ is one; therefore

$$Y(t,0)=W(t). \tag{19}$$

Substituting $z=0$ into (17) yields

$$W(t)=\frac{1}{1-\tau(t)W(t)},$$

or equivalently

$$\tau(t)=\frac{W(t)-1}{W(t)^2}. \tag{20}$$

Differentiate (20) and use $\tau'(t)=1/W(t)$:

$$\frac{1}{W(t)} =\frac{2-W(t)}{W(t)^3}W'(t).$$

Since $W(0)=1$, both $W(t)$ and $2-W(t)$ are formally invertible. We obtain

$$\boxed{\displaystyle W'(t)=\frac{W(t)^2}{2-W(t)}. }$$

This is exactly Conjecture 6.1 for all $n\geq0$.

For completeness, integration also gives the implicit closed form

$$t=2-\frac{2}{W(t)}-\log W(t), \tag{21}$$

so that, writing $U(t)=W(t)-1$,

$$t=\frac{2U(t)}{1+U(t)}-\log\bigl(1+U(t)\bigr). \tag{22}$$

The initial exact counts are

$$\bigl|\mathcal W_n\bigr| =1,1,3,17,147,1729,25827,468593,10012083, 246287521,6856204803,\ldots.$$

The source checked only the terms through $n=7$; the derivation above establishes the entire infinite sequence and its stronger ascent-run-refined transport equation.