Number of possible ways to pair elements from two datasets

Question

I have a problem counting all the possible ways of "pairing" two datasets of size n and m, including partial pairing.

Example: Assume we have two sets $\{A,B\}$ and $\{1,2,3\}$. My aim is to find all ways of pairing letters with numbers, including the consideration of situations, where only a fraction of possible pairs is actually present, including a case of "no pairing at all".

In this case I would get the following ways of pairing:
$\{A,1\},\{B,2\},\{3\}$ (two pairs out of two concurrent pairs possible)
$\{A,2\},\{B,1\},\{3\}$ (two pairs out of two concurrent pairs possible)
$\{A,1\},\{B,3\},\{2\}$ (two pairs out of two concurrent pairs possible)
$\{A,3\},\{B,1\},\{2\}$ (two pairs out of two concurrent pairs possible)
$\{A,2\},\{B,3\},\{1\}$ (two pairs out of two concurrent pairs possible)
$\{A,3\},\{B,1\},\{1\}$ (two pairs out of two concurrent pairs possible)
$\{A,1\},\{B\},\{2\},\{3\}$ (one pair out of two coexisting pairs possible)
$\{A,2\},\{B\},\{1\},\{3\}$ (one pair out of two coexisting pairs possible)
$\{A,3\},\{B\},\{1\},\{2\}$ (one pair out of two coexisting pairs possible)
$\{A\},\{B,1\},\{2\},\{3\}$ (one pair out of two coexisting pairs possible)
$\{A\},\{B,2\},\{1\},\{3\}$ (one pair out of two coexisting pairs possible)
$\{A\},\{B,3\},\{1\},\{2\}$ (one pair out of two coexisting pairs possible)
$\{A\},\{B\},\{1\},\{2\},\{3\}$ (zero pairs out of two coexisting pairs possible)

How can I generalize it to bigger sets of size n and m?

Answer 1

Assume your sets are $A,B$ with $|A|\le |B|$ and $A\cap B = \emptyset$. Then you are looking for the sum of the ways for each $X\subset A$, the number of injections $f:X\hookrightarrow B$. This is counted by $X$-permutations of $B$.

So, the number of ways is given by:

$$\sum_{X \in P(A)} (|B|)_{|X|}$$

where $(|B|)_{|X|}$ is the Descending factorial.

Answer 2

Assume our two sets are $A$ and $B$ where $A\cap B = \emptyset$ Break into cases based on the number of pairs used. With $k$ pairs used, choose which $k$ elements are involved in the pairs from the first set and which $k$ from the second set.

Then, choose how the selected elements are paired together.

This gives a total of:

$$\sum\limits_{k=0}^{\min(|A|,|B|)}\binom{|A|}{k}\binom{|B|}{k}k!$$

Answer 3

there is a solution involving the exponential generating function.

The description using combinatorial species is $E(X)\cdot E(XY) \cdot E(Y)$ where:

X is the sort of letters

Y is the sort of digits

and the formula means that there is a set of unpaired letter, than a set of pairs, then a set of unpaired digits.

The exponential generating function is

$$exp(x).exp(xy).exp(y)$$

By reading the coefficient of $$\frac {x^n}{n!} \frac {y^m}{m!}$$ one gets the solution.

For $n=2$ and $m=3$ the exponential series contains the term

$$13 \frac {x^2}{2!} \frac {y^3}{3!}$$

so there are $13$ pairings.