0
$\begingroup$

I have a combination problem that I can't get my head around. Similar problems were found here and here but are not quite the same of my problem.

I have two sets of units and I want to find the number of possible matches between the two. So for every unit in set1, I pick a matched unit is set2 until there is no more units to pick in set1. This become one possible draw. I want to find the number of possible draws that exist within two sets of size $m$ and $n$.

The two sets are of different length, however the first set is always smaller or equal to the second one. Here are the problem description:

  • set1: size $m$
  • set2: size $n$
  • $m <= n$
  • The order do not matter
  • The draws are done without replacement
  • You keep drawing until set1 is empty, some items in set2 may not have been picked in one event.

I'll try to make it clearer with an example. Let's say my set1 is of length 2 and contains unit id: $\{A,B\}$. On the other side, my set2 is of size 3 and contains units $\{1,2,3\}$. There are 6 different outcomes possible $[\{A1,B2\},\{A1,B3\},\{A2,B1\},\{A2,B3\},\{A3,B1\},\{A3,B2\}]$. I need a general solution to calculate the number of outcome possible for any sets of size $\{m,n\}$.

Like stated before, $\{A1,B2\}$ is equivalent to $\{B2,A1\}$ so it doesn't count as a different output.

I manually counted the number of outcomes for a bunch of examples with the hope of finding the pattern but I didn't succeed. Here are the results of my manual calculations (hopefully I didn't miss any).

----------------------------
|  m   |   n   | outcomes  |
----------------------------
|  2   |   3   |     6     |
|  3   |   3   |     6     |
|  2   |   4   |     12    |
|  3   |   4   |     24    |
|  4   |   4   |     24    |
|  2   |   5   |     20    |
----------------------------

In this question, the problem is similar but they were asking for a Python script to list all possible outcomes. In my case, I don't really need to list all the outcomes, I just need to know how many there are. That why I'm mostly asking of the proper equation to represent my problem. However, if such equation does not exist, having a similar script in R would be acceptable.

*** Edits: To try to clarify. My actual problem is that I have a multiple small tables where each lines represent an individual (so $m$ individuals in my set1). All those small tables are inside their "group" (my set2) which is a spatial localisation of population $n$. I want to identify the likelihood of matching perfectly each individual in a table to its associated person in the group. To do that, I just need to identify all the possible matches between the rows in my table and the people in the group.

$\endgroup$
  • $\begingroup$ How, exactly, are you drawing units from two different bags and what exactly is a "match"?? $\endgroup$ – whuber May 25 at 13:39
  • $\begingroup$ @whuber, I added some edits, however I honestly find it hard to improve my question. It may be the language barrier (english isn't my first language), but when I first wrote my question I tried to simplify my problem as much as possible, maybe I however simplified it. $\endgroup$ – Bastien May 25 at 14:03
  • $\begingroup$ @whuber, My draw is that for every unit in set1, I draw a unit in set2 until there is no more units in set1. A match is the the unit in set1 paired with the unit is set2 at that time (for example A1 or B2) $\endgroup$ – Bastien May 25 at 14:05
  • $\begingroup$ It looks like your "match" is an ordered pair. That interpretation agrees with your table of counts, for which the formula is $(n)_m = n(n-1)\cdots(n-m+1).$ $\endgroup$ – whuber May 25 at 15:21
  • $\begingroup$ great! It's what I needed. To be sure I understand well, $(n)_m = (5)_4 = 5*(5-1)*(5-2)*(5-4+1) = 120$ possible cases. You can transform your comment as an answer, I'll accept it. Thanks. $\endgroup$ – Bastien May 25 at 16:55

Your Answer

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

Browse other questions tagged or ask your own question.