Path-count recurrence for generalized action graphs of the super Catalan numbers

Path-count recurrence for the super-Catalan action graphs

We prove Conjecture 5.5 of Caldwell, Cochran, Glisson, Jennings, McDicken, Proctor, Klanderman and Tebbe, arXiv:2507.22719v1.

For an actual vertex $x$ of $G_n$, let $p_n(x,r)$ be the number of directed paths of length $r$ from $x$ to a vertex labeled $n$. For integers $v$ and $r$, let

$$K_{r,v,n}=\sum_{\substack{ x\in V(G_n)\\ \operatorname{label}(x)=v }}p_n(x,r).$$

Thus $K_{r,v,n}$ counts all directed paths of length $r$ in $G_n$ whose initial vertex has label $v$ and whose terminal vertex has label $n$, exactly as in the source.

Integrality of the construction

Definition 5.2 asks us, for each $x\in V(G_n)$ and each $0\le i\le n$, to add

$$\frac{2}{2^i}p_n(x,i)$$

new vertices. We first prove that these numbers are integers. In fact, simultaneously with the construction of the graphs, we prove the stronger assertion

$$\begin{gathered} 2^r\mid p_n(x,r)\\ \text{for every }x\in V(G_n)\\ \text{ and every }r\ge 0. \end{gathered} \tag{1}$$

For $G_0$, the only nonzero path count is $p_0(x,0)=1$, so (1) holds. Suppose that $G_n$ has been constructed and satisfies (1). For $i=0$, the required number of new vertices is $2p_n(x,0)$; for $i\ge1$, divisibility (1) shows that $2^{1-i}p_n(x,i)$ is an integer. Hence $G_{n+1}$ is well-defined.

It remains to verify (1) for $G_{n+1}$. A newly added vertex has one path of length zero to label $n+1$ and no positive-length path to that label, so the assertion is immediate for new vertices. Let $x$ be an old vertex and let $r\ge1$. Delete the final edge of a path of length $r$ from $x$ to a new vertex. If its old endpoint is $z$, then the construction supplies, for every $i$, exactly $2^{1-i}p_n(z,i)$ choices for the final edge. Concatenating the initial path of length $r-1$ with the path of length $i$ counted at $z$ gives

$$p_{n+1}(x,r) =\sum_{i=0}^{n}\frac{2}{2^i}p_n(x,r-1+i). \tag{2}$$

Every summand in (2) is divisible by $2^r$: when $r-1+i>0$, this follows from

$$2^{r-1+i}\mid p_n(x,r-1+i),$$

and the factor $2^{1-i}$; the sole remaining case is $r=1,i=0$, where the factor $2$ gives the same conclusion. Thus (1) holds for $G_{n+1}$, completing the simultaneous induction.

The aggregate recurrence

Now fix $n\ge0$, $0\le v\le n+1$, and $\ell\ge1$. Every path of length $\ell$ in $G_{n+1}$ from a vertex labeled $v$ to a vertex labeled $n+1$ has a unique last edge $x\to y$, where $x\in V(G_n)$ and $y$ is one of the new vertices. Removing that last edge leaves a path of length $\ell-1$ from a vertex labeled $v$ to $x$. Conversely, any such old path, followed by any new edge out of $x$, gives exactly one path counted by $K_{\ell,v,n+1}$. Expanding the construction count at $x$ therefore gives

$$\begin{aligned} &K_{\ell,v,n+1}\\ &=\sum_{i=0}^{n}\frac{2}{2^i} \sum_{\substack{P:\ |P|=\ell-1\\ \operatorname{label}(\operatorname{start}P)=v}} p_n(\operatorname{end}P,i). \end{aligned} \tag{3}$$

For fixed $i$, the pairs counted by the inner sum consist of a path $P$ of length $\ell-1$ followed by a path of length $i$ from its endpoint to a vertex labeled $n$. Concatenation is a bijection from these pairs to the paths counted by $K_{\ell-1+i,v,n}$. Hence (3) becomes

$$K_{\ell,v,n+1} =\sum_{i=0}^{n}\frac{2}{2^i}K_{\ell-1+i,v,n}. \tag{4}$$

Every edge in these inductively constructed graphs goes from a smaller label to a larger label. Consequently, a path from label $v$ to label $n$ has length at most $n-v$. Thus

$$\begin{gathered} K_{\ell-1+i,v,n}=0\\ \text{whenever}\qquad i>n+1-\ell-v. \end{gathered}$$

Deleting the zero terms from (4) gives precisely the conjectured recurrence

$$\boxed{ K_{\ell,v,n+1} =\sum_{i=0}^{n+1-\ell-v}\frac{2}{2^i}K_{\ell-1+i,v,n}. } \tag{5}$$

When $n+1-\ell-v<0$, the sum in (5) is empty and equals zero; the left side is also zero because no path with those parameters can exist. The case $\ell=0$ is the separately stated table boundary: it counts the newly added vertices themselves and is not part of this recurrence. This proves Conjecture 5.5.