1
$\begingroup$

I have a hard time linking the results from group theory to combinatoric problems.

Below is an example of something I'm stuck on:

Necklaces are manufactured by arranging thirteen white beads and three black beads on a loop of string. How many necklaces can be produced this way?

My notes suggest that this exercise can be solved using the lemma, any help would be appreciated.

This is not homework

$\endgroup$
2
1
$\begingroup$

If the symmetry group is the dihedral group of order $32$, then this is the solution.

Let $D_n$ be the dihedral group of order $2n$. We start with the set $X$ of sequences $$(x_1,x_2,\ldots,x_{15},x_{16})$$ where $x_i\in\{0,1\}$ such that there are exactly $3$ values $i$ such that $x_i=1$ ($0$ represents a white bead and $1$ represents a black bead). Then the group $D_{16}$ acts on $X$ by cyclically rotating the entries and by reflecting the entries of each element of $X$. Namely, if $D_{16}$ is generated by a rotation $r$ and a reflection $s$, then we can define $$r\cdot (x_1,x_2,\ldots,x_{15},x_{16})=(x_2,x_3,\ldots,x_{16},x_1)$$ and $$s\cdot (x_1,x_2,\ldots,x_{15},x_{16})=(x_{16},x_{15},\ldots,x_2,x_1).$$

We want to compute the size of the set $Y$ of orbits of $X$ under $D_{16}$. By Burnside's lemma, $$|Y|=\frac{1}{|D_{16}|}\sum_{g\in D_{16}}|X^g|,$$ where $X^g$ is the set of elements of $X$ stabilized by $g\in D_{16}$.

Note that $D_{16}=\left\{e,r,r^2,\ldots,r^{15},s,rs,r^2s,\ldots,r^{15}s\right\}$, where $e$ is the identity element of $D_{16}$. Observe that $X^{r^k}=\emptyset$ for $k=1,2,\ldots,15$ (this is due to the fact that there are an odd number of $i$ such that $x_i=1$). However, there are reflections that fix some elements of $X$. A reflection of the form $r^ks$ with $k$ odd fixes precisely $2\cdot 7=14$ elements of $X$. This leaves $$|Y|=\frac{1}{|D_{16}|}\left( |X^e|+\sum_{k=0}^7 \left|X^{r^{2k+1}s}\right|\right)=\frac{1}{|D_{16}|}\big(|X|+8\cdot 14\big),$$ so $$|Y|=\frac{1}{32}\left(\binom{16}{3}+112\right)=\frac{560+112}{32}=21.$$

In general, if there are $n$ beads on the bracelet with $c$ colors and the $j$th color has $\ell_j$ beads, then we have the following scenarios.

  • If $n$ is even and every $\ell_j$ is even, then $$|Y|=\tiny\frac{1}{2n}\left(\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}{k},\frac{\ell_2}{k},\ldots,\frac{\ell_c}{k}}+\frac{n}{2}\binom{n/2}{\frac{\ell_1}{2},\frac{\ell_2}{2},\ldots,\frac{\ell_c}{2}}+\frac{n}{2}\sum_{j=1}^c\binom{\frac{n}{2}-1}{\frac{\ell_1}{2},\frac{\ell_2}{2},\ldots,\frac{\ell_{j-1}}{2},\frac{\ell_j}{2}-1,\frac{\ell_{j+1}}{2},\ldots,\frac{\ell_c}{2}}\right).$$
  • If $n$ is even and $\ell_j$ is odd for exactly two $j$, say $j_1$ and $j_2$, then $$|Y|=\tiny\frac{1}{2n}\left(\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}{k},\frac{\ell_2}{k},\ldots,\frac{\ell_c}{k}}+\frac{n}{2}\binom{\frac{n}{2}-1}{\frac{\ell_1}{2},\frac{\ell_2}{2},\ldots,\frac{\ell_{j_1-1}}{2},\frac{\ell_{j_1}-1}{2},\frac{\ell_{j_1+1}}{2},\ldots,\frac{\ell_{j_2-1}}{2},\frac{\ell_{j_2}-1}{2},\frac{\ell_{j_2+1}}{2},\ldots,\frac{\ell_c}{2}}\right).$$
  • If $n$ is even and there are more than two values of $j$ such that $\ell_j$ is odd, then $$|Y|=\frac{1}{2n}\left(\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}{k},\frac{\ell_2}{k},\ldots,\frac{\ell_c}{k}}\right).$$
  • If $n$ is odd and $\ell_j$ is odd for exactly one value of $j$, say $j_0$, then $$|Y|=\small\frac{1}{2n}\left(\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}{k},\frac{\ell_2}{k},\ldots,\frac{\ell_c}{k}}+n\binom{\frac{n-1}{2}}{\frac{\ell_1}{2},\frac{\ell_2}{2},\ldots,\frac{\ell_{j_0-1}}{2},\frac{\ell_{j_0}-1}{2},\frac{\ell_{j_0+1}}{2},\ldots,\frac{\ell_c}{2}}\right).$$
  • If $n$ is odd and there are more than one values of $j$ such that $\ell_j$ is odd, then $$|Y|=\frac{1}{2n}\left(\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}{k},\frac{\ell_2}{k},\ldots,\frac{\ell_c}{k}}\right).$$

If the symmetry group is the cyclic group of order $16$, then this is the solution.

Let $Z_n$ be the cyclic group of order $n$. We start with the set $X$ of sequences $$(x_1,x_2,\ldots,x_{15},x_{16})$$ where $x_i\in\{0,1\}$ such that there are exactly $3$ values $i$ such that $x_i=1$ ($0$ represents a white bead and $1$ represents a black bead). Then the group $Z_{16}$ acts on $X$ by cyclically rotating the elements. Namely, if $Z_{16}$ is generated by $z$, then we can define $$z\cdot (x_1,x_2,\ldots,x_{15},x_{16})=(x_2,x_3,\ldots,x_{16},x_1).$$ We want to compute the size of the set $Y$ of orbits of $X$ under $Z_{16}$. By Burnside's lemma, $$|Y|=\frac{1}{|Z_{16}|}\sum_{g\in Z_{16}}|X^g|,$$ where $X^g$ is the set of elements of $X$ stabilized by $g\in Z_{16}$. Let $O_k=\big\{g\in Z_{16}\big| \text{order of }g\text{ is }k\big\}$. Observe that, if $k\mid 16$ and $k>1$, then $X^g=\emptyset$ for any $g\in O_k$ (this is due to the fact that there are an odd number of $i$ such that $x_i=1$). This leaves $$|Y|=\frac{1}{|Z_{16}|} |X^e|=\frac{1}{|Z_{16}|}|X|=\frac{1}{16}\binom{16}{3}=35,$$ where $e$ is the identity element of $Z_{16}$.

In general, if $\ell$ is the number of $i$ such that $x_i=1$, then for any positive integer $k$ such that $k\mid 16$, $O_k$ is non-empty if and only if $k$ divides $\ell$. Even more generally, if we replace $16$ by a positive integer $n$, then for any positive integer $k$ such that $k\mid n$, $O_k$ is non-empty if and only if $k$ divides $\ell$. We can see that $$|Y|=\frac{1}{n}\sum_{k\mid\gcd(n,\ell)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\ell/k}.$$ If there are $c$ colors such that the $j$th color has $\ell_j$ beads, then $$|Y|=\frac{1}{n}\sum_{k\mid\gcd(n,\ell_1,\ell_2,\ldots,\ell_c)}\phi\left(\frac{n}{k}\right)\binom{n/k}{\frac{\ell_1}k,\frac{\ell_2}k,\ldots,\frac{\ell_c}k}.$$

$\endgroup$
6
  • 3
    $\begingroup$ Are you sure you want the cyclic group $\Bbb Z_{16}$ and not the dihedral group $D_{16}$? $\endgroup$ – Arthur Nov 29 '19 at 9:57
  • 2
    $\begingroup$ I think reflection (i.e. turning over the necklace) should be taken care of too. So you don't have just the cyclic group of potential symmetries, but the dihedral group. $\endgroup$ – Jaap Scherphuis Nov 29 '19 at 9:57
  • 1
    $\begingroup$ Ah, yes. I forgot. I will fix this. $\endgroup$ – Batominovski Nov 29 '19 at 9:57
  • 2
    $\begingroup$ On the other hand, in combinatorics it is apparently now convention to use the term bracelet in that case, and keep the term necklace for the case without reflection symmetry reduction. en.wikipedia.org/wiki/Necklace_(combinatorics) $\endgroup$ – Jaap Scherphuis Nov 29 '19 at 10:05
  • 1
    $\begingroup$ If $(x_1,x_2,\ldots,x_{16})$ is fixed by $r^k$, then show that $x_i=x_j$ whenever $i\equiv j\pmod{d}$, where $d=\gcd(16,k)$ $\endgroup$ – Batominovski Nov 29 '19 at 12:21

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.