Number of pairs combinations

Question

I want to determine the number of pairs combinations that can be made between two sets of different sizes.

We have two lists of objects, $X= \{x_1, \dots, x_n\}$ and $Y = \{y_1, \dots, y_m\}$, and we want to match every $x$ with an $y$. $n$ and $m$ can be different. Every $x$ and $y$ can be used once, and ordering matters (so $x_1-y_1 x_2-y_2$ is not the same as $x_2-y_2 x_1-y_1$).

Every solution has hence a fixed size of $\min(m, n)$.

For instance, for $X = \{x_1, x_2\}$ and $Y = \{y_1, y_2\}$, we have the following solutions :

$x_1-y_1 x_2-y_2$

$x_1-y_2 x_2-y_1$

$x_2-y_1 x_1-y_2$

$x_2-y_2 x_1-y_1$

So we have $n(n-1)\dots(n - \min(n, m))m(m-1)\dots \min(n,m)$ different combinations possible.

I now would like to find the number of combinations with new properties on the set $X$.

1. Let us say that some elements in $X$ can be present more than once, eg. $X = \{x_1, x_2, x_1\}$. The previous formula cannot be applied since some combinations would be counted more than once. How can we take this into account?

2. An even weirder property (a special case of 1.): let us say that some elements in X can be present twice (only twice), but these two iterations must be used in a row in a combination. eg. if $x_1$ is such a element, $x_1-y_1 x_1-y_2 x_2-y_3$ is a solution, but $x_1-y_1 x_2-y_2 x_1-y_3$ isn't.

I hope I was clear enough. I do not know if there is an easy way to find a generic formula or not. Any tip/help is appreciated, thank you!

Answer 1

If $|X| = n \geq m = |Y|$ then the total solutions are given by $$n \cdot (n-1) \cdots (n-m+1)\cdot m! \tag{1}$$ if$|X| = n \leq m = |Y|$ then the total solutions are given by $$m \cdot(m-1) \cdots(m-n+1)\cdot n!\tag{2}$$ Now, for $(a)$ you just have to consider the repeated elements and divide what you get in the formulas $(1)$ or $(2)$ by the factorial of the number of times an element is repeated, for each number.

Let me show an example: consider that $X= \{x_1,x_2,x_2,x_3,x_3 \}$ and $Y=\{y_1,y_2,y_3 \}.$ Then you would use $(1)$, and consider the repeating elements. So the answer would be $$\dfrac{5 \cdot4\cdot3 \cdot (3\cdot2 \cdot1)}{2!2!}=90$$ ways to form the $(x,y)$ permutations you desire. We divide by $2! 2!$since the elements $x_2$ and $x_3$ appear twice, so you have to do this to avoid overcounting.