Combinatorics Question

[nacho]

I don't know how to use LaTex or w/e it's called so I wrote it in word.
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

[TrueTears]

Wow I like this question, is it in a Methods textbook or something? Anyways combinatorics is one of my fave areas of pure maths so here's my method:

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 simply replace with and you get your result.

Now a combinatorial argument goes like this to prove the identity, consider the specific case where and .

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 ways to pick the group with A and ways to pick the group without A. Thus there are ways in total to pick a committee of 11 from 18 people. But there are ways of picking that, so ways in total."

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.

[nacho]

Thanks Simon,
generally in learning how to solve a problem, i find a logical approach better than mathematical statements

As for the second question, what do you mean 'this is a conjuctive scenario'?

[TrueTears]

Yeah, the book's way is a purely algebraic approach which should not be discarded, often in combinatorics you will see there is a combinatorial argument method and also an algebraic manipulation exercise, often the algebraic manipulation involves induction and sometimes a speck of ingenuity, combinatorial arguments also require wishful thinking and creativeness.


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.

[Ahmad]

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!).

[nacho]

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' ?

[TrueTears]

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.

[nacho]

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.

(Image removed from quote.)

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?
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 .

[TrueTears]

Try not to think of permutations and combinations separately, they are in fact very similar and derived from each other.

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".

[nacho]

Okay, well.
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

Alternatively, to find the ways the children can be selected, you can use the box method.
[ 6 ] [ 5 ] [ 4 ] = 120

So in total, this can be done in 360 ways

[TrueTears]

There's a loophole in your logic

Close but just fix up a little bit and you'd be right.

[TrueTears]

O just saw your edit, it's right now

Now can you think of a method which includes order straight from the start?

[nacho]

I'm not entirely sure what you mean by this 'order from the start'.
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?

[TrueTears]

First can we pick a boy ( ways) then we pick a toy for this boy (3 ways) then we pick 2 girls but counting order ( ways)

So in total we have ways