Catalan-type formula for transitive partitions of the complete directed graph

We prove Conjecture 3.13. Here the directed graph is the acyclic tournament with edge set $I_n=\{(i,j):1\leq i<j\leq n\}$. Thus we count partitions of $I_n$ into $n-2$ nonempty blocks such that, writing $c(i,j)$ for the block containing $(i,j)$,

$$c(i,k)\in\{c(i,j),c(j,k)\} \qquad(i<j<k).$$

Block names are only notation: the blocks are not separately labeled. Let $t_n$ be this count, and let $C_m=\frac{1}{m+1}\binom{2m}{m}$ be the Catalan numbers. We will show

$$\begin{aligned} t_n&=\binom{n-1}{2}C_{n-1}\\ &\quad-(n-2)C_{n-2}. \end{aligned} \tag{1}$$

The maximal, $n-1$-block case is the Catalan enumeration of Adin, Berenstein, Greenstein, Li, Marmor and Roichman, Theorem 2.17. We include the needed decomposition and then analyze the case with one fewer block.

Consecutive edges and cuts

Repeated use of transitivity gives

$$c(i,j)\in\{c(i,i+1),\ldots,c(j-1,j)\}. \tag{2}$$

In particular, every block occurs on the consecutive-edge path. A coloring with $n-1$ blocks has distinct colors on that path; one with $n-2$ blocks has exactly one color occurring twice there, with every other path color occurring once.

Call $r\in\{1,\ldots,n-1\}$ a cut if all edges $(i,j)$ with $i\leq r<j$ have the same color. That color must be $c(1,n)$.

If $c(1,n)=a$ occurs on the consecutive-edge path only at $r$, then $r$ is a cut. Indeed, for $j>r$, transitivity and (2) force $c(1,j)=a$: the other part of a split at $j$ cannot contain $a$. For $i\leq r$, splitting $(1,j)$ at $i$ similarly forces $c(i,j)=a$. The endpoint cases $i=1$ or $j=n$ are immediate.

Let $M_n$ count the maximal, $n-1$-block partitions, with $M_1=1$ for the empty edge set. Such a partition has a unique cut. Its two restrictions are maximal, their color sets are disjoint, and the cut color is new. Conversely, these data always give a transitive partition. Hence

$$M_1=1,\qquad M_n=\sum_{r=1}^{n-1}M_rM_{n-r}=C_{n-1}.$$

Writing $M(z)=\sum_{n\geq1}M_nz^n$, we therefore have

$$M=z+M^2. \tag{3}$$

Partitions without a cut

We now classify an $n-2$-block partition having no cut. Its outer color $a=c(1,n)$ must occur twice on the path, say at positions $p<q$. Put

$$A=[1,p],\qquad B=[p+1,q],\qquad D=[q+1,n].$$

All edges from $A$ to $D$ have color $a$, by the same splitting argument used above. No edge inside any of $A,B,D$ has color $a$, by (2).

Let $L$ consist of vertices of $B$ having some non-$a$ edge to $A$, and let $R$ consist of vertices of $B$ having some non-$a$ edge to $D$. Both are nonempty, since otherwise $p$ or $q$ would be a cut. They are disjoint: a vertex in both would give an $A$--$B$--$D$ triangle whose outer edge has color $a$ and whose two other edges do not. Consequently, every $A$--$R$ edge and every $L$--$D$ edge has color $a$.

Every vertex of $R$ precedes every vertex of $L$. Otherwise, take $\ell<r$ with $\ell\in L$, $r\in R$, and $i\in A$ with $c(i,\ell)\ne a$. Since $c(i,r)=a$, transitivity forces $c(\ell,r)=a$, impossible inside $B$.

For $r\in R$ and $\ell\in L$, choose $i\in A$ and $j\in D$ witnessing their non-$a$ contacts. Applying transitivity to $i<r<\ell$ and $r<\ell<j$ yields

$$c(i,\ell)=c(r,\ell)=c(r,j). \tag{4}$$

Fixing one vertex in each of $R,L$ and then varying the choices shows that all non-$a$ contacts in question, and all $R$--$L$ edges, have one common color $b\ne a$. By (2), $b$ occurs on the path inside $B$, where every path color occurs only once.

There are no remaining vertices in $B$. To see this, let $v\in B\setminus(R\cup L)$. Its edges to $A$ and $D$ all have color $a$. For any $r\in R$, transitivity with a non-$a$ contact from $r$ to $D$ shows that $v<r$ would force an $a$-colored edge inside $B$. Thus $r<v$, and the same triangle gives $c(r,v)=b$. Similarly, $v<\ell$ and $c(v,\ell)=b$ for every $\ell\in L$. All such remaining vertices would therefore lie between $R$ and $L$, with color $b$ on both consecutive-edge boundaries. This contradicts the uniqueness of $b$ on the path. Hence $B$ is the consecutive concatenation of the two nonempty intervals $R,L$.

Every $A$--$L$ edge has color $b$. Indeed, a triangle through a vertex of $R$ shows that its color is either $a$ or $b$. For a fixed $\ell\in L$, two different such colors at vertices of $A$ would, by transitivity, force an internal edge of $A$ to have color $a$ or $b$. Neither color occurs on the path inside $A$, so this is impossible. Since $\ell$ has a non-$a$ contact to $A$, all these colors are $b$. The same argument gives color $b$ on every $R$--$D$ edge.

We have obtained four consecutive, nonempty intervals with the following inter-interval colors:

Pair	Color
$A,R$	$a$
$A,L$	$b$
$A,D$	$a$
$R,L$	$b$
$R,D$	$b$
$L,D$	$a$

Inside each interval the coloring is maximal; these internal color sets are pairwise disjoint and avoid $a,b$, since all the other consecutive-edge colors are distinct.

Conversely, any four maximal interval colorings with disjoint color sets, joined by this table using two new colors, give a transitive partition with $n-2$ blocks and no cut. Transitivity is checked on the four triples of distinct intervals; triples meeting fewer intervals are immediate. Every possible cut has crossing edges of both colors $a,b$. The decomposition is unique: $p,q$ are the positions of the repeated path color, and the boundary between $R,L$ is the position of $b$.

Thus the generating function for partitions with no cut is

$$M(z)^4. \tag{5}$$

Counting the partitions with cuts

Set $t_1=t_2=0$ and $T(z)=\sum_{n\geq1}t_nz^n$. Count pairs consisting of an $n-2$-block partition and a marked cut. If the two sides have sizes $r,s$, where $r+s=n$, there are exactly three possibilities:

• The left restriction has one fewer block than maximal, the right is maximal, and all their colors and the cut color are distinct: $t_rM_s$ possibilities.
• The right restriction has one fewer block than maximal, with the analogous distinctness: $M_rt_s$ possibilities.
• Both restrictions are maximal, and exactly one pair among their colors and the cut color is identified. The pair is either one color from each side, or the cut color and one color from either side. This gives

$$\begin{aligned} &\bigl((r-1)(s-1)+(r-1)+(s-1)\bigr)\\ &\qquad\cdot M_rM_s=(rs-1)M_rM_s. \end{aligned}$$

These cases exhaust the possibilities because the total deficit from $n-1$ colors is exactly one. All listed identifications preserve transitivity, and they give distinct partitions with the marked cut. Consequently, the generating function for marked cuts is

$$2MT+(zM')^2-M^2. \tag{6}$$

A partition has at most two cuts: all cuts have color $c(1,n)$, so their consecutive edges have the same color. If there are two cuts, the three intervening intervals are maximal, with disjoint internal colors and one new common color between intervals. Conversely, every such choice has exactly those two cuts. Their generating function is $M^3$.

Therefore, subtracting one extra count for each two-cut partition and adding the no-cut partitions from (5),

$$\begin{aligned} (1-2M)T&=(zM')^2-M^2\\ &\quad-M^3+M^4. \end{aligned} \tag{7}$$

Extracting the coefficient

Equation (3) gives

$$M'=\frac{1}{1-2M},\qquad M''=\frac{2}{(1-2M)^3}.$$

Substituting these identities and $z=M-M^2$ into (7), and simplifying, gives

$$\begin{aligned} T&=\frac{z^2}{2}M''-z(1+z)M'\\ &\quad+(1+z)M. \end{aligned} \tag{8}$$

All operations are in formal power series; $M(0)=0$, so the denominator $1-2M$ is invertible. Since $[z^n]M=C_{n-1}$, equation (8) gives, for every $n\geq3$,

$$\begin{aligned} t_n &=\left(\frac{n(n-1)}2-n+1\right)C_{n-1}\\ &\quad-(n-2)C_{n-2}\\ &=\binom{n-1}{2}C_{n-1}-(n-2)C_{n-2}. \end{aligned}$$

Finally, substituting the factorial formulas for the Catalan numbers yields

$$\boxed{\displaystyle t_n=(n-2)\binom{2n-3}{n}+\binom{2n-4}{n}},$$

with $\binom{m}{n}=0$ when $m<n$. In particular, the boundary case $n=3$ gives the unique one-block partition. This proves the conjecture.