Post by: nacho on November 20, 2010, 03:34:17 pm
See question attached. (Those are supposed to be in ' nCr ' but MS Word would not allow this)
I've got the solution with me (it'd take a year to type out in word) and I understand it.
It shows that
n.C.r = n! / [ (n-r)! r! ] and n.C.r-1 = n!/[ (n-r+1)! x (r-1)! ]
. It then adds them, expands etc etc until it gets to the stage where this is equivalent to
n+1. C . r which is (n+1)!/ [ (n+1-r)! x r! ].
Pretty simple right?
So i was just wondering whether the only way to do this question was trial and error/process of elimination? Because the solution starts by stating
"Because n.C.r + n.C.r-1 ...."
Also, another question:
In how many ways can a party of 18 people be divided into three equal groups in three different rooms?
Answer =
18.C.6 x 12.C.6 x 6.C.6 = 17153136.
I had close to the same thing, but I'm not sure why the multiplication principle was used and also thought that there is a bit more to this answer as the three groups must be divided into 3 different rooms?
As in the question is asking:
1. How many ways to divide 18 people into three equal groups?
2. How many ways can these three different groups be placed in three different rooms?
Perhaps my interpretation of the question is incorrect?
Thanks.
edit: solution is upped
Post by: TrueTears on November 20, 2010, 06:56:30 pm
Often in combinatorics you will hear of a slick technique called "combinatorial argument" it's a great way of proving questions, in fact, one of the most famous recurrence problems called the catalan recurrence can be solved purely by combinatorial arguments. http://en.wikipedia.org/wiki/Catalan_number and http://en.wikipedia.org/wiki/Catalan_number#Fourth_proof
So what are combinatorial arguments? I will illustrate them in your first question.
First your question is a famous identity called the Summation Identity, basically it states
Now a combinatorial argument goes like this to prove the identity, consider the specific case where
My combinatorial argument is "Consider a group of 18 people, 11 picked from a committee, assume 2 ways of picking 11 people, we pick person A into a group and another group without A. Now there are
Now replace the specific case with a general case and you are done :)
For your second question we assume the 18 people are irreplaceable. We take off 6 people each time because of the former assumption, we multiply them because of this conjunctive scenario. Note the question did not give you a choice, ie, say "divided into 3 groups into 1 or 2 or 3 different rooms" or else it would be disjunctive and we would need to add other cases.
Post by: nacho on November 20, 2010, 07:42:44 pm
generally in learning how to solve a problem, i find a logical approach better than mathematical statements :D
As for the second question, what do you mean 'this is a conjuctive scenario'?
Post by: TrueTears on November 20, 2010, 09:49:04 pm
What I mean by conjunctive is that you need to have 3 equal groups in EXACTLY 3 different groups, in other words, you can't have 3 equal groups in 1 OR 2 OR 3 different groups. Say we have group A, B and C each consists of 6 people and name our rooms X, Y and Z. If this was disjunctive, we could have A, B and C all in room X and none in Y and Z. However, WLOG, assume we have A in X, B in Y and C in Z (ie, create a bijection b/w groups and room) then we have a conjunctive scenario, we MUST have A AND X, B AND Y, C and Z, hence the multiplication.
Post by: Ahmad on November 21, 2010, 09:55:36 am
Post by: nacho on November 21, 2010, 04:44:36 pm
Another way to think about the question: number the people from 1 to 18 (write it on their shirts!), there's 18! different ways to line them up in a single line. Now put the first six people in room 1, second six in room 2 and last six in room 3. We've overcounted because if we rearranged the order of the first six people in the line, for example, we get the same separation of people into the three rooms, so we divide by 6! for each group of six people, giving the final answer 18!/(6!6!6!).
Ah, is this because the people can be considered as 'identical objects' ?
Post by: TrueTears on November 21, 2010, 04:53:46 pm
Another way to think about the question: number the people from 1 to 18 (write it on their shirts!), there's 18! different ways to line them up in a single line. Now put the first six people in room 1, second six in room 2 and last six in room 3. We've overcounted because if we rearranged the order of the first six people in the line, for example, we get the same separation of people into the three rooms, so we divide by 6! for each group of six people, giving the final answer 18!/(6!6!6!).Yes we assume they are indistinguishable.
What Ahmad just used was a simple application of the Mississippi Rule, just a formalisation of the maths behind the logic.
(http://img263.imageshack.us/img263/7835/mississippiformula.jpg)
Post by: nacho on November 21, 2010, 05:03:48 pm
Ah right I remember seeing this somewhere before (not the actual rule, but the method of finding permutations of identical and distinguishable objects). This is only applied to permutations right?Another way to think about the question: number the people from 1 to 18 (write it on their shirts!), there's 18! different ways to line them up in a single line. Now put the first six people in room 1, second six in room 2 and last six in room 3. We've overcounted because if we rearranged the order of the first six people in the line, for example, we get the same separation of people into the three rooms, so we divide by 6! for each group of six people, giving the final answer 18!/(6!6!6!).
Yes we assume they are indistinguishable.
What Ahmad just used was a simple application of the Mississippi Rule, just a formalisation of the maths behind the logic.
(http://img263.imageshack.us/img263/7835/mississippiformula.jpg)
Just to double up
Permutations = re-arranging objects 18.P.6 = how many ways to re-arrange 6 people from 18 into a row
Combinatorics = selecting objects thus 18.C.6 = how many ways to select 6 people from 18
So then this question, could be solved using either combinatorics OR permutations?
Combinatorics using the solution provided and permutations using ahmed's solution?
Funny too, after looking at Ahmed's signature, i read up on Ramanujan .
Post by: TrueTears on November 21, 2010, 05:09:23 pm
The algebraic exercise is simple:
I leave the logically interpretation to you.
What I'm trying to emphasize is that most questions can be done through either thinking about combinations or permutations, they are very closely related.
Eg, consider this example:
Suppose we have 3 different toys and we want to give them away to 2 girls and 1 boy (one toy per child). The children will be selected from 4 boys and 6 girls. In how many ways can this be done?
There are 2 ways of doing this, you can either ignore the order from the start, or you can include the order from the start. See if you can think of both solutions, this will test whether you really understand the relationship rather than simply manipulating the definitions of combinations and permutations "formulas".
Post by: nacho on November 21, 2010, 05:18:46 pm
the three different toys can be given to the three children in 3! ways = 6.
And the children can be selected in 60 different ways : 6.C.2 x 4.C.1
[ 6 ] [ 5 ] [ 4 ] = 120
So in total, this can be done in 360 ways
Post by: TrueTears on November 21, 2010, 05:21:14 pm
Close but just fix up a little bit and you'd be right.
Post by: TrueTears on November 21, 2010, 05:28:19 pm
Now can you think of a method which includes order straight from the start?
Post by: nacho on November 21, 2010, 05:36:11 pm
I found how many ways the three different gifts can be given out to 3 children (2 girls, 1 boy)
and how many ways 2 girls and 1 boy can be selected from the given children.
Order from the start would mean to?
Post by: TrueTears on November 21, 2010, 05:43:05 pm
So in total we have