Results 1 to 13 of 13

Math Help - Ways Orange can be arranged

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    Re: Ways Orange can be arranged

    I don't really get what you mean?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1

    Re: Ways Orange can be arranged

    Quote Originally Posted by BobtheBob View Post
    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}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1

    Re: Ways Orange can be arranged

    Quote Originally Posted by BobtheBob View Post
    \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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    Re: Ways Orange can be arranged

    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. ^^
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    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)?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,383
    Thanks
    1474
    Awards
    1

    Re: Ways Orange can be arranged

    Quote Originally Posted by BobtheBob View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Oct 2011
    Posts
    37

    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] How many ways
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 17th 2011, 05:28 PM
  2. Regularly arranged matrices
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 25th 2011, 02:27 AM
  3. No of ways ?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2010, 08:43 AM
  4. How many ways can the word "Think" be arranged?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2009, 01:54 PM
  5. How many ways are there ?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 26th 2009, 04:51 AM

Search Tags


/mathhelpforum @mathhelpforum