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!

  • 1
    $\begingroup$ Just saying, this is highly unrelated to the set-theoretic study of cardinals and thus is a misleading use of the tag - apologies if this sounds strict. $\endgroup$ – Isky Mathews Apr 27 '18 at 6:58

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.

  • $\begingroup$ Hi, thank you for the fast answer! I do not understand how you found the first formula though, should it not be n!.m. / |m-n|! instead? $\endgroup$ – user148691 Apr 27 '18 at 6:18
  • $\begingroup$ No. I will explain the the formula $(1)$, since $(2)$ is basically the same. Since $n \geq m$, we cannot use more than $m$ elements of $X$ - this is because we are pairing the elements of $X$ and $Y$. In particular, in $n \cdot(n-1) \cdots (n-m+1)$ you have $m$ elements. So imagine you line them up as follows: $n\cdot$ _ $\cdot (n-1)$_$\cdots (n-m+1)$_. We are just fixing the spaces where elements of $X$ can be and finding all the permutations.Notice also that the spaces in between are the places where the elements of $Y$ will be put. And you can arrange the elements of $Y$ in $m!$ ways. $\endgroup$ – Thomas Bladt Apr 27 '18 at 6:26
  • $\begingroup$ Yes I am sorry, I meant n!.m!. / |n-m|!, which is the same :) Could you explain in a similar fashion your answer for (a)? I do not understand how you find the formula... $\endgroup$ – user148691 Apr 28 '18 at 1:45

Your Answer

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