Counting red–blue Motzkin excursions

Let $a_m$ be the number of length-$m$ Motzkin excursions satisfying the red–blue rule of Wu–Eu–Ku–Shih, Question 8.5 of arXiv:2509.16872v2. Thus the letters are $U,D,H$, the height never becomes negative and ends at zero, and an up or down step is blue when the number of preceding horizontal steps is even and red otherwise. In every prefix,

$$\begin{aligned} \#D_{\mathrm{red}}&\leq\#U_{\mathrm{blue}},\\ \#D_{\mathrm{blue}}&\leq\#U_{\mathrm{red}}. \end{aligned}$$

All paths satisfying this rule are counted; no additional condition concerning cycle Petrie matrices is imposed.

Let $b_n$ count permutations of $[n]=\{1,\ldots,n\}$ with no increasing subsequence of length four. Let $c_n$ count set partitions of $[n]$ whose arcs are colored with two colors, with no crossing between arcs of the same color. Here a block $\{i_1<\cdots<i_j\}$ has the arcs $(i_1,i_2),\ldots,(i_{j-1},i_j)$; arcs $(i,j)$ and $(k,l)$ cross when $i<k<j<l$ or $k<i<l<j$. Colors belong to arcs, not to blocks or singletons.

Theorem. For every integer $n\geq1$,

$$a_{2n-1}=b_n, \qquad a_{2n}=c_n. \tag{1}$$

These are the two identities asked about in Question 8.5 and recorded in A389602, with $b_n$ and $c_n$ given by A005802 and A216947.

The idea is to keep the two nonnegative differences in the red–blue rule as coordinates. This turns a path into a walk whose allowed direction changes at every horizontal step. Reversible local flips put these walks into a fixed direction order. Odd-length excursions become pairs of equal-size tableaux, giving a bijection with the required permutations. Even-length excursions become a different family of tableau pairs. For that family, a finite signed-walk cancellation gives the colored-partition count. The even argument is a combinatorial counting proof; it does not assert a direct positive bijection to colored partitions.

1. Two coordinates for the prefix rule

For an admissible prefix, put

$$\begin{aligned} x&=\#U_{\mathrm{blue}}-\#D_{\mathrm{red}},\\ y&=\#U_{\mathrm{red}}-\#D_{\mathrm{blue}}, \end{aligned} \tag{2}$$

and let $p\in\{0,1\}$ be the parity of the number of horizontal steps already read. The two prefix conditions are exactly $x,y\geq0$. Ordinary height is $x+y$, so its nonnegativity follows from them. The prefix is an excursion precisely when $x=y=0$ at the end.

At phase $p=0$, a $U$ increases $x$ and a $D$ decreases $y$. At phase $p=1$, a $U$ increases $y$ and a $D$ decreases $x$. The letter $H$ changes $p$ to $1-p$ without changing $x,y$.

For an excursion of length $m$, the number of up steps equals the number of down steps. Consequently the number of horizontal steps has the same parity as $m$:

$$p\equiv m\pmod2. \tag{3}$$

2. Reversible tandem flips

Use the three forward steps

$$\begin{aligned} f_1&=(1,0),\\ f_2&=(-1,1),\\ f_3&=(0,-1), \end{aligned} \tag{4}$$

and the backward steps $\bar f_i=-f_i$, with indices interpreted cyclically modulo three. A direction word specifies whether each step is forward, denoted $F$, or backward, denoted $B$. All walks below remain in $\mathbb N^2$.

The following flips and their coherence are due to Courtiel–Elvey Price–Marcovici, Definition 10, Theorem 6, and Proposition 14:

$$(f_i,\bar f_j)\longleftrightarrow (\bar f_j,f_i)\qquad(i\ne j), \tag{5}$$ $$(f_i,\bar f_i)\longleftrightarrow (\bar f_{i-1},f_{i-1}), \tag{6}$$

and, at the last position only,

$$f_i\longleftrightarrow\bar f_{i-1}. \tag{7}$$

Flip lemma. Fix a starting point and a walk length. The flips give a bijection between walks with any two prescribed direction words. Moreover, starting from a fixed walk, every flip sequence reaching a prescribed direction word gives the same final walk.

The cited theorem is stated for a triangle $x,y\geq0$, $x+y\leq L$. It applies here by choosing $L$ at least the starting coordinate sum plus the walk length. Every quadrant walk of that length, including every intermediate walk in a flip sequence, lies in this triangle.

For clarity, quadrant preservation can also be checked directly. In (5), a coordinate that becomes negative after swapping could have been repaired by the other step only if the two steps were opposite, which is excluded. The forward zero pairs in (6), for $i=1,2,3$, are available respectively at every point, when $x>0$, and when $y>0$; their matched backward pairs have exactly the same availability. The three replacements in (7) have these same respective conditions. Thus each local operation is reversible within the quadrant. Coherence is the additional assertion of the cited Proposition 14.

Write $\Gamma$ for the resulting all-forward to all-backward bijection with starting point fixed. One explicit procedure flips the last forward step, moves that backward step left across the remaining forward steps using (5)–(6), and repeats. Reverse these operations for $\Gamma^{-1}$.

Two consequences will be used. Swap flips preserve the endpoint. Therefore, within one coherent flip class, the endpoint depends only on the number of backward steps, not on their positions. Also,

$$\bar f_{i-1}-f_i=f_{i+1}. \tag{8}$$

Thus increasing the backward-step count by one moves the endpoint by one forward step; decreasing that count by one moves it by one backward step. To change the count monotonically, move a step of the required direction to the end, apply (7), and repeat. The successive endpoints remain in the quadrant.

3. A bijection for every admissible prefix

Expand a source prefix into a walk starting at $(1,0)$ by the following table.

Phase before the letter	$U$	$D$	$H$
$p=0$	$f_1$	$f_3$	$f_2$, then change to phase $1$
$p=1$	$\bar f_3$	$\bar f_1$	$\bar f_2$, then change to phase $0$

At every prefix the expanded position is

$$Z=(x+1-p,\ y+p). \tag{9}$$

For phase $0$ its first coordinate is positive; for phase $1$ its second coordinate is positive. These protected coordinates make both horizontal replacements legal. The other replacements are legal exactly when the corresponding source steps are legal.

Normalize the expansion recursively. More generally, at either phase and any starting point with its phase's protected coordinate positive, turn an admissible expanded suffix into a walk all of whose steps have that phase's direction.

1. Keep its first step.
2. If that step is not a middle step, normalize the remaining suffix in the same phase.
3. If it is a middle step, normalize the suffix in the opposite phase, then apply $\Gamma$ or $\Gamma^{-1}$ to that suffix to restore the first step's direction.

The empty suffix is unchanged. All conversions of a suffix fix its starting point.

There is an explicit inverse. Read the first step of a uniform-direction walk. At phase $0$, steps $f_1,f_3,f_2$ give $U,D,H$, respectively; at phase $1$, steps $\bar f_3,\bar f_1,\bar f_2$ give $U,D,H$. After a middle step, first convert the uniform remaining suffix to the opposite direction and continue in the opposite phase. Otherwise continue in the same phase.

The protected-coordinate condition is preserved after the first step in each branch. In particular, after a middle step the newly protected coordinate is positive. Induction on suffix length proves that the inverse always produces an admissible prefix and reverses the normalization. This proves a bijection for every length, not just an equality of recurrences.

Every forward quadrant walk starting at the origin has first step $f_1$. Prepending this step to the normalized expansion therefore gives a bijection

$$\begin{gathered} \left\{\begin{gathered} \text{admissible prefixes}\\ \text{of length }m \end{gathered}\right\}\\ \longleftrightarrow\\ \left\{\begin{gathered} \text{forward quadrant walks}\\ \text{of length }m+1\text{ from }0 \end{gathered}\right\}. \end{gathered} \tag{10}$$

The empty prefix maps to the one-step walk $f_1$. The construction is not generally endpoint-preserving; the next two sections establish exactly the endpoint restrictions needed.

Include the initial $f_1$ in the unnormalized expansion, and let $N=m+1$ and $k$ be its number of backward steps. The nonhorizontal contribution to $\#F-\#B$ is $x-y$; horizontal steps contribute $p$, since their phases alternate. Hence

$$\begin{gathered} \#F-\#B=x-y+p+1,\\ k=\frac{N-x+y-p-1}{2}. \end{gathered} \tag{11}$$

Every normalization in (10) is a sequence of the flips, so the expansion and the normalized walk belong to the same coherent class.

A forward walk from $(a,b)$ to $0$ must have length at least $2a+b$. Indeed, if its step counts are $r_1,r_2,r_3$, then $r_2=r_1+a$ and $r_3=r_1+a+b$, so its length is $3r_1+2a+b$. Similarly, a backward walk from $(a,b)$ to $0$ has length at least $a+2b$.

4. Odd-length excursions and permutations

Let $m=2n-1$, so $N=2n$. After (10), use the flip lemma to prescribe the direction word $F^nB^n$.

Suppose first that the source prefix is an excursion. Then $x=y=0$, $p=1$, its expanded endpoint is $(0,1)$, and (11) gives $k=n-1$. Its last horizontal step is $f_2$. All following steps are $\bar f_1$ or $\bar f_3$, so (5) commutes this $f_2$ unchanged to the end. The last-step flip

$$f_2\longmapsto\bar f_1$$

increases $k$ to $n$ and moves the endpoint by $f_3=(0,-1)$, to $0$. Swaps arrange the direction word as $F^nB^n$. Coherence identifies this result with the prescribed normalization.

Conversely, suppose the normalized $F^nB^n$ walk ends at $0$. For the original expanded prefix,

$$\begin{gathered} Z=(x+1-p,y+p),\\ n-k=\frac{x-y+p+1}{2}. \end{gathered} \tag{12}$$

If $n-k\geq0$, the endpoint consequence of the flip lemma would give a forward walk from $Z$ to $0$ of length $n-k$. The minimum length minus this available length is

$$\begin{gathered} (2Z_1+Z_2)-(n-k)\\ =\frac32(x+y+1-p). \end{gathered} \tag{13}$$

This is nonnegative and can be zero only when $x=y=0$, $p=1$. If $n-k<0$, the analogous backward minimum gives

$$\begin{gathered} (Z_1+2Z_2)-(k-n)\\ =\frac32(x+y+1+p)>0, \end{gathered} \tag{14}$$

which is impossible. Thus an origin endpoint occurs exactly for source excursions.

An $F^nB^n$ excursion splits into two forward walks of length $n$ from $0$ to the same point, by reversing the backward half. To encode a forward walk as a standard Young tableau, place label $j$ into row $i$ when its $j$th step is $f_i$. If the row lengths read so far are $r_1,r_2,r_3$, the coordinates are $r_1-r_2,r_2-r_3$. The quadrant condition is precisely the condition that these are valid successive Young diagrams. This is a bijection with standard tableaux having at most three rows.

The common endpoint and the common length determine the same final shape for the two tableaux. Robinson–Schensted identifies such pairs with permutations whose longest decreasing subsequence has length at most three. Value complementation, $w_j\mapsto n+1-w_j$, then gives the permutations counted by $b_n$. These classical tableau facts are recalled, for example, in Stanley, Section 2 and Theorem 2.

All steps are reversible, proving the odd identity in (1) bijectively. At $n=1$, the sole source excursion is $H$, and its normalized walk is $f_1\bar f_1$.

5. Even-length excursions and unequal-size tableau pairs

Let $m=2n$, $n\geq1$, so $N=2n+1$. This time prescribe the direction word

$$F^{n+2}B^{n-1}. \tag{15}$$

For a source excursion, $x=y=p=0$, the expanded endpoint is $(1,0)$, and $k=n$. A nonempty source excursion cannot have no horizontal step: in phase $0$ the first down step would violate $y\geq0$, and a word containing only up steps is not an excursion. The number of horizontal steps is even, so there are at least two.

The last horizontal step is therefore $\bar f_2$, followed only by $f_1$ or $f_3$. Commute it unchanged to the end and flip $\bar f_2$ to $f_3$. This decreases the backward count to $n-1$ and moves the endpoint by $(-1,0)$, to $0$.

For the converse, put

$$\begin{aligned} d&=(n-1)-k\\ &=\frac{x-y+p-2}{2}. \end{aligned} \tag{16}$$

If $d\geq0$, the needed forward endpoint walk is too short, since

$$\begin{gathered} (2Z_1+Z_2)-d\\ =\frac32(x+y+2-p)>0. \end{gathered} \tag{17}$$

If $d<0$, the backward minimum minus the available length is

$$\begin{gathered} (Z_1+2Z_2)-(-d)\\ =\frac32(x+y+p). \end{gathered} \tag{18}$$

An origin endpoint therefore requires $x=y=p=0$. As before, the prefix bijection restricts to a bijection between even source excursions and excursions with direction word (15).

The two forward pieces have lengths $n+2$ and $n-1$ and the same endpoint. Their tableau shapes consequently differ by $(1,1,1)$. Writing $f^\lambda$ for the number of standard tableaux of shape $\lambda$, and padding shapes with zeros to three parts, this also gives

$$a_{2n} =\sum_{\substack{\lambda\vdash n-1\\ \ell(\lambda)\leq3}} f^\lambda f^{\lambda+(1,1,1)}. \tag{19}$$

To obtain the even identity in (1), it remains to count this excursion family by colored partitions.

6. Two signed walk enumerations

Put $q=n-1\geq0$. Let $\operatorname{CT}$ denote the constant coefficient of a Laurent polynomial in the specified variables. Define

$$\begin{gathered} F(x,y)=x+\frac yx+\frac1y,\\ B(x,y)=\frac1x+\frac xy+y. \end{gathered} \tag{20}$$

The number of quadrant excursions with direction word $F^{q+3}B^q$ is

$$\operatorname{CT}_{x,y} \Delta F^3\bigl(FB\bigr)^q, \tag{21}$$

where

$$\begin{aligned} \Delta(x,y) ={}&1-\frac y{x^2}-\frac x{y^2}\\ &+\frac1{x^3}+\frac1{y^3} -\frac1{x^2y^2}. \end{aligned} \tag{22}$$

Here is the reflection argument, including the prescribed direction order. Shift the start and end to $\rho=(1,1)$, and use the reflections

$$\begin{gathered} (u,v)\mapsto(-u,u+v),\\ (u,v)\mapsto(u+v,-v). \end{gathered}$$

Their six-element group permutes the forward steps among themselves and the backward steps among themselves. Sum unrestricted walks from $w\rho$ to $\rho$ with the sign of $w$. The signed displacement monomials $x^{(w\rho-\rho)_1}y^{(w\rho-\rho)_2}$ are precisely (22).

Cancel walks meeting a wall by reflecting the part before the last wall encounter, equivalently the first wall encounter when read backwards from the endpoint. If both walls are met at the same vertex, choose a fixed one of them. Reflection preserves the prescribed forward/backward direction at every position and reverses the sign. Its suffix is unchanged, so the chosen last wall encounter is unchanged and the operation is an involution. The steps cannot pass from positive to negative in a coordinate without visiting zero. Hence every walk starting in another chamber meets a wall, and the uncanceled walks are exactly the positive-chamber walks from $\rho$ to itself. Translating back gives (21).

The colored-partition model is older. Marberg's Theorems 1.6 and 1.7 give

$$c_n=\operatorname{CT}_{a,b}M(a,b)P(a,b)^q, \tag{23}$$

with

$$\begin{aligned} P={}&3+a+b+a^{-1}\\ &+b^{-1}+a/b+b/a \end{aligned} \tag{24}$$

and

$$\begin{aligned} M={}&1-a^2/b-b^2/a\\ &+a^3+b^3-a^2b^2. \end{aligned} \tag{25}$$

In this model the coefficient $3$ represents three distinct zero-step choices. There are $q=n-1$ steps, not $n$.

One can see the walk interpretation directly. Scan a colored partition from left to right, closing the incoming arc before opening the outgoing arc at each vertex. Keep one last-in-first-out stack per color. Closing the top of the appropriate stack is equivalent to the absence of same-colored crossings. Conversely these operations reconstruct all arcs and hence all blocks uniquely.

The incoming operation at vertex $1$ and the outgoing operation at vertex $n$ are forced stays. Remove them, and pair the outgoing operation at vertex $i$ with the incoming operation at vertex $i+1$. There are nine choices: the six nonzero steps of $P$, and three zero choices consisting of two stays or an opening immediately followed by a closing of either one color. Each pair stays in the quadrant exactly when its endpoint does; an opening precedes a closing, so the intermediate operation introduces no extra boundary restriction. Thus these are precisely the $q$-step quadrant excursions with step polynomial $P$.

The same reflection argument as above counts these excursions with $\Delta(a,b)P^q$. Both reflections preserve this six-direction step set and the three zero labels. Finally invert both variables: $P(a^{-1},b^{-1})=P(a,b)$ and $\Delta(a^{-1},b^{-1})=M(a,b)$, which gives (23). This derivation makes both the length shift and the zero-step multiplicity explicit.

7. Putting the two counts in the same variables

Set

$$a=x^2/y,\qquad b=xy. \tag{26}$$

The map on exponent pairs has determinant $3$ and is injective. A Laurent monomial in $a,b$ becomes constant in $x,y$ if and only if its original exponents are both zero. Thus this substitution preserves constant coefficients; there is no factor of three.

Direct multiplication gives

$$\begin{gathered} FB=P,\\ \Delta=D\\ =(1-a^{-1})(1-a/b)(1-b^{-1}), \end{gathered} \tag{27}$$

and

$$\begin{gathered} F^3=C\\ =ab+b/a^2+a/b^2\\ +3P-3. \end{gathered} \tag{28}$$

Consequently (21) becomes

$$a_{2n}=\operatorname{CT}_{a,b}DCP^q. \tag{29}$$

We will prove $\operatorname{CT}(DC-M)P^q=0$ for every $q\geq0$ by a finite signed cancellation.

Define the six-term Laurent polynomials

$$\begin{aligned} S&=\frac{(a-1)(a-b)(b-1)}{ab}\\ &=a-b-a/b+b/a\\ &\quad+b^{-1}-a^{-1}, \end{aligned} \tag{30}$$ $$\begin{aligned} T&=\frac{(a-b^2)(a^2-b)(ab-1)}{a^2b^2}\\ &=a^2/b+b^2/a+(ab)^{-1}\\ &\hspace{8mm}-ab-a/b^2-b/a^2, \end{aligned} \tag{31}$$

and set

$$\begin{aligned} L={}&ab+b/a^2+a/b^2\\ &+(ab)^{-1}+a^2/b+b^2/a,\\ H&=L+6P-6. \end{aligned} \tag{32}$$

The definitions imply

$$\begin{gathered} D=-S/b,\\ C=(H-T)/2,\\ M=abT. \end{gathered} \tag{33}$$

Let $G$ be the twelve monomial substitutions generated by

$$\begin{gathered} r:(a,b)\mapsto(b,b/a),\\ s:(a,b)\mapsto(b,a). \end{gathered} \tag{34}$$

These substitutions preserve constant coefficients. They form the dihedral group with elements $r^j$ and $sr^j$, $0\leq j<6$. Direct substitution shows that $P,L,H$ are invariant and

$$\begin{array}{c|rr} &r&s\\ \hline S&-S&-S\\ T&-T&T \end{array} . \tag{35}$$

Write $\chi_S(g),\chi_T(g)\in\{1,-1\}$ for these signs. The six-term expressions give

$$\sum_{g\in G}\chi_S(g)g(b^{-1})=2S, \tag{36}$$ $$\sum_{g\in G}\chi_S(g)\chi_T(g)g(b^{-1})=0, \tag{37}$$ $$\sum_{g\in G}\chi_T(g)g(ab)=-2T. \tag{38}$$

For example, the orbit of $b^{-1}$ consists of the six axial monomials in $P-3$, each appearing twice, and its signs give (36)–(37). The orbit of $ab$ consists of the six monomials in $L$, again each twice, giving (38). Using (33) therefore yields

$$\begin{gathered} \sum_{g\in G}g(DC)=-S^2H,\\ \sum_{g\in G}g(M)=-2T^2. \end{gathered} \tag{39}$$

8. The signed cancellation

For Laurent polynomials define

$$\begin{aligned} \{A,B\} &=(a\partial_aA)(b\partial_bB)\\ &\quad -(b\partial_bA)(a\partial_aB). \end{aligned} \tag{40}$$

Expanding the six-term expressions gives two finite identities:

$$\begin{aligned} \{S,P\}&=-2T,\\ \{T,P\}&=SH. \end{aligned} \tag{41}$$

They can be checked by multiplying the displayed Laurent polynomials; the derivatives of $P$ are

$$a\partial_aP=a-a^{-1}+a/b-b/a,$$ $$b\partial_bP=b-b^{-1}-a/b+b/a.$$

The bracket has the product rule. Thus, for $R=-ST$, equations (39)–(41) give

$$\begin{aligned} \{R,P\} &=2T^2-S^2H\\ &=\sum_{g\in G}g(DC-M). \end{aligned} \tag{42}$$

For every integer $q\geq0$,

$$\operatorname{CT}\{R,P\}P^q=0. \tag{43}$$

To prove this combinatorially, write

$$R=\sum_e r_ea^{e_1}b^{e_2},$$

and regard $P$ as its nine labeled steps. A contribution to the constant coefficient in (43) consists of an exponent $e$, a word of $q+1$ steps $v_0,\ldots,v_q$ with sum $-e$, and its first position distinguished. Its signed multiplicity is

$$r_e\det(e,v_0).$$

Every possible distinguished position has the same total signed count, since permuting positions is a bijection of the unrestricted step words with given total displacement. Sum over all $q+1$ distinguished positions. For each fixed exponent and fixed word the total signed multiplicity is

$$\begin{aligned} &r_e\sum_{j=0}^q\det(e,v_j)\\ &\quad=r_e\det\!\left(e,\sum_{j=0}^qv_j\right)\\ &\quad=r_e\det(e,-e)=0. \end{aligned}$$

All multiplicities are integers: if desired, replace an integer weight by that many distinguishable copies of its sign and pair the positive and negative copies within each word. Since $q+1>0$, the original distinguished-first-position count is zero. The three labels on zero steps are retained; a marked zero contributes determinant zero, but its three choices at other positions remain distinct.

This is a finite cancellation. Equivalently, the formal identity

$$\begin{aligned} &(q+1)\operatorname{CT}\{R,P\}P^q\\ &\quad=\operatorname{CT}\{R,P^{q+1}\}=0 \end{aligned}$$

follows by logarithmic differentiation of Laurent polynomials. No limit, convergence assertion, or analytic integration is needed.

Every $g\in G$ preserves $P$ and constant coefficients. Multiplying (42) by $P^q$ and taking constant coefficients therefore gives

$$12\operatorname{CT}(DC-M)P^q=0. \tag{44}$$

Equations (23), (29), and (44) prove $a_{2n}=c_n$ for every $n\geq1$.

9. Boundary cases and conclusion

For $n=1$, the even source path is $HH$, which maps to the unique three-step forward excursion $f_1f_2f_3$. Its tableau pair consists of the empty tableau and the column of height three. In the constant-coefficient calculation, $q=0$ and both $\operatorname{CT}(DC)$ and $\operatorname{CT}(M)$ equal $1$, matching the singleton partition. The empty source word has $a_0=1$ and is covered by the prefix bijection; no negative-length walk is used.

The odd identity follows from a positive bijection through equal-shape tableau pairs. The even identity follows from a positive prefix-and-excursion correspondence and a finite signed-walk count. Together these prove both cardinality identities in Question 8.5. A direct positive bijection from the even source paths to colored partitions, or one preserving further statistics such as the number of up steps and the number of arcs, is not asserted.