Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I have a combinatorics question. Say you have two sequences:
$$X_{1},X_{2},X_{3},\ldots,X_{N_{1}}$$
and
$$Y_{1},Y_{2},Y_{3},\ldots,Y_{N_{2}}$$
How can i pair up elements from the $X$'s with elements of the $Y$'s, such that if I pair up $Y_{1}$ with $X_{3}$, then I can only pair up $Y_{2}$ with $X_{n}$ such that $n$ is greater than the index of the $X$ paired up with the previous $Y$, in this case $n>3$.
One interpretation of this question is that the criterion is intended to apply to all the $Y_i$, not just $Y_1$ and $Y_2$. Such pairings $\alpha$, given as sets of ordered pairs $\{Y_i, X_{\alpha(i)}\}$, satisfy $j \gt i$ implies $X_{\alpha(j)} \gt X_{\alpha(i)}$. They are in one-to-one correspondence with the $N_2$-element subsets of $\{X_j\}$, because
Any such pairing determines such a subset $\{ X_{\alpha(i)},\ 1 \le i \le N_2\}$, and
Any such subset is determined by its sorted indexes $j_1 \lt j_2 \lt \ldots \lt j_{N_2}$ and they determine a valid pairing $\alpha(i) = j_i$.
There are $\binom{N_1}{N_2}$ such subsets. This number equals $\frac{N_1!}{N_2!(N_1-N_2)!}$ when $0 \le N_2 \le N_1$ and otherwise is zero.
If the criterion is meant to apply only to $Y_1$ and $Y_2$, then if $\alpha(1)=j$, we only need $\alpha(2)\gt j$. Like before, such partial assignments are in one-to-one correspondence with the two-element subsets of $\{X_i\}$. The remaining $N_2-2$ assignments start with $N_1-2$ choices and therefore can be made in $(N_1-2)(N_1-3)\cdots (N_1-N_2+1)$ ways. Assuming $N_1 \ge N_2 \ge 2$ we obtain
$$\frac{N_1(N_1-1)}{2!}(N_1-2)(N_1-3)\cdots (N_1-N_2+1) = \frac{(N_1)!}{2! (N_1-N_2)!}.$$
When $N_2=1$, obviously the answer is $N_1$.
