2
$\begingroup$

Find the number of merry-go-rounds formed by 10 carriages of two different colors

i tried this problem with 4 carriages:
let the colors be {0,1}
so with 2 colors and 4 carraiges the cofiguration is:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

0010, 0010, 0100, 1000 are the same
so there is 0000, 0010, 0011, 0101, 0111, and 1111
so there is total 6 possible ways to color a 4 carriage merry go round with two colors is 6

what if there are m carriges and n colors, how to approach the problem? and what is the general formula for it?

$\endgroup$
  • 1
    $\begingroup$ Can you see that $6 = \binom {4}{2}$? $\endgroup$ – Rohan Feb 16 '17 at 9:14
  • $\begingroup$ so wil it be $45 = \binom {10}{2} $ ? $\endgroup$ – Nirban Feb 16 '17 at 9:21
  • $\begingroup$ but when I tried with 3 carraiges and two colors I got 000, 001, 011, 111 there is 4 ways to do so, but $\binom{3}{2} = 3 $ $\endgroup$ – Nirban Feb 16 '17 at 9:33
  • $\begingroup$ no thats not the case, a merry go round is circular so 0 0 1 1 is not same as 0 1 0 1 . but 0011 is same as 0110, 1100, and 1001 $\endgroup$ – Nirban Feb 16 '17 at 9:43
2
$\begingroup$

You can use Polya's enumeration method if you know it. If you consider these cases the same: enter image description here

we have $D_m$ as the symmetry group of the merry-go-around, otherwise we have $C_m$ as its symmetry group. ($D_m$ is the dihedral group of order $2m$ and $C_m$ is the cyclic group of order $m$) Denote by $G$ the symmetry group chosen.

In order to use Polya's method, we need the cycle index of $G$. These can be found here. This is a polynomial $Z(x_1, \ldots, x_m)$. Suppose we have $n$ colours, then Polya's method says that the number of merry-go-arounds with $m$ carriages and $n$ is $Z(n, \ldots, n)$.

Now in the case when $m=10$ and $n=2$, we get the cycle index with respect to $C_{10}$ is $$\frac{1}{10}(x_1^{10} + x_2^5 + 4x_5^2 + 4x_{10})$$ plugging in $2$ we get $\frac{1}{10}(2^10 + 2^5 + 4\cdot 2^2 + 4 \cdot 2)=108$.

The cycle index of $D_{10}$ is $$\frac{1}{20}(x_1^{10} + x_2^5 + 4x_5^2 + 4x_{10}) + \frac{1}{4}(x_1^2x_2^4+x_2^5)$$ plugging in $2$ we get $54 + \frac{1}{4}(2^22^4+2^5)=78$.

In case of $C_m$ the general formula is $$\frac{1}{m}\sum_{d \mid m} \varphi(d) n^{m/d}$$ where the sum is over all divisors $1 \leq d \leq m$ and where $\varphi$ is the Euler totient function.

In the case of $D_m$ as the symmetry group there are 2 cases: If $m$ is even, then the formula becomes: $$\frac{1}{2m}\sum_{d \mid m} \varphi(d) n^{m/d} + \frac{n^{m/2}}{4}(n + 1)$$

If $m$ is odd, then the formula becomes: $$\frac{1}{2m}\sum_{d \mid m} \varphi(d) n^{m/d} + \frac{n^{(m-1)/2}}{2}$$

$\endgroup$
  • $\begingroup$ Thanks for the answer, I Think I have to learn group Theory of this.... $\endgroup$ – Nirban Feb 18 '17 at 7:10
0
$\begingroup$

Perhaps my solution is more suitable for your purposes.

For a train of 10 carriages

$c_1$-$c_2$-$c_3$-$c_4$-$c_5$-$c_6$-$c_7$-$c_8$-$c_9$-$c_{10}$

and two colors $\{0,1\}$ there are $2^{10}$ possible configurations. But, since in a merry-go-round, rotation is accepted, we have counted configurations that are the same. Now, I distinguish different cases depending if a configuration of a train remains the same under 1,2,5 or 10 rotations of every carriage one position to the left (Notice that this fact is only possible for the divisors of 10). For example the next configuration is the same as in the beginning after 2 rotations of this kind.

1-0-1-0-1-0-1-0-1-0 ---> 0-1-0-1-0-1-0-1-0-1 ---> 1-0-1-0-1-0-1-0-1-0

Then, we obtain the following possibilities for a train after 1,2,5 or 10 rotations (and not less):

  • 1 rotation -> This is only possible if the train has only 1 color : 0-0-0-0-0-0-0-0-0-0 or 1-1-1-1-1-1-1-1-1-1.
  • 2 rotations -> Necessarily we have that $c_1=c_3=c_5=c_7=c_9$ and $c_2=c_4=c_6=c_8=c_{10}$ then, we have two cases 1-0-1-0-1-0-1-0-1 and 0-1-0-1-0-1-0-1-0.
  • 5 rotations -> In this case we have that $c_1=c_6$, $c_2=c_7$, $c_3=c_8$, $c_4=c_9$, $c_5=c_{10}$ and we have $2^5-2=30$ configurations for trains of this kind. (Notice that we have discounted the two trains with only 1 color).
  • 10 rotations -> In this case we have the configurations remaining, because every train of 10 elements remains the same under 10 rotations of this kind. Then we have $2^{10}-30-2-2=990$ configurations.

Now, in order to count all the merry-go-rounds, we have to consider that if a configuration of a train is the same under

  • 10 rotations -> we have counted the same configuration 10 times.
  • 5 rotations -> we have counted the same configuration 5 times.
  • 2 rotations -> we have counted the same configuration 2 times.

Then, the number of different merry-go-rounds formed by 10 carriages of two different colors is

$$\frac{1}{10} \cdot 990 + \frac{1}{5} \cdot 30 + \frac{1}{2} \cdot 2 + \frac{1}{1} \cdot 2 =108,$$

obtaining the same result as Simon Marynissen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.