Unique pairings with repeated elements

111 Views Asked by At

I am looking for a generalization of the formula for the number of unique pairs of a list of elements to the case where there are multiple copies of each element.

First a review of the standard formula: If we have $2r$ distinct elements (i.e., $X_1, \ldots,X_r,X_{r+1}, \ldots, X_{2r}$), then the number of ways to create unique pairings of elements is $$ (2r-1)!! = \frac{(2r)!}{2^r r!},$$ where we define a pairing as an arrangement where all the elements are placed into pairs. (The order within a pair and the order of all the pairs in a pairing are not important)

Here is the new situation: Let's say we have $2r$ types of elements denoted $X_1, \ldots,X_r,X_{r+1}, \ldots, X_{2r}$. These elements exist in multiple copies such that we have $n_k$ copies of $X_k$ and $n_k$ copies of $X_{r+k}$ for each $k = 1, \ldots, r$. Namely, we have $n_1$ copies of both $X_1$ and $X_{r+1}$ and so on. (We create the same number of copies for both $X_1$ and $X_{r+1}$ to ensure there are an even number of total elements)

What is the number of unique pairing we can form in this system?

Example: Let's say $r = 1$. Then we have two types of elements $X_1$ and $X_2$. We also take $n_1 = 2$ giving us the elements $X_1$ and $X_2$ in copies of $2$ each. Consequently, the unique pairings are $(X_1, X_2), (X_1, X_2)$ and $(X_1, X_1), (X_2, X_2)$ and the above formula (assuming we can find it) should reduce to 2.

Motivation: With an answer to the above question it should be possible to find the number of deranged matchings (https://oeis.org/A053871) where there are multiple components of each element.