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. :tongue2:

Homework Statement

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?

Homework Equations

Combination without repetition:$$_nC_2 = \left( \begin{array}{c}n\\2\end{array} \right) = \frac{n!}{(n-2)!\,2!}$$

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]

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.

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 $u_1$=1 (only one way to make a pair out of just one pair)
Then when adding a new pair to go to $u_{n+1}$, 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 $u_n$=(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: $u_n=(2n-1)!=\frac{(2n)!}{2^n n!}$

 

[blue_raver22]

First of all, great job on your reasoning and coming up with a solution for this problem! Your approach is correct and your final equation is also correct.

To answer your first question, yes, you are doing this correctly. Your reasoning and calculations for the n = 4 and n = 6 cases are correct, and your general formula also holds true. As you mentioned, for larger values of n, the number of pairings becomes extremely large, which makes sense given the factorial in the denominator of your formula.

For your second question, the factor of 1/2 is not ad hoc, but rather a consequence of the definition of combinations. When we write $_nC_r$, we are essentially asking how many ways we can choose r objects from a set of n objects without replacement and without regard to order. This means that once we choose a pair of objects, we do not need to consider them again when choosing the remaining pairs. In other words, we are only interested in unique combinations, which is why we divide by 2 for each pair that we choose. This is also why your final equation includes the factor of 1/2.

For your third question, you can arrive at the final equation in terms of n! by considering the fact that for each pair that we choose, we are essentially dividing the total number of combinations by 2. In other words, we are essentially dividing the total number of combinations by 2^m, where m is the number of pairs. Therefore, we can write the final equation as $N_\textrm{pairings} = \frac{n!}{2^m}$, where m is the number of pairs and n is the total number of objects.

In summary, your approach and reasoning are correct, and your final equation is also correct. The factor of 1/2 is not ad hoc, but a consequence of the definition of combinations, and the final equation can be derived by considering the fact that we are essentially dividing the total number of combinations by 2 for each pair that we choose. Great job on solving this combinatorics problem!