Return to Answer

• Suppose $r \in R_0$ starts with a $\U$ (the other case is symmetrical). Locate all $\U$ transitions that reach each positive $y$ for the first time in $r$, and change them into $\D$'s.
• Suppose $l \in L_0$ stays below $y = 0$ (the other case is symmetrical). Let $-2h$ be the final $y$-coodinate of $P$. Find $\D$'s that reach $y= -1, \ldots, -h$ for the last time in $l$, and change them into $\U$'s.

• Suppose $r \in R_0$ starts with a $\U$ (the other case is symmetrical). Locate all $\U$ transitions that reach each positive $y$ for the first time in $r$, and change them into $\D$'s.
• Suppose $l \in L_0$ stays below $y = 0$ (the other case is symmetrical). Let $-2h$ be the final $y$-coodinate of $l$. Find $\D$'s that reach $y= -1, \ldots, -h$ for the last time in $l$, and change them into $\U$'s.

$\newcommand{U}{\uparrow}$ $\newcommand{D}{\downarrow}$ $\newcommand{F}{\nearrow}$ $\newcommand{G}{\searrow}$ $\newcommand{O}{\otimes}$

Fascinating question. Here goes an involved, but essentially bijective, argument.

Note that $g$ allows to establish more product representations for sizes of similarly defined $W_{p_1, \ldots, p_k}$ visiting many prescribed points on $y = 0$, but matching LHS sum have to look differently.

$\newcommand{U}{\uparrow} \newcommand{D}{\downarrow} \newcommand{F}{\nearrow} \newcommand{G}{\searrow} \newcommand{O}{\otimes}$Fascinating question. Here goes an involved, but essentially bijective, argument.

Note that $g$ allows to establish more product representations for sizes of similarly defined $W_{p_1, \ldots, p_k}$ visiting many prescribed points on $y = 0$, but matching LHS sums have to look differently.

On the other hand, consider the following recursive algorithm $g$:

• The encoding $x$ looks like $w_0 \O w_1 \O \ldots \O w_p$, where all $w_p$ are $\U\D$-walks of even length. $w_p$ is simply the tail of $w$ after visiting $(p, 0)$. Every other $w_i$ is built as an $R_0$ tail of some $w'$, followed by some $f_0(a) \in L_0$, therefore the split is unique (recall bijective proof of $(\clubsuit)$).
• $h$, as a "signed" balanced bracket sequence, encodes the recursion tree of $g$, as well as which chunks of the input were flipped.

• $x$ consists of $p + q$ $\O$'s, and $2n$ $\U\D$'s, grouped in even-length blocks. Thus there are $4^n {n + p + q \choose n}$ possible $x$'s (choose the sequence of $\U\D$'s, and interleave the $\O$'s with consecutive $\U\D$ pairs).
• $h$ is an $\F\D$-walk of length $2p$ visiting $(p, 0)$ and finishing at $(p + q, 0)$. There are ${2p \choose p}{2q \choose q}$ of them.

In general, consider the following recursive algorithm $g$:

• The encoding $x$ looks like $w_0 \O w_1 \O \ldots \O w_p$, where all $w_i$ are $\U\D$-walks of even length. $w_p$ is simply the tail of $w$ after visiting $(p, 0)$. Every other $w_i$ is built as an $R_0$ tail of some $w'$, followed by some $f_0(a) \in L_0$, therefore the split is unique (recall bijective proof of $(\clubsuit)$).
• $h$, as a "signed" balanced bracket sequence, encodes the recursion tree of $g$, as well as which chunks of the input were flipped.

• $x$ consists of $(p + q)$ $\O$'s, and $(2n)$ $\U\D$'s, grouped in even-length blocks. Thus there are $4^n {n + p + q \choose n}$ possible $x$'s (choose the sequence of $\U\D$'s, and interleave the $\O$'s with consecutive $\U\D$ pairs).
• $h$ is an $\F\D$-walk of length $2(p + q)$ visiting $(p, 0)$ and finishing at $(p + q, 0)$. There are ${2p \choose p}{2q \choose q}$ of them.