Combinatorics Olympiad Problem 2

Count the number of circular 6-permutations of the multiset { 2 R , 2 W , 2 B } \{2 · R, 2 · W, 2 · B\} .

This problem is not original and is roughly of the level of the BMO. This problem is part of this set .


The answer is 16.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Here the group acting on the set of colorings is the 6 6 -element group consisting of rotations by multiple of 60 60 degrees. By Burnside’s Lemma, the answer is 1 6 ( A + 2 B + 2 C + D ) \frac{1}{6} (A + 2B + 2C + D) , where A is the number of colorings that are invariant under 0 0 degree rotation, B is both the number of colorings that are invariant under 60 60 degree clockwise rotation and the number of colorings that are invariant under 60 60 degree counterclockwise rotation, C is both the number of colorings that are invariant under 120 120 degree clockwise rotation and the number of colorings that are invariant under 120 120 degree counterclockwise rotation, and D is the number of colorings that are invariant under 180 180 degree rotation. We have A = 6 ! / 2 ! 2 ! 2 ! = 90 A = 6!/2!2!2! = 90 (these are just ordinary permutations of the multiset), B = 0 B = 0 (the only way a circular 6-permutation involving R’s, W’s, and B’s can be invariant under 60 60 degree rotation is if all six letters are the same), C = 0 C = 0 (for the same sort of reason as B = 0 B = 0 , but more complicated: a circular 6 6 -permutation involving R’s, W’s, and B’s can be invariant under 120 120 degree rotation only if either some color occurs six times or two of the colors occur three times each, contradicting our requirement that each of the three colors occurs twice), and D = 3 ! = 6 D = 3! = 6 (there are 3 ! 3! ways of assigning the three colors to the three pairs of diametrically opposite positions in the circular 6 6 -permutation, and each of these corresponds to a way of arranging two R’s two B’s, and two W’s). So the number of orbits, i.e., the number of 6 6 -permutations, is 1 6 ( 90 + 6 ) = 16 \frac{1}{6}(90 + 6) = 16 .

This solution is not mine.

Ruben Wiechers
Dec 26, 2018
two consecutive Rs one element between two Rs two elements between two Rs
RRWWBB RBRWBW RWWRBB
RRWBWB RBRWWB RWBRWB
RRWBBW RBRBWW RBWRBW
RRBBWW RWRBWB RBWRWB
RRBWBW RWRBBW
RRBWWB RWRWBB
6 6 4 = 16

I just like to write all permutations. You can check if there are the same amount of permutations in each category with Bs and Ws (considering cyclic-permutations)

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...