permutation help! (1 Viewer)

john-doe

Member
Joined
Jul 29, 2012
Messages
179
Gender
Male
HSC
2012
can someone explain and show me the working out of this question?

If the letters of the word GUMTREE and the letters of the word KOALA are combined
and arranged into a single twelve-letter word, in how many of these arrangements do the
letters of KOALA appear in their correct order, but not necessarily together?

thanks!

and will it help if i keep doing extension questions from cambridge textbook? they are extremely hard!!
 
Last edited:

Sy123

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013


Simply treat the word KOALA as a whole, then find the number of different arrangements of this 'seven' element word. The reason you dont have a multiplier of 5! is that we dont want KOALA to have a different order. So we treat it so it cant change order, hence our answer.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013


Simply treat the word KOALA as a whole, then find the number of different arrangements of this 'seven' element word. The reason you dont have a multiplier of 5! is that we dont want KOALA to have a different order. So we treat it so it cant change order, hence our answer.
You can't just treat the word KOALA as a whole.
 

Sy123

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013
Oh hang on I didnt see the other part saying not necessarily together. My bad.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
I got 4324320.

The working out is going to be very hard to explain and very tedious to type out, so I want to make sure that it's correct before actually writing out the solution. So is this right?
 

bleakarcher

Active Member
Joined
Jul 8, 2011
Messages
1,509
Gender
Male
HSC
2013
I remember attempting this question lol, I was going to explode.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
I remember attempting this question lol, I was going to explode.
The way to do this question is using the idea of triangular numbers like I told you about a while back. But for this question you have to extend the triangular numbers to summations of triangular numbers than the summation of the summation of triangular numbers etc lol.
 

bleakarcher

Active Member
Joined
Jul 8, 2011
Messages
1,509
Gender
Male
HSC
2013
I got 4324320.

The working out is going to be very hard to explain and very tedious to type out, so I want to make sure that it's correct before actually writing out the solution. So is this right?
The answer is 1 995 840 according to my textbook.
 

bleakarcher

Active Member
Joined
Jul 8, 2011
Messages
1,509
Gender
Male
HSC
2013
The way to do this question is using the idea of triangular numbers like I told you about a while back. But for this question you have to extend the triangular numbers to summations of triangular numbers than the summation of the summation of triangular numbers etc lol.
YES FUCK!! it gets confusing as shit lol. thanks for teaching me that man. it has actually come in handy.
 

john-doe

Member
Joined
Jul 29, 2012
Messages
179
Gender
Male
HSC
2012
But do u guys think that they will ask these difficult questions in the hsc?
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
YES FUCK!! it gets confusing as shit lol. thanks for teaching me that man. it has actually come in handy.
Basically this is what I've found, and I'm pretty sure it works:

For questions where you want to find how many ways letters can be arranged so that the letters are in a certain order (ie the letter "a" precedes the letter "b"), you can use the following:

Consider you wanted to arranged 'n' letters and you want 'k' of those letters to be in a particular order, like the question in this thread (the letters of koala need to be in order, so in this case n=12 and k=5). Then the following is what you do (I think):

For k=2, amount of arrangements is:

which is just the '(n-1)'th triangular number.

This can also be written as:



For k=3, amount of arrangements is:



For k=4, amount of arrangements is:



For k=5, amount of arrangements is:



Etc.

I'm going to go through this post and make sure I haven't did a typo or something and make sure everything is correct as well.

But notice how the number on top of the summations always goes down by 1? It goes from n-1, to n-2, to n-3, to n-4, etc. And you just keep adding a summation each time basically.
 
Last edited:

Sy123

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013
Basically this is what I've found, and I'm pretty sure it works:

For questions where you want to find how many ways letters can be arranged so that the letters are in a certain order (ie the letter "a" precedes the letter "b"), you can use the following:

Consider you wanted to arranged 'n' letters and you want 'k' of those letters to be in a particular order, like the question in this thread (the letters of koala need to be in order, so in this case n=12 and k=5). Then the following is what you do (I think):

For k=2, amount of arrangements is:

which is just the '(n-1)'th triangular number.

This can also be written as:



For k=3, amount of arrangements is:



For k=4, amount of arrangements is:



For k=5, amount of arrangements is:



Etc.

I'm going to go through this post and make sure I haven't did a typo or something and make sure everything is correct as well.

But notice how the number on top of the summations always goes down by 1? It goes from n-1, to n-2, to n-3, to n-4, etc. And you just keep adding a summation each time basically.
This method is ingenious...

Can you explain why this works though?
 

bleakarcher

Active Member
Joined
Jul 8, 2011
Messages
1,509
Gender
Male
HSC
2013
Basically this is what I've found, and I'm pretty sure it works:

For questions where you want to find how many ways letters can be arranged so that the letters are in a certain order (ie the letter "a" precedes the letter "b"), you can use the following:

Consider you wanted to arranged 'n' letters and you want 'k' of those letters to be in a particular order, like the question in this thread (the letters of koala need to be in order, so in this case n=12 and k=5). Then the following is what you do (I think):

For k=2, amount of arrangements is:

which is just the '(n-1)'th triangular number.

This can also be written as:



For k=3, amount of arrangements is:



For k=4, amount of arrangements is:



For k=5, amount of arrangements is:



Etc.

I'm going to go through this post and make sure I haven't did a typo or something and make sure everything is correct as well.

But notice how the number on top of the summations always goes down by 1? It goes from n-1, to n-2, to n-3, to n-4, etc. And you just keep adding a summation each time basically.
how awesome..
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
This method is ingenious...

Can you explain why this works though?
I'll use an example, it'll be much easier to see I think with an example.

Take the letters of the word MATHS and arrange them so the 'A' always comes after the 'M'.

Fix the 'M' in the first spot:

M A _ _ _

M _ A _ _

M _ _ A _

M _ _ _ A

So there are 4 ways to do this, now fix the M in the 2nd spot:

_ M A _ _

_ M _ A _

_ M _ _ A

So there are 3 ways to do this, now fix the 'M' in the 3rd spot:

_ _ M A _

_ _ M _ A

So there are 2 ways, and finally fix the 'M' in the 4th spot:

_ _ _ M A

So there is only 1 way.

Amount of ways = 1 + 2 + 3 + 4 = 10

This is just the 4th triangular number. If we used the letters ABCDEF and had B after A, it would be the 5th triangular number, and so on, hence it is the (n-1)th triangular number when there are n letters.

Now consider MATHS again, and say we want A to be after M, and T to be after A, so in this order - MAT:

Fix M in the first spot:

M A T _ _

M A _ T _

M A _ _ T

M _ A T _

M _ A _ T

M _ _ A T

Which is 6 ways.

So you should be able to see that when we fix M in the first spot, there are now only 4 letters instead of 5, and we want to arrange 2 letters again (A and T) like befor, so we can use the (n-1) triangular number, so since n is now 4, we have the 3rd triangular number, which is 1+2+3=6 as required.

If we fix M in the 2nd spot we get:

_ M _ _ _

So if we put A and T in there, the amount of ways will be the (n-1) triangular number, and we know there are only 3 spaces to put the A and T, so 'n' is now 3, hence it is the 2nd triangular number, that is 1+2=3.

If we fix M in the 3rd position we get:

_ _ M _ _

And now there are only 2 letters, so using (n-1) it is the 1st triangular number, hence there is only 1 arrangement with M in the 3rd spot (which should be obvious, it is _ _ M A T).

So the total arrangements when A comes before M, and T comes before A (M A T), is 6 + 3 + 1 = 3rd triangular number + 2nd triangular number + 1st triangular number = Sum of the first (n-2) triangular numbers (remember that 'n' is the total amount of letters in the word, in this case MATHS, so n=5, (n-2)=3, sum of first 3 triangular numbers).

If I then wanted it so that 4 letters are in order, for example M A T H in that oder, it would just become the "sum of the sum of the (n-3) triangular numbers) since it will follow the same pattern as before.

Hope this makes sense lol.
 

Sy123

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013
I'll use an example, it'll be much easier to see I think with an example.

Take the letters of the word MATHS and arrange them so the 'A' always comes after the 'M'.

Fix the 'M' in the first spot:

M A _ _ _

M _ A _ _

M _ _ A _

M _ _ _ A

So there are 4 ways to do this, now fix the M in the 2nd spot:

_ M A _ _

_ M _ A _

_ M _ _ A

So there are 3 ways to do this, now fix the 'M' in the 3rd spot:

_ _ M A _

_ _ M _ A

So there are 2 ways, and finally fix the 'M' in the 4th spot:

_ _ _ M A

So there is only 1 way.

Amount of ways = 1 + 2 + 3 + 4 = 10

This is just the 4th triangular number. If we used the letters ABCDEF and had B after A, it would be the 5th triangular number, and so on, hence it is the (n-1)th triangular number when there are n letters.

Now consider MATHS again, and say we want A to be after M, and T to be after A, so in this order - MAT:

Fix M in the first spot:

M A T _ _

M A _ T _

M A _ _ T

M _ A T _

M _ A _ T

M _ _ A T

Which is 6 ways.

So you should be able to see that when we fix M in the first spot, there are now only 4 letters instead of 5, and we want to arrange 2 letters again (A and T) like befor, so we can use the (n-1) triangular number, so since n is now 4, we have the 3rd triangular number, which is 1+2+3=6 as required.

If we fix M in the 2nd spot we get:

_ M _ _ _

So if we put A and T in there, the amount of ways will be the (n-1) triangular number, and we know there are only 3 spaces to put the A and T, so 'n' is now 3, hence it is the 2nd triangular number, that is 1+2=3.

If we fix M in the 3rd position we get:

_ _ M _ _

And now there are only 2 letters, so using (n-1) it is the 1st triangular number, hence there is only 1 arrangement with M in the 3rd spot (which should be obvious, it is _ _ M A T).

So the total arrangements when A comes before M, and T comes before A (M A T), is 6 + 3 + 1 = 3rd triangular number + 2nd triangular number + 1st triangular number = Sum of the first (n-2) triangular numbers (remember that 'n' is the total amount of letters in the word, in this case MATHS, so n=5, (n-2)=3, sum of first 3 triangular numbers).

If I then wanted it so that 4 letters are in order, for example M A T H in that oder, it would just become the "sum of the sum of the (n-3) triangular numbers) since it will follow the same pattern as before.

Hope this makes sense lol.
Thanks for taking the time to post it up heh, I get the concept now.
 

deterministic

Member
Joined
Jul 23, 2010
Messages
423
Gender
Male
HSC
2009
1) Since you want the letters of KOALA in order, fix those first:
__ K __ O __ A __ L __ A __
The lines indicate the spots the letters of GUMTREE can be placed

2) Choose the spot for the letter G: 6 spots means 6 ways to do so. Then our arrangement becomes something like (depending on your spot for G):
__ K __ O __ A __ L __ G __ A __

3) Choose the spot for the 2nd letter: Now there are 7 spots and hence 7 ways to do so. Then our arrangement becomes something like:
__ K __U __ O __ A __ L __ G __ A __

Continue this above pattern for each letter of GUMTREE, and then dividing by 2 since the letter E is repeated, we get the number of ways to be: 6*7*8*9*10*11*12/2=1995840
 

DAFUQ

Member
Joined
Jul 15, 2012
Messages
41
Gender
Male
HSC
2011
No. of arrangements= (7!/2!) x [ 6 + 6C2 (2!+2!+2!) + 6C3 ( 3!/2! + 3! + 3!/2! + 3!/2!) + 6C4 (4!/3!+4!/2!+4!/3!) + 6C5 ( 5!/4! + 5!/3!2! ) + 6C6 x 6!/5!]

dumb question because its unnecessarily long

EDIT: Almost forgot last bracket

EDIT #2: that long thing evaluates to 1995840
 
Last edited:

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top