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
|
