Number of pairings in a set of n objects

cepheid

This isn't homework, just a combinatorics problem I came across. However, it is a textbook-style problem. So I'm compromising and posting in the math forums, but using the HH template. I asked a mentor and he said it was acceptable.

1. The problem statement, all variables and given/known data

I have a set of n objects, where ##n = 2m, m \in \mathbb{N}##. In other words, I have an even number of objects. How many different ways are there to match up each object in the set with another object from the set, to produce m pairs?

2. Relevant equations

Combination without repetition:$$_nC_2 = \left( \begin{array}{c}n\\2\end{array} \right) = \frac{n!}{(n-2)!\,2!}$$
3. The attempt at a solution

I guess n = 2 is the trivial case (one pair). I started with the simplest non-trivial case of n = 4 and solved it by brute force:

4 objects:$$\bigcirc~\bigcirc~\bigcirc~\bigcirc$$3 different pairings:$$\bigoplus~\bigoplus~\bigotimes~ \bigotimes$$ $$\bigoplus~\bigotimes~\bigotimes~\bigoplus$$ $$\bigoplus~\bigotimes~\bigoplus~\bigotimes$$where the plusses and crosses are paired together. Then I asked myself: how would I arrive at a result of 3 combinations by counting? I know that ##_4C_2 = 6##, but as soon as I choose one pair out of the four objects, the remaining pair of objects are together by default. So I guess I have to stick a factor of 1/2 in there$$N_\textrm{pairings} = \frac{1}{2}\left( \begin{array}{c}4\\2\end{array} \right) = 3$$What if I had 6 objects? I would pick my first pair, and there would be ##_6C_2 = 15## ways of doing that. Then 4 objects would remain, and it would reduce to a previously-solved problem of how many ways to choose pairs from the four remaining objects. So:$$N_\textrm{pairings} = \frac{1}{2}\left( \begin{array}{c}6\\2\end{array} \right)\left( \begin{array}{c}4\\2\end{array} \right) = 45$$If I had 8 objects, then I guess I would choose my first pair, and there would be 8 choose 2 ways of doing that. Then six objects would remain, and it would reduce to a previously-solved problem:$$N_\textrm{pairings} = \frac{1}{2}\left( \begin{array}{c}8\\2\end{array} \right)\left( \begin{array}{c}6\\2\end{array} \right)\left( \begin{array}{c}4\\2\end{array} \right) = 1260$$By looking at this sequence of products and thinking about it, I arrived at the general equation for arbitrary n:$$N_\textrm{pairings} = \frac{1}{2}\prod_{i=0}^{m-2}\left( \begin{array}{c}n-2i\\2\end{array} \right)$$However, I then noticed something which is that you can write the equation before last as:$$N_\textrm{pairings} = \frac{1}{2}\left( \begin{array}{c}8\\2\end{array} \right)\left( \begin{array}{c}6\\2\end{array} \right)\left( \begin{array}{c}4\\2\end{array} \right) = \frac{1}{2}\frac{8\cdot 7}{2!} \frac{6\cdot 5}{2!} \frac{4\cdot 3}{2!} = \frac{1}{2^m}\frac{8!}{2!} = \frac{8!}{2^{m+1}}~\textrm{(where m = 4 here)}$$which leads me to believe that the general formula is just $$N_\textrm{pairings} = \frac{n!}{2^{m+1}}$$Question 1: Am I doing this correctly? For n = 100, the case I was originally interested in, the number of pairings is approximately 4e142, which is ridiculously large! On the other hand, I have verified the n = 4 and n = 6 cases by brute force.

Question 2: That factor of 1/2 seems kind of ad hoc. I reasoned my way to it by looking at a specific case. Is there a general argument for why it should be there?

Question 3: Is there a line of reasoning that I can use to arrive at the last equation, in terms of n!, directly?

It's like my probability theory professor used to say: "counting is hard!"

I like Serena

Hi cepheid!

Trying to keep track in dealing with unordered stuff usually gives me a head ache.
What I have learned to do, is first count the ordered stuff, and then divide by the number of duplicate countings.

In your case you can order the objects in ##n!## ways, yielding ##m## ordered pairs.
However, since the pairs are supposed to be unordered, we are counting each pair twice.
So we need to divide by ##2^m##.
Furthermore, the m pairs can be ordered in m! ways, so we need to divide by ##m!## to eliminate the duplicate countings.

I believe the general formula is:
$$N_{pairings}={n! \over m! 2^m}$$
I didn't try to brute force count and verify though...


To illustrate with n=6, the first ordering is:
(1,2),(3,4),(5,6)
However, (2,1),(3,4),(5,6) is the same pairing which we would be counting separately.
We need to divide by 2 for each pair in the pairing.
That is, by 2³.

Furthermore, (3,4),(1,2),(5,6) is again the same pairing which we would also be counting separately.
We need to divide by 3! to compensate.

cepheid

Yeah, I see what I did wrong. You're right, I am over-counting due to the ordering of the pairs (not the ordering within the pairs, which is taken care of by my using n choose 2 instead of n permute 2). The problem first started with my stray factor of 1/2 in the n = 4 step. This wasn't a factor 1/2, it was a factor 1/m, because it was saying that if you four objects, 1 2 3 4, and you choose to pair 12, then the other pair is 34. However, if you choose to pair 34, then the other one is 12, and these are not distinct outcomes. This correction of 1/m needs to occur at every recursion step. For example, with n = 6, I had 6 choose 2, and I said, if the two initially chosen are 12, then you have

12 34 56
12 35 46
12 36 45

these being the three pairings of the remaining four that weren't initially chosen. The problem is, if you multiply these three sets by 6 choose 2, you're including, for example, the case where you choose 34 initially, which leads to

34 12 56

which is not distinct from one of the above sets. So it's clear that number of times a duplicate set will appear is just going to be equal to m, the number of pairs (3 in this case). That's because this set of pairs will appear again in the "56" series, when those are the two initially chosen). So, recasting my product, I end up with:$$ N_\textrm{pairings} = \prod_{i=2}^m \frac{1}{i}\left (\begin{array}{c}2i\\2\end{array}\right)$$And for m = 4 this is $$\frac{1}{2}\left (\begin{array}{c}4\\2\end{array}\right)\frac{1}{3}\left (\begin{array}{c}6\\2\end{array}\right)\frac{1}{4}\left (\begin{array}{c}8\\2\end{array}\right) = \frac{1}{4\cdot 3 \cdot 2}\frac{8 \cdot 7}{2}\frac{6\cdot 5}{2}\frac{4\cdot 3}{2} = \frac{1}{4!}\frac{1}{2^3}\frac{8!}{2!} $$ $$ = \frac{8!}{4! \cdot 2^4} $$ reproducing your formula. However, your method is WAY better. Mine is tricky and prone to error.

oli4

Hi cepheid and Serena's fan, I got to the same result you got but with yet a different way (closer to cepheid's way to make it through)
Here is how I went through it.
I have [itex]u_1[/itex]=1 (only one way to make a pair out of just one pair)
Then when adding a new pair to go to [itex]u_{n+1}[/itex], you have to chose one of the two items fixed, and use the other one to "play" with all the previous results.
So for instance for n=2 (4 items) you have 3 ways to play with the previous set of size 1
Then 5 ways to play with the previous set of 3, so [itex]u_n[/itex]=(2n-1)!! (double factorial, the product of odd numbers, 1x3x5x7x9x...x2n-1)
Well, I am calling n what you called m in fact but it is clear, so the formula is the same: [itex]u_n=(2n-1)!!=\frac{(2n)!}{2^n n!}[/itex]