I am trying to solve a combinatorics problem which I do not know how to generalize. Let's say we have two sets of $n$ elements. We label set 1 with odd numbers and set 2 with even numbers.
For example, for n=3
Set 1: $1\ 3\ 5$
Set 2: $2\ 4\ 6$
In general, there are $n!$ ways to pair set 1 with set 2. For example, in this case, 3!=6 ways: {1,2}{3,4}{5,6}, {1,2}{3,6}{5,4}, {1,4}{3,2}{5,6}, {1,4}{3,6}{5,2}, {1,6}{3,4}{5,2}, and {1,6}{3,2}{5,4}.
Up until here is fine. Now we consider that set 1 and 2 can be partitioned into two distinct sets such that I always split the set into ${\rm integer}(n/2)$ elements or less. Let's call them set L and set R.
${\rm L}\Big|\ {\rm R}$
$1\Big|\ 3\ 5$
$2\Big|\ 4\ 6$
Now the elements within set L $\textbf{cannot}$ be paired together, only with the set L-R, R-L and R-R. In the example before, the allowed pairing is only 4: {1,4}{2,3}{5,6}, {1,4}{2,5}{3,6}, {1,6}{2,3}{4,5}, and {1,6}{2,5}{3,4}. Another example, for n=4 which has two possible partitions L=1 and L=2:
${\rm L}\Big|\ {\rm R}$
$1\Big|\ 3\ 5\ 7$
$2\Big|\ 4\ 6\ 8$
Here there are 18 possible combinations: {1,4}{2,3}{5,6}{7,8}, {1,4}{2,3}{5,8}{7,6},{1,6}{2,3}{5,4}{7,8}, {1,6}{2,3}{5,4}{7,6}, etc.
${\rm L}\Big|\ {\rm R}$
$1\ 3\Big|\ 5\ 7$
$2\ 4\Big|\ 6\ 8$
Here there are 20 possible combinations {1,8}{2,3}{4,5}{7,6}, {1,8}{2,7}{3,6}{4,5}, etc.
I attach a pictorial graph to help grasp the idea:
I am now trying to generalize the number of possible pairings in the function of $n$ and the size of $L$. I asked a similar, but more trivial, question here:Bipartite graph: Average number of cuts for a given partition. And the answer should be somewhat similar, but I cannot find a way to solve it.
Any help would be appreciated.
Pairings with no $L$-to-$L$ pairs
Suppose that there are $2\ell$ elements in $L$ ($\ell$ on the top, $\ell$ on the bottom) and $2r$ elements in $R$ ($r$ on the top, $r$ on the bottom) with $\ell \le r$.
Then there are $r(r-1)(\cdots)(r-\ell+1) = \frac{r!}{(r-\ell)!}$ ways to pair the top-left elements with bottom-right elements. Independently, there are $\frac{r!}{(r-\ell)!}$ ways to pair the bottom-left elements with top-right elements. After that is done, there are $r-\ell$ elements left on each side of $R$, which can be matched in $(r-\ell)!$ ways, for an overall count of $$\frac{r!^2}{(r-\ell)!}$$ pairings.
Pairings with exactly $2k$ crossing pairs
Using the same notation as the above (but dropping the now-unnecessary assumption that $\ell \le r$) let's count the number of pairings with $2k$ crossing pairs: $2k$ pairs where one element is in $L$ and one element is in $R$. The number of these must be even, because the number of top-left-to-bottom-right pairs must be equal to the number of bottom-left-to-top-right pairs.
There are $\binom \ell k^2 \binom rk^2$ ways to pick which elements of $L$ and $R$ are going to be part of crossing pairs. From there, there are $k!$ ways to pick the top-left-to-bottom-right pairs, and $k!$ ways to pick the bottom-left-to-top-right pairs.
The remaining $2(\ell-k)$ elements of $L$ can be paired in $(\ell-k)!$ ways, and the remaining $2(r-k)$ elements of $R$ can be paired in $(r-k)!$ ways. Altogether, we get $$ \binom \ell k^2 \binom rk^2 k!^2 (\ell-k)! (r-k)! = \ell!\,r!\,\binom \ell k \binom rk $$ pairings.
The $k=\ell$ case gives us the formula in the previous section.
The $k=0$ case gives us the $\ell!\,r!$ pairings with no crossing pairs at all. Since there are $(\ell+r)!$ pairings total, we also know that $(\ell+r)! - \ell!\,r!$ gives us the number of pairings with at least one crossing pair.
The total number of crossings across all pairs
Another thing that seems useful is the total number of crossings added up over all pairings, where each of the $ \ell!\,r!\,\binom \ell k \binom rk$ pairings with $2k$ crossings contributes $2k$ to the count.
We can express this as a summation over all $k$ from $0$ to $\min\{r,\ell\}$, but there is an easier way. There are $2r\ell$ possible crossing pairs, and each one of them appears in $(r+\ell-1)!$ pairings (since the other $r-\ell-1$ elements on the top and bottom need to be paired somehow). Therefore, in total, there are $$2r\ell (r+\ell-1)!$$ crossings among all the pairings.