A mapping of two sequences with no overlaps and partial assignments

Question

I want to characterize a correspondence mapping of two sequences $\psi : A \rightarrow B$ for an article that I am writing.

I need help describing the function class. I think this is an injective, non-surjective, order isomorphism. Please correct me on this?

In the figure below I have visually described the constraints on $\psi$ adopting the representation language of the following article: https://www.mathsisfun.com/sets/injective-surjective-bijective.html

Constraints on the mapping, $\psi$. The gray arrows within each sequence indicate ordering within each sequence. This information is repeated in the text.

Constraints:

1. First and last elements of each sequence must correspond. Given that $A$ has length $n$, and $B$ has length $m$: It can be said that $A(1) \widehat{=} B(1)$ and $A(n) \widehat{=} B(m)$.

2. Every element in $A$ has at most one element in $B$. Not every element in $A$ can be assigned.

3. The elements of $B$ can have at most one assignment.

4. The assignments $A_i \rightarrow B_j$ cannot cross other assignments. That is if $A_i \widehat{=} B_j$ then $A_{i+1} \rightarrow B_k,\ \exists k > j$

Thank you.

Answer 1

If I understand correctly, you have two sequences: \begin{gather*} a_1, a_2, \dots, a_n \\ b_1, b_2,b_3,b_4,\dots,b_m \end{gather*} You want to associate to each value $a_j$ a corresponding value $b_{k(j)}$.

The use of $a_j$ and $b_j$ is tripping you up; IMHO it makes more sense to work on the level of indices. Instead of associating $a_j$ with $b_k$, associate $j$ with $k$. The difficulty here is that then one cannot distinguish an index $j$ for $a_j$ from the same index $j$ for $b_j$; I will use $a_j$ and $b_j$ when I risk such confusion, but just $j$ otherwise.

There is no standard notation for association, but I will use $\sim$, because it is the standard notation for graph adjacency. Pretty much any relation can be described by a graph; you cannot use functions to describe your sort of association because they must associate to every $a_j$ some $b_k$ (or associate to every $b_k$ some $a_j$).

Working with indices, you want to count a certain class of bipartite graphs on $\{1,2,\dots,n\}\to\{1,2,\dots,m\}$: those for which the arrows do not cross in the natural embedding into the plane, for which $a_1\sim b_1$ and $a_n\sim b_m$.

Each arrow is constrained by the one below and the one above it: that is, in the following diagram, the only "free parameters" are the lengths of the red jumps.

That is, fix $N$; we will have $N$ jumps, each of size $x_s$. You want to count solutions to $$\sum_{s=1}^N{x_s}=n-1; x_s\geq1\tag{*}$$ Say that there are $f_N(n)$ solutions to (*).

We have to choose jumps on the left and on the right, but there are the same number of jumps on each (because the number of jumps corresponds to the number of matchings, and each matching has a left and a right side). So there are $f_N(n)f_N(m)$-many jump orders; since $N$ was chosen arbitrarily, we want $$\sum_{N=0}^{\infty}{f_N(n)f_N(m)}$$ (Don't be scared by the infinite sum! Most terms are $0$.)

We can then count $f_N(n)$ using the famous "stars-and-bars" trick. Alternatively, if you want to enumerate these matchings, then the above is entirely constructive:

1. Iterate over $N$. For each $N$:
2. Iterate over all (well, some) numbers. For each number:
3. Convert that number to a binary sequence.
4. Split the binary sequence in the middle. Now you have two binary sequences.
5. Use stars-and-bars to convert each binary sequence to a solution to (*).
6. Take the cumulative sum of your solution to (*) to get an association.

I leave you to fill in the details, especially the bounds on steps (1-2).