View Question
Q: maths ( Answered ,   1 Comment )
 Question
 Subject: maths Category: Science > Math Asked by: nivis-ga List Price: \$2.00 Posted: 05 Sep 2003 21:57 PDT Expires: 05 Oct 2003 21:57 PDT Question ID: 252803
 ```suppose there are 2n items. How many ways are there that the 2n items could be paired up. Ex> if the item are (a,b,c,d) (ab,cd) is one pair (ac,bd) is another pair Note (a,b,c,d) is the same as (ba,cd)```
 ```Hi, nivis-ga: The short answer is (2n-1)!! Okay, that answer is probably too short! My double exclamation marks aren't for enthusiasm, they are a mathematical shorthand for: (2n-1)*(2n-3)*...*1 That is, 2n-1 will always be an odd number (at least 1, given n >= 1), and if we write a product of the factors beginning with (2n-1) and declining by 2 until we drop down to a final factor of 1, then we get what is called the "double factorial": [Double Factorial -- from MathWorld] http://mathworld.wolfram.com/DoubleFactorial.html We only need the definition for odd positive integers, but as you'll see from the link above, the definition can be sensibly extended to all integers (and even beyond that, using the gamma function). Let's do a couple of quick examples and then prove the answer "by induction". First, the easy example. If we have a set of two items, {a,b}, then we can only "partition" this set into unordered pairs in one way, {{a,b}}. Second, let's revisit your original example with four items. You've already identified two ways of partitioning the set {a,b,c,d} into unordered pairs: {{a,b},{c,d}} {{a,c},{b,d}} Noting that in these cases a was paired with b and c, but not d, we find the third possibility: {{a,d},{b,c}} This agrees with the formula (4-1)!! = 3*1 = 3 ways. For the induction proof, let F(n) be the number of ways that a set of 2n items can be partitioned into unordered pairs. We've already discussed the basis step, in that for n=1 we have only 1 such partition, so F(1) = 1!!. Now the interesting part. We will assume the truth of F(n) = (2n-1)!! and proceed to extend our knowledge to the value of F(n+1). Given a set of 2(n+1) items, let's pick out one item and call it a. That is, our set consists of {a} U S where S contains the remaining 2n+1 items. Now we can (and must) pair a with any one of the 2n+1 items in S. After this choice is made, then the remaining set S' (consisting of S with the item paired to a removed) contains 2n items and thus can be partitioned in F(n) ways. Thus F(n+1) = (2n+1)*F(n) = (2n+1)*(2n-1)!! = (2n+1)!! So that completes the induction proof. Please alert me to anything in my answer that requires clarification; you should find a button to Request Clarification on this Web page for that purpose. regards, mathtalk-ga``` Clarification of Answer by mathtalk-ga on 06 Sep 2003 10:11 PDT ```Hi, nivis-ga: One other point. With a bit of algebra we can express the answer in terms of the regular factorial function and avoid "double factorials". The idea is that if we start with (2n)! and divide away the "even" factors in this product, what's left are precisely those odd factors that we wanted: F(n) = (2n-1)!! = (2n)!/[ (2n)*(2n-2)*...*2 ] = (2n)!/[ 2^n * n! ] regards, mathtalk-ga``` Request for Answer Clarification by nivis-ga on 06 Sep 2003 22:41 PDT ```Hi, According to your clarification , it would be 2n!/2^n * n!, this would work for our even number , can u explain me the new simple formula that u send me last , how can we derive that with avoiding doulble factorial.I need to know how can we subtitue 2n into simple combination and permutation formula and get the final 2n!/2^n * n! Please reply me nidhdo``` Request for Answer Clarification by nivis-ga on 07 Sep 2003 00:14 PDT ```Hi Mathtalk, Just give me a simple proof that how can we subtitute 2n is our original formula for permutation and combition and get the simple answer with avoiding double factorial. Thank u Nidho``` Clarification of Answer by mathtalk-ga on 07 Sep 2003 13:33 PDT ```Hi, nivis-ga: I'm not quite clear what additional information you would like at this point. Let me first explain/prove the equality of the two formulations that I gave. Then let me make some suggestions, if this would help, about how one evaluates the second formula, e.g. with a calculator or a computer program. EQUALITY OF THE TWO FORMULAS ============================ In your original question you ask how many ways 2n items could be separated out into (unordered) pairs. Obviously it is critical that the number of items will be even. An odd number of items cannot be separated out into pairs at all, because there would always be an "odd" item left over. I presented two equal expressions for this number: (2n-1)!! = (2n)!/[ (2^n) * n! ] If you check the algebra above you will see that the equality of these expressions is simply a matter of "cancellation" between common factors of the numerator and denominator of the right hand side. Every "even" factor 2k that appears in numerator (2n)! corresponds to the pair of factors 2 * k from the denominator 2^n * n!. After all those common factors are removed (there are n of these, as k varies from 1 to n), one is left with only the odd factors in the numerator, i.e. with (2n-1)!! WAYS TO EVALUATE THE SECOND FORMULA =================================== Perhaps your request for clarification is about evaluating the resulting expression: (2n)! / [ (2^n) * n! ] The factorial and exponential functions required to evaluate this expression are commonly found on a "scientific" calculator or provided as "built-in" functions in many programming languages. One concern can be the large size of values return by these functions. Already for 20 items (n=10 pairs), we would need: 20! = 2432902008176640000 2^10 = 1024 10! = 3628800 Thus F(10), as we denoted it above, would be: 20!/[ (2^10) * 10! ] = 654729075 I was able to perform these operations on my Windows calculator applet in "scientific" view with no difficulty. However the numbers are big ones, and this could pose a difficulty in computing them. Since the final answer is itself a big number, the difficulty of working with big numbers in some form can only be avoid up to a point. Your request for clarification seems to mention permutations and combinations, so perhaps in your particular circumstances you have functions already written or available to evaluate these (but not the double factorial, for example). One might take advantage of those "building blocks" in this way: F(n) = (2n)! / [ (2^n) * n! ] = (2n-1)! / [ (2^(n-1) * (n-1)! ] = [ (2n-1)! / (n!(n-1)!) ] * n! / [ 2^(n-1) ] = C(2n-1,n-1) * n! / [ 2^(n-1) ] = C(2n-1,n-1) * ( n! / [ 2^(n-2) ] ) / 2 Here C(m,n) denotes the familiar "combinations of m things taken n at a time" function. Also, recall that n! is the number of "permutations of n things". In this form, for n > 1, all the operations can be carried out in integer arithmetic while keeping the size of any intermediate results within a factor of 2 of the final answer. In other words this slightly more complicated way of evaluating the expression keeps the size of numbers that we have to work with down to a minimum. FURTHER CLARIFICATION? ====================== Please let me know whether I've cleared things up yet; if not I'll be happy to try again with a little more direction from you about what needs to be clarified. regards, mathtalk-ga``` Clarification of Answer by mathtalk-ga on 07 Sep 2003 14:58 PDT ```Hi, nivis-ga: Here's another "proof" approach that may be of interest to you. While our formula obviously is not strictly speaking a permutation or combination, we can relate the formula to the sort of computation used to deal with permutations (or distinct arrangements) involving "duplicate" items. To jog your memory, perhaps you've seen a problem like this. How many distinct arrangements of the letters in "misspelled" are there? Although there are 10 letters in "misspelled", many of them are "the same", so we actually have fewer than 10! distinct arrangments. Indeed because we have two s's, two e's, and two l's, the real answer is: 10!/( 2! 2! 2! ) because in any "arrangement" of the ten letters, one can "switch" the pairs of s's, e's, or l's without changing the appearance. We can take a similar approach to counting the "partitions into pairs" problem. Consider the following rule: Choose an arrangement of all 2n items, then form n pairs by taking the 1st and 2nd items as the first pair, the 3rd and 4th items as the second pair, and so on until all items are paired off. Now there are (2n)! ways to arrange 2n items, but in many cases the same pairings will be created by different arrangements. For example, we could swap the 1st and 2nd items with one another, and then we'd still have them as the same first pair. In fact, any of the n pairs can be switched, which accounts for a factor of 2^n in overcounting of these partitions. On the other hand, one can also envision switching the 1st and 2nd items together as a block with the 3rd and 4th items, or with any of the other n pairs. The rearrangements of the n "pair" blocks accounts for another n! factor of overcounting. Combining these two sorts of duplications, we can see that the actual number of ways to partition 2n items into pairs is: (2n)! /[ (2^n) * n! ] Here the denominator divides out for overcounting by swapping within a pair (the 2^n factor) and by permuting the n "pair" blocks (the n! factor). regards, mathtalk-ga``` Request for Answer Clarification by nivis-ga on 07 Sep 2003 17:35 PDT ```Hi Mathtalk, Thank you for your clarification, clear me one thing that this problem can not be solved by directly subtituing for as standard in combination and permutation formulas.And other thing is that what is 2n !,2^n,n! , how we have set up the formula that 2n!/2^n * n!. so that what is the meaning of 2n!, 2^n, n! Reply me THank You nidhdo``` Clarification of Answer by mathtalk-ga on 07 Sep 2003 18:38 PDT ```Hi, nivis-ga: You are the ultimate expert on what your problem means, but I can at least clarify the meaning of the notation used in my answer. Let's return to your original example to make sure, as far as possible, that the problem has been correctly understood. You asked in how many ways "2n items could be paired up". You then described two ways of pairing up the four items {a,b,c,d}. I believe you intended for the illustration to read: " (ab,cd) is one pair (ac,bd) is another pair Note (ab,cd) is the same as (ba,cd)." One issue to raise is whether you would consider (ab,cd) the same as (cd,ab). I assumed that, just as no pair has any preferred "order" as demonstrated in your example, e.g. ab is the same as ba, also the ordering of the pairs makes no difference, e.g. (ab,cd) is the same as (cd,ab). As with many combinatorial exercises, the answer can be derived in many different ways. But for a fixed interpretation of what is to be counted, all the answers should agree in their values whatever number of pairs is specified. Here the notations (2n)! and n! are factorials. The factorial of a positive integer n is a simple product of all the positive integers from 1 to n: n! = 1 * 2 * . . . * (n-1) * n = n * (n-1) * . . . * 2 * 1 The order of these factors doesn't matter because multiplication is commutative. Now (2n)! is defined similarly: (2n)! = (2n) * (2n-1) * . . . * 2 * 1 as would the factorial of any positive integer. [Note: By convention, 0! or zero factorial is 1, although we don't rely on this curiousity to solve this problem.] The factorial function is the answer to how many permutations there are of some distinct items. That is, if you have n distinct items, these can be arranged in a sequential order in n! distinct ways. There are n choices for the first item, followed by n-1 choices for the second item, and so on down the line until we reach the final position, at which point there is but one choice remaining to complete the list. The formula for combinations, as we have already alluded before, can also be stated in terms of the factorial function. Here is the expression for the number of combinations of m things taken n at a time: C(m,n) = m! / [ n! * (m-n)! ] whenever n is less than or equal to n (recall 0! = 1). Your answer can be given like this: (2n)! / [ 2^n * n! ] or in other algebraically equivalent ways (two alternative ways have been described in detail above, the double factorial being the most compact form). What this means is to divide the numerator, the factorial of 2n, by the denominator, which here is a product of 2 raised to the n'th power (2 times 2 times 2, and so on, for n factors of 2) times the factorial of n: (2n)! := "factorial of 2n" 2^n := "2 to the n'th power" n! := "factorial of n" As previously mentioned you will typically find these functions on a scientific calculator, but not on a "basic" or "four function" calculator. However there meanings should be familiar to you from the theory of permutations and combinations, which can scarcely be presented without relying upon them. In a narrow sense the answer (2n)! / [ (2^n) * n! ] is neither a permutation nor a combination formula. However in my previous comments I tried to point out some ways of understanding it in terms of those building blocks. In this connection, you should perhaps re-read my last note, in which I discuss a "proof" of the formula: (2n)! / [ (2^n) * n! ] in terms of distinct arrangements of items with some duplicates. As I mentioned above, it is virtually characteristic of these kinds of problems that they have many approaches that lead always to the same solution. Let's do one more, to see how the answer might be understood from a "pick, pick, pick" approach. Suppose the set of 2n items has some fixed order, with item "a" being first in this order. How many ways can item "a" be paired with another item? As it can be paired with any item except itself, we see that there are: 2n-1 choices for the pairing of a with another item. Once this choice is made, there are 2n-2 items left to pair up. Identify the "lowest" item of those remaining (just as we began with item a initially), and let's ask ourselves how many ways _that_ item can be paired with another of the remaining items. We see that there are: (2n-2)-1 = 2n-3 choices for this next pairing (of the lowest item remaining with one other, since an item again cannot be paired with itself). Continuing in this manner we can count the entire set of possible pairings by multiplying the numbers of choices available at each stage, until finally only one remaining pair is allowed: (2n-1) * (2n-3) * . . . * 1 Such an expression, while neither a permuatation nor a combination, is of sufficiently frequent interest to have earned its own mathematical notation, the "double factorial" (2n-1)!! as first described above. regards, mathtalk-ga``` Request for Answer Clarification by nivis-ga on 07 Sep 2003 22:07 PDT ```Hi Mathtalk, I know what is factorial(i know how to simplyfy factorial), i know what is 2^n , I know what is n!. I came to know one thing that 2n! is the permutation of 2n item . then i want to know why we divide 2^n and n! to get my answer that in how many ways 2n items paired up? Please reply me last time, Thank U Nidho``` Clarification of Answer by mathtalk-ga on 07 Sep 2003 23:44 PDT ```Hi, Nidho: Sometimes working through an example is the best way to understand "why" an answer is the way it is. Let's extend your original example with 4 items to one involving 6 items, say: {A,B,C,D,E,F} How many ways are there to partition this set into pairs? Since there are 6 items, there are 6! = 720 different permutations of these items. I won't list them all, but here are a few: ABCDEF DCBAFE ABEFCD Now suppose we took one of these permutations (arrangements) of all six items and converted it into a list of pairs, as outlined earlier in one of our proofs. That is, take the first two items and make a pair of them. Take the next two items and make a pair of them. Finally we are left with the third and final two items to form a pair. Here's what we get for each of these sequences: { {A,B}, {C,D}, {E,F} } { {D,C}, {B,A}, {F,E} } { {A,B}, {E,F}, {C,D} } If you look carefully, you'll notice that although the three sequences are different, the _pairings_ that these three sequences provide ARE EXACTLY THE SAME! In the second case, the order of each pair was switched and also the first pair was swapped with the second pair (as blocks). In the third case, no change was made to order within a pair, but second pair and the third pair were swapped (as blocks). So out of all the (2n)! = 6! = 720 permutations of these 6 items, there are many duplications of pairing that will be produced. Within any pair the two items can be switched, just as in your original example you noted that ab and ba are the same pair. Since there are n pairs, that gives 2^n different permutations with the same pairings, differing only in the order within one or more pairs. At the same time one sees that one entire "block" of a pair can be swapped with another such block. Here there are three pairs, so we can permute these "blocks" in 3! ways without changing the underlying pairings that will be dictated by the overall arrangement. Dividing out the multiplicities of these duplications is ONE WAY to arrive at the formula I've given you: (2n)! / [ (2^n) * n! ] = 6! / [ (2^3) * 3! ] In other words, instead of having 6! = 720 different pairings, we will only have: 720 / [ 8 * 6 ] = 15 pairings Let's tackle the same example with one of the OTHER APPROACHES that I've described for you. Here the item A must be paired with some item not equal to A. How many ways can this happen? Well, there are 5 other items besides A, so A can be paired with any one of those 5 items. There are 5 possible pairings for the item A. After we pair of A with another item, how many are left? Now we taken out two items from the original 6, so there are 4 items left. Pick the least item (in alphabetical order) of those remaining, and let's ask how many ways it can be paired to another remaining item. Now the least item of the four items remaining must be paired to one of the 3 items not equal to it. So there are 3 ways for that pair to be formed. How many items are left now? We've removed two pairs from the original 6 items, so only 2 items are left. They can form a pair in only one way. Thus we have completely determined a partition of the original items into pairs by this process of selection. We had 5 choices to pick from in the first step, then 3 choices to pick from in the second step, and finally only 1 choice remained open to us in the last step: 5 * 3 * 1 = 15 ways to partition the 6 items into pairs Hopefully you will see from studying this example something of the general logic behind the formula which I've given you. Good luck, mathtalk-ga```
 `Not bad for two bucks`