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 $\displaystyle 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.

Re: Ways Orange can be arranged

Consider o=1, r=2, a=3, n=4, g=5, e=6. So you have the permutation $\displaystyle \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 $\displaystyle A_i$ the set of permutations for which i is a fixed point and use the Inclusion–exclusion principle.

Re: Ways Orange can be arranged

I don't really get what you mean?

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 $\displaystyle 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.

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

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 $\displaystyle 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 $\displaystyle A_i \cap A_j$ (they have i and j fixed points, for i and j from 1 to 6, and $\displaystyle i\leqslant j$), that means $\displaystyle \binom{6}{2} \cdot 3!$.

The number of permutations which have exactly three fixed points is $\displaystyle \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 )

$\displaystyle 6!-5\cdot 5!+15 \cdot 4!-20 \cdot 3!+...$. The "..." will be completed by you. :D

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 $\displaystyle \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 $\displaystyle \mathcal{D}(6)=265.$

Note that $\displaystyle \mathcal{D}(n)\approx\frac{n!}{e}$

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:

$\displaystyle 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.

Re: Ways Orange can be arranged

Quote:

Originally Posted by

**BobtheBob** $\displaystyle \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.

That answer is incorrect.

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.

Re: Ways Orange can be arranged

Quote:

which equals 385, not 265 as Plato says...?

Sorry, my fault, it's not $\displaystyle 5 \cdot 5!$, but $\displaystyle 6 \cdot 5!$ because six points can be fixed points (one at a time).

And that's the prove of the derangements formula. ^^

Re: Ways Orange can be arranged

Ok so i take it that

$\displaystyle 6!-6\cdot5!+15\cdot4!-20\cdot3!+15\cdot2!-6\cdot1!+1$ which does equal $\displaystyle 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)?

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 $\displaystyle \binom{6}{2}=15$ ways.

There are $\displaystyle 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.

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!