3
$\begingroup$

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$.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

  1. Any such pairing determines such a subset $\{ X_{\alpha(i)},\ 1 \le i \le N_2\}$, and

  2. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.