Results 1 to 4 of 4

Math Help - combinatorics around a circle

  1. #1
    boxcarracer
    Guest

    combinatorics around a circle

    A manufacturer of merry-go-rounds uses 8 identical wooden horses, 4 identical plastic motorbikes and 2 different miniature car. They are all equally connected around the rim of a circular moving base. Establish how many different arrangements there can be if the 2 cars are not to be placed in consecutive positions.

    I don't understand how to work it out if you don't want the 2 cars to be next to each other.

    Any help would be much appreciated.

    thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,806
    Thanks
    697
    Hello, boxcarracer!

    This is not a simple problem.
    . . I hope I got it right . . .


    A manufacturer of merry-go-rounds uses 8 identical wooden horses,
    4 identical plastic motorbikes and 2 different miniature car.
    They are all equally connected around the rim of a circular moving base.

    Establish how many different arrangements there can be
    if the two cars are not to be placed in consecutive positions.

    There are 8 identical horses, 4 identical bikes and 2 different cars.
    The objects are: . \{H,\,H,\,H,\,H,\,H,\,H,\,H,\,H,\,B,\,B,\,B,\,B,\,  C_1,\,C_2\}

    If they were arranged in a row, there are: . {14\choose 8,4,1,1} \:=\:90,090 arrangements.

    . . Since they are in a circle, there are: . 90,090 \div 14 \:=\:6435 arrangements.


    Now we'll find the number of ways the two cars are together.

    Duct-tape the two cars together.
    Then we have 13 "objects" to arrange: . \{H,H,H,H,H,H,H,H,B,B,B,B,\boxed{C_1C_2} \}
    . . In a row, there are: . {13\choose8,4,1} \:=\:6435 arrangements.

    But the two cars could be taped like this: . \boxed{C_2C_1}
    . . which creates another 6435 arrangements, for a total of 12,870 ways.

    But since they are arranged in a circle, there are: . 12,870 \div 13 \:=\:990 ways.


    Recap: .There are 6435 possible arrangements.
    . . . . . .In 990 of them, the two cars are adjacent.


    Therefore, there are: . 6435 - 990 \:=\:{\color{blue}5445} ways in which the cars are not adjacent.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    Quote Originally Posted by Soroban View Post
    Therefore, there are: . 6435 - 990 \:=\:{\color{blue}5445} ways in which the cars are not adjacent.
    That certainly the same answer that I got.
    However, I first looked at the case where the cars were identical; that minor change made the calculation much more difficult for me.
    How would you approach that changed problem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member F.A.P's Avatar
    Joined
    Dec 2006
    Posts
    26
    Quote Originally Posted by Plato View Post
    That certainly the same answer that I got.
    However, I first looked at the case where the cars were identical; that minor change made the calculation much more difficult for me.
    How would you approach that changed problem?
    'bit of a teaser this one...

    When there are multiple occureces of objects one has to be cautious when determining the number of unique permutations around a circle. What one has to look out for is the possibility of repeating sequences.

    In the case where at least one object occurs only once there is no chance of repeating and one can proceed as according to Soroban's post.

    However... In the case when the two cars are identical we have an even number of occurences for all objects. This means that we can divide the objects into two identical groups of size 7.

    CBBHHHH CBBHHHH

    The number of unique row-permutations is given by \frac{14!}{8!4!2!}=45045 as before.
    In \frac{7!}{4!2!}=105 of these row-permutations the second group will repeat the sequence of the first.

    This means that we can't just divide by 14 to get the number of unique permutations around a circle. (It doesn't even result in an integer...)

    105 of the row-permutations should only be divided by 7, beacause in the 8th position the sequence is repeated.

    The remaining 45045 - 105 = 44940 permutations we divide by 14 giving a total of

    \frac{105}{7}+\frac{44940}{14}= 15 +3210 = 3225

    unique circle-permutations.
    Again the cars are glued together resulting in

    \frac{13!}{8!4!1!}\cdot \frac{1}{13}=495

    unique circle-permutations with the cars being adjacent. (No repetitions here because we have only one "double-car"-object)

    Thus the total number of unique permutations with the identical cars separated is

    3225-495=2730

    cheers...

    (If we would've had 4 cars we could have divided the objects into both two AND four identical groups... allowing for repeating... Corresponding situations arise if the objects occur in multiples of 3,5,6.........etc...etera)
    Last edited by F.A.P; September 28th 2007 at 12:20 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Circle, tangent line, and a point not on the circle
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: March 31st 2011, 01:40 PM
  2. Replies: 6
    Last Post: July 8th 2010, 05:39 PM
  3. Replies: 7
    Last Post: March 15th 2010, 04:10 PM
  4. Replies: 2
    Last Post: February 6th 2010, 08:31 AM
  5. Replies: 0
    Last Post: October 12th 2008, 04:31 PM

/mathhelpforum @mathhelpforum