Register to reply 
Number of pairings in a set of n objects 
Share this thread: 
#1
Feb213, 04:31 PM

Emeritus
Sci Advisor
PF Gold
P: 5,196

This isn't homework, just a combinatorics problem I came across. However, it is a textbookstyle 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!}{(n2)!\,2!}$$ 3. The attempt at a solution I guess n = 2 is the trivial case (one pair). I started with the simplest nontrivial 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 previouslysolved 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 previouslysolved 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}^{m2}\left( \begin{array}{c}n2i\\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!" 


#2
Feb213, 05:22 PM

HW Helper
P: 6,189

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^{3}. 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. 


#3
Feb213, 06:02 PM

Emeritus
Sci Advisor
PF Gold
P: 5,196

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. 


#4
Feb313, 07:46 AM

P: 218

Number of pairings in a set of n objects
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]=(2n1)!! (double factorial, the product of odd numbers, 1x3x5x7x9x...x2n1) Well, I am calling n what you called m in fact but it is clear, so the formula is the same: [itex]u_n=(2n1)!!=\frac{(2n)!}{2^n n!}[/itex] 


Register to reply 
Related Discussions  
Doubles pairings with five people  General Math  4  
Finding the number of objects in a microstate  Introductory Physics Homework  0  
Given 2n objects, number of ways to select n objects  Calculus & Beyond Homework  1  
Probability of Pairings in Chess Game  Calculus & Beyond Homework  3  
DNA Base Pairings  Biology  2 