0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$)

$\endgroup$
1
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – ً ً Dec 26 '16 at 9:57
1
$\begingroup$

Verify that any necklace may be characterized via one of the patterns below.

Recall that there are $\frac{3!}{(3-n)!}$ ways to put 3 things into n ordered slots.

xxxxx: 3 = $\frac{3!}{(3-1)!}$

xxxxy: 6 = $\frac{3!}{(3-2)!}$

xxxyy: 6 = $\frac{3!}{(3-2)!}$

xxxyz: 6 = $\frac{3!}{(3-3)!}$

xxyyz: 6 = $\frac{3!}{(3-3)!}$

xxyxy: 6 = $\frac{3!}{(3-2)!}$

xxyxz: 6 = $\frac{3!}{(3-3)!}$

xxyzy: 6 = $\frac{3!}{(3-3)!}$

xyzyz: 6 = $\frac{3!}{(3-2)!}$

3 + 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6 = 51

$\endgroup$
1
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – ً ً Dec 26 '16 at 9:57

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.