Path systems between two families of lattice points, and non-intersecting systems

Fix a natural number $r$, start points $(A_i{)}_{i<r}$ and end points $(E_i{)}_{i<r}$ in ${\mathbb{Z}}^2$.

For a permutation $\pi \in S_r$ (The finite symmetric group $S_n$, one-line notation, and cycle notation), a $\pi$-system is an $r$-tuple

$\mathbf{P}=(P_i{)}_{i<r}$

such that for each index $i<r$, the path $P_i$ is a monotone lattice path from $A_i$ to $E_{\pi (i)}$ (Monotone lattice paths with steps $E=(1,0)$ and $N=(0,1)$).

Two monotone lattice paths intersect when they share a lattice point, that is, when the images of their point functions have a common element of ${\mathbb{Z}}^2$. A $\pi$-system is non-intersecting when no two of its paths intersect.

Write ${\mathcal{S}}_{\pi }(A,E)$ for the set of $\pi$-systems and ${\mathcal{N}}_{\pi }(A,E)\subseteq {\mathcal{S}}_{\pi }(A,E)$ for the non-intersecting ones.

Each set ${\mathcal{S}}_{\pi }(A,E)$ is finite. Indeed, for every index $i<r$, either the endpoints $A_i$ and $E_{\pi (i)}$ are compatible and $\mid \mathcal{M}((0,0),(m,n))\mid =\left(\genfrac{}{}{0px}{}{m+n}{n}\right)$ counts a finite set of monotone paths between them, or they are incompatible and Monotone lattice paths with steps $E=(1,0)$ and $N=(0,1)$ makes that set empty. Repeated use of The product rule: $\mid A\times B\mid =\mid A\mid \mid B\mid$, and $\mid {\prod }_{i<m}{A}_i\mid ={\prod }_{i<m}\mid A_i\mid$ therefore makes the product of those finite sets finite, and that product is exactly ${\mathcal{S}}_{\pi }(A,E)$. Therefore the subset ${\mathcal{N}}_{\pi }(A,E)$ is finite as well (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$).

• The definition uses all lattice points of the paths, not only their step words. Two paths that merely cross between lattice points are not visible in this model; everything below is about sharing a lattice vertex.

• The permutation is part of the datum. A path system records not only which paths occur but also which start is matched to which end.