- #1

cepheid

Staff Emeritus

Science Advisor

Gold Member

- 5,196

- 38

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:

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?

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

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}}$$

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

## 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!"

Last edited: