[Math] The number of distinct bracelets of five beads made up of

combinatoricspermutations

The number of distinct bracelets of five beads made up of $\color{red}{\text{red}}$, $\color{Blue}{\text{blue}}$ and $\color{green}{\text{green}}$ beads (two bracelets are indistinguishable if the rotation of one yield another) is:

  1. $243$
  2. $81$
  3. $51$
  4. $47$

My attempt:

Somewhere it explained as : Combination of 5 beads same color =RRRRR,BBBBB,GGGGG

4 same colors = RRRRB ,RRRRG (similarly Blue and green colors ) =(5!/4! +5!/4!) ⨉3

3 same colors =RRRGB, RRRGG,RRRBB (Similarly other colors)=(5!/3! + 5!/3!2! + 5!/3!2!)⨉3

2 -2 same color , RRBBG, RRGGB, BBGGR =5!/2!2! ⨉3

Adding all we get answer 273.

But, official key is given $(3)\space 51$.

Can you explain it, please?

Best Answer

Let us consider this problem from a graph theory perspective.

Consider the bracelets made up of five beads, which can be of red, blue or green colour. Then let us have $D =\{1,2,3,4,5\}$ is the set of places the beads can take, $C =\{r, b, g\}$ is the set of colours that a bead in a particular place can take and $C_5$ is the cyclic group of order $5$ generated by the permutation $(12345)$. Then the question is: how many orbits does $C_5$ have?. For the identity, $1\in C_5$, clearly, $F(1) = X$.

For a permutation $\alpha \in C_5$, we denote by $F(\alpha)$ the set of elements fixed by $\alpha$ as $F(\alpha) = \{x\in X: \alpha x=x\}$ where $X$ is considered to be the set of all possible bracelets (which are $3^5 = 243$ in number).

Now, we use the Cauchy-Frobenius lemma to find the number of orbits. The original form of the lemma says that, $$N(\tau) =\frac{1}{|\tau|} \sum_{ \alpha \in \tau} |F (\alpha)|$$ where $N(\tau)$ is the number of orbits.

Returning to our problem, we know that for every non-trivial rotation $\alpha \in C_5$, only the three monochromatic bracelets are invariant under $\alpha$, so $$N(\tau) = \frac{1}{5}[243 + 3 + 3 + 3 + 3] = 51$$ Hope it helps.


Reference: Modern Graph Theory by Bella Bollobas (pg.$277-279$)

Related Question