# Ways Orange can be arranged

• November 6th 2011, 09:32 AM
BobtheBob
Ways Orange can be arranged
Hi,

Can someone help me with this question as I can't seem to get it:

How many ways can the letters of the word 'orange' be arranged so that no of the letters are in their original place? (i.e can't have ognear as o is in its original place but can have earong)

There are obviously $6!$ number of ways for the letters to be arranged but how do you find out the number of ways without the letters being in the original place?

Thanks for all the help.
• November 6th 2011, 10:04 AM
veileen
Re: Ways Orange can be arranged
Consider o=1, r=2, a=3, n=4, g=5, e=6. So you have the permutation $\bigl(\begin{smallmatrix}1\: 2\: 3\: 4\: 5\: 6 & \\ 1\: 2\: 3\: 4\: 5\: 6\end{smallmatrix}\bigr)$ and you have to fine the number fixed-point-free permutations. You should count all the permutations which have at least one fixed point, note with $A_i$ the set of permutations for which i is a fixed point and use the Inclusion–exclusion principle.
• November 6th 2011, 11:38 AM
BobtheBob
Re: Ways Orange can be arranged
I don't really get what you mean?
• November 6th 2011, 11:53 AM
veileen
Re: Ways Orange can be arranged
For ease, assign each letter a number position, so "o" becomes 1, "r" becomes 2, "a" becomes 3 and so on. Now your problem is how to find the number of fixed-point-free permutations (ognear correspond to 1 5 4 6 3 2 which has a fixed point: 1 or "o"). Now count the permutations which have one fixed point, two fixed points, three, four, five or six fixed points.

If i (so, 1, 2, 3, 4, 5 or 6) is a fixed point for a permutation (e.g. 1 for ognear) then that permutation is included in the set $A_i$. But this way some permutations will be in two or more sets, that's why you have to use the inclusion-exclusion principle.
• November 6th 2011, 12:35 PM
BobtheBob
Re: Ways Orange can be arranged
Ok I sort of see what you are saying. Surely you would just end up with six sets adding up to 720 (6!) still? And how are you supposed to know which points to fix? (Would you not just get, with 1 fixed point, 5!, 2 fixed points, 4! etc?)

Thanks again
• November 6th 2011, 01:31 PM
veileen
Re: Ways Orange can be arranged
Um... I'm the one who doesn't understand what you mean now >.>

The number of permutations which have just one fixed point is $6 \cdot 5!$. If i (again, 1, 2, 3, 4, 5 or 6) is the fixed point then you have five other elements you can arrange in 5! ways. But you do that for every i, so six times.

The number of permutations which have exactly two fixed points is the number of elements of the set $A_i \cap A_j$ (they have i and j fixed points, for i and j from 1 to 6, and $i\leqslant j$), that means $\binom{6}{2} \cdot 3!$.

The number of permutations which have exactly three fixed points is $\binom{6}{3} \cdot 2!$. Same for the rest of them.

The inclusion-exclusion principle: the number of fixed-point-free permutations = the total number of permutations - the number of permutations which have just one fixed point + the number of permutations which have exactly two fixed points - the number of permutations which have exactly three fixed points + the number of permutations which have exactly four fixed points - the number of permutations which have exactly five fixed points + 1 (the number of permutations which have exactly six fixed points )

$6!-5\cdot 5!+15 \cdot 4!-20 \cdot 3!+...$. The "..." will be completed by you. :D
• November 6th 2011, 02:21 PM
Plato
Re: Ways Orange can be arranged
Quote:

Originally Posted by BobtheBob
How many ways can the letters of the word 'orange' be arranged so that no of the letters are in their original place? (i.e can't have ognear as o is in its original place but can have

These are known as derangements.
If we rearrange n objects, then there are $\mathcal{D}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$ ways to have no item in its original place.

So $\mathcal{D}(6)=265.$

Note that $\mathcal{D}(n)\approx\frac{n!}{e}$
• November 7th 2011, 09:45 AM
BobtheBob
Re: Ways Orange can be arranged
Ok thanks Plato, I'm getting that.

Sorry veileen, I'm still not quite getting it. I take it that the ... you want me to do is:

$6!-5\cdot5!+15\cdot4!-20\cdot3!+15\cdot2!-6\cdot1!+1$ which equals 385, not 265 as Plato says...?

Sorry I'm a bit slow perhaps, but I am teaching myself maths in my free time and so trying to do a few questions too.
• November 7th 2011, 10:01 AM
Plato
Re: Ways Orange can be arranged
Quote:

Originally Posted by BobtheBob
$\color{red}6!-5\cdot5!+15\cdot4!-20\cdot3!+15\cdot2!-6\cdot1!+1$ which equals 385, not 265 as Plato says...?
Sorry I'm a bit slow perhaps, but I am teaching myself maths in my free time and so trying to do a few questions too.

This is not an easy concept to try and self-learn.
It follows from repeated applications if the inclusion/exclusion principle. That idea is what was tried, incorrectly, in that reply.
• November 7th 2011, 10:05 AM
veileen
Re: Ways Orange can be arranged
Quote:

which equals 385, not 265 as Plato says...?
Sorry, my fault, it's not $5 \cdot 5!$, but $6 \cdot 5!$ because six points can be fixed points (one at a time).

And that's the prove of the derangements formula. ^^
• November 7th 2011, 10:32 AM
BobtheBob
Re: Ways Orange can be arranged
Ok so i take it that

$6!-6\cdot5!+15\cdot4!-20\cdot3!+15\cdot2!-6\cdot1!+1$ which does equal $265$

I'm getting the hang of this now...

Would you be able to explain how you find how many permutaions which have exactly two points as I don't understand how you come to that, or any other no. of fixed points for that matter (apart for 1 fixed spot as thats obviosly 6)?
• November 7th 2011, 10:43 AM
Plato
Re: Ways Orange can be arranged
Quote:

Originally Posted by BobtheBob
Would you be able to explain how you find how many permutaions which have exactly two points as I don't understand how you come to that, or any other no. of fixed points for that matter (apart for 1 fixed spot as thats obviosly 6)?

Please tell us in you understand inclusion/exclusion ?
If the answer is no, then this question is hard to answer.

We can select two fixed points in $\binom{6}{2}=15$ ways.
There are $4!=24$ ways to rearrange the other four points.
But in some of ways we have more than two fixed points.

So you need to consider all possible arrangements.
• November 7th 2011, 10:56 AM
BobtheBob
Re: Ways Orange can be arranged
Ok I sort of get that.

To be honest, I don't know about the inclusion exclusion principle and have only just heard of it in this thread. I take it (after looking it up a lot) that it is something to do with the union and size of two or more sets. I don't know much more than that and how it helps one find out the answer to this question. Would you be able to explain more?
Sorry, but thanks again for all the help so far!