Different possibilities of arranging perls in a chain using a group action or combinatorial argument

55 Views Asked by At

We want to build chains of $6$ perls. The perls are provided in $n$ colors: $n_1, n_2, \dotsc, n_n$. We call two such a chains essentially different, if after a rotation by $180^°$ the chains are different, i.e., if swapping the ends of the chain the two chains will be distinguishable between them.

How many essentially different chains can be built?

If the two ends of a chain are of different color then no matter what color the $4$ remaining perls are, the chains will be essentially different. Thus, there will be $C_2^n \cdot n^4$ essentially different chains. I am not sure if by that we exhaust all the possibilities.

Another way to consider can be a group theoretical argument by considering a group action and the set of fixed points and using the Burnside lemma. But I do not know how to use this argument. Do you have any suggestion or a solution proposal? Thanks.

1

There are 1 best solutions below

6
On BEST ANSWER

Ignoring the essentially different condition for a moment, we know that there are $n^6$ chains of perls. To get the number of essentially different chains, we must subtract off the number of pairs of distinct chains which are 180-degree rotations of each other. There are $n^3$ symmetric chains (counted by choosing the colors of the first three beads), which means the remaining $n^6 - n^3$ chains can be divided into $\frac{n^6-n^3}2$ pairs which are rotations of each other. The number of essentially different chains is then $$n^6 - \frac{n^6-n^3}{2} = \frac{n^6+n^3}{2}$$