Thread: combinatorics around a circle

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: .

If they were arranged in a row, there are: . arrangements.

. . Since they are in a circle, there are: . 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: .
. . In a row, there are: . arrangements.

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

But since they are arranged in a circle, there are: . ways.


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


Therefore, there are: . ways in which the cars are not adjacent.

Originally Posted by Soroban

Therefore, there are: . 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?

Originally Posted by Plato

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 as before.
In 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



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



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



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)