How many different necklaces can be made from beads. If we have
- 10 green beads
- 5 red beads
- 3 yellow beads
And we will use all the beads for creation of necklace.
Disclaimer: Not a homework question, just preparing for test
[Math] How many necklaces can be made from 18 beads of 3 different colours.
combinatoricspermutations
Related Solutions
The problem of calculating the number $p_n$ of necklaces when reflections are included among the admissible symmetries is just as easy, as the equivalence classes are still of the same size $2n$, giving $$p_n = \frac{n!}{2n} = \frac{1}{2} (n-1)!.$$
To compute this with Polya counting we need the cycle index $Z(D_n)$ of the dihedral group $D_n$, which contains reflections and rotations. It is given by $$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2}, & n \mbox{ odd, } \\ \frac{1}{4} \left( a_1^2 a_2^{(n-2)/2} + a_2^{n/2} \right), & n \mbox{ even.} \end{cases}.$$ There is more information here.
The cycle index computation confirms the result of the basic analysis:
with(numtheory);
with(group):
with(combinat):
pet_cycleind_dihedral :=
proc(n)
local d, s, t;
s := 0;
for d in divisors(n) do
s := s + phi(d)*a[d]^(n/d);
od;
if type(n, odd) then
t := n*a[1]*a[2]^((n-1)/2);
else
t := n/2*(a[1]^2*a[2]^((n-2)/2)+a[2]^(n/2));
fi;
(s+t)/2/n;
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
v :=
proc(n)
option remember;
local p, k, gf;
p := add(cat(q, k), k=1..n);
gf := expand(pet_varinto_cind(p, pet_cycleind_dihedral(n)));
for k to n do
gf := coeff(gf, cat(q, k), 1);
od;
gf;
end;
The code in action looks like this:
> seq([n, v(n), (n-1)!/2], n=1..12); [1, 1, 1/2], [2, 1, 1/2], [3, 1, 1], [4, 3, 3], [5, 12, 12], [6, 60, 60], [7, 360, 360], [8, 2520, 2520], [9, 20160, 20160], [10, 181440, 181440], [11, 1814400, 1814400], [12, 19958400, 19958400]
Remark July 4 2018. Let me observe once more that with all beads a distinct color all orbits are the same size namely $2n$, giving the answer $(n-1)!/2.$ Polya counting is not needed here because Burnside says that if we have $n$ different colors and a color is to be constant on the cycles we need a permutation that factors into at least $n$ cycles. There is only one of these namely the identity which has $n$ fixed points. The number of ways of assigning the $n$ colors to these fixed points is $n!$ and we once more obtain $n!/2/n.$ On the other hand the cycle index becomes useful when we seek to classify bracelets according to the distribution of colors where colors may be repeated. For example with three colors red green and blue and a bracelet of six beads we get
$$Z(D_6)(R+B+G) = {B}^{6}+{B}^{5}G+{B}^{5}R+3\,{B}^{4}{G}^{2}+3\,{B}^{4}GR \\ +3\,{B}^{4}{R}^{2}+3\,{B}^{3}{G}^{3}+6\,{B}^{3}{G}^{2}R \\ +6\,{B}^{3}G{R}^{2}+3\,{B}^{3}{R}^{3}+3\,{B}^{2}{G}^{4} \\ +6\,{B}^{2}{G}^{3}R+11\,{B}^{2}{G}^{2}{R}^{2}+6\,{B}^{2}G{R}^{3} \\ +3\,{B}^{2}{R}^{4}+B{G}^{5}+3\,B{G}^{4}R+6\,B{G}^{3}{R}^{2} \\ +6\,B{G}^{2}{R}^{3}+3\,BG{R}^{4}+B{R}^{5}+{G}^{6}+{G}^{5}R \\ +3\,{G}^{4}{R}^{2}+3\,{G}^{3}{R}^{3}+3\,{G}^{2}{R}^{4} \\ +G{R}^{5}+{R}^{6}.$$
This is where the Maple code may be deployed, using the command
pet_varinto_cind(R+G+B, pet_cycleind_dihedral(6));The reader may want to verify some of these using pen and paper. For example the term $3B^4G^2$ represents the possibilities using four blue beads and two green ones which are: green beads adjacent, green beads with one blue bead and three blue beads separating them and green beads with two blue beads separating them.
$S$ = {necklaces of length 14 with 8 blue, 3 green and 3 brown beads}.
Clearly,$|S| = \frac {14!} {8!3!3!} $.
The group of symmetries, $G = D_{14}$. Clearly, $|G| = 28$. And as you have identified G is acting on S.
And by Burnside lemma, required answer is, $$ \#orbits = \frac 1 {|G|}*\sum_{\sigma \in G}fix(\sigma)$$
1) $\sigma = identity $
Then it fixes any element in $S$. Thus, $fix(\sigma) = |S| = \frac {14!} {8!3!3!}$
2) Rotations, $\sigma$ = rotation by $\frac {360} {14} degree$ clockwise = $p^1$
Carefully consider the cyclic structure of the permutation $\sigma$, $$\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ 2&3&4&5&6&7&8&9&10&11&12&13&14&1 \end{pmatrix}$$ $$\equiv (1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ 14) \ \ \text{[in cycle notation]}$$ If $\sigma$ fixes $x \in S$, then all vertex of the 14-gon must have the same color which is not the case, hence $fix(\sigma)=0$.
Clearly, $fix(\sigma=p^{13})=0$.
3)$\sigma=p^2$ i.e $$\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ 3&4&5&6&7&8&9&10&11&12&13&14&1&2 \end{pmatrix}$$ $$\equiv (1\ 3\ 5\ 7\ 9\ 11\ 13)(2\ 4\ 6\ 8\ 10\ 12\ 14) \ \ \text{[in cycle notation]}$$.
So, $\sigma$ has two cycles of length 7 and if you think carefully, for x to be in $fix(\sigma)$ all vertices in a single cycle will have same bead color. Which is not possible with 8 red, 3 blue and 3 brown beads. So, $fix(\sigma)=0$.
Clearly, $fix(\sigma=p^{12})=0$.
In the same fashion compute the $fix(\sigma)$ for the remaining by looking into the cycle structure and then use the burnside to get the required answer.
Best Answer
There are $\frac{18!}{10!\times 5!\times 3!}$ different ways to arrange the beads in a row.
To see this, start by labelling the beads to make them all different, and now there are $18!$ ways to order the different beads. However, every arrangement of unlabelled beads corresponds to $10!\times 5!\times 3!$ arrangements of the labelled beads (you can rearrange the green labels in $10!$ ways, etc.).
But we want the number of necklaces, not the number of ways to arrange the beads in a row. Now each necklace corresponds to $18$ ways of arranging the beads in a row - break the necklace at any point and start the row there. These $18$ arrangements are always all different (this is not necessarily true for a general necklace problem, but it is here). This is because if two different places, $k$ apart, to break the necklace gave the same arrangement, there would always be another red bead $k$ places after every red bead, and since $5$ and $18$ are coprime this is not possible.
Thus we have to divide the number of arrangements by $18$ to get the number of necklaces, which is therefore $\frac{17!}{10!\times 5!\times 3!}$