TransWikia.com

Burnside's Lemma bracelet with beads in 2 colours (uneven cardinality)

Mathematics Asked by Patrycja on February 12, 2021

How many bracelets can be made with 5 beads in one colour and nine in the other (rotated and flipped bracelets are considered the same).

I’m trying to use Burnside’s Lemma yet I’m little confused. So far I’ve got:

Let $X={text{bracelets of length 14 beads = 5 red + 9 blue}}$, $|X|=frac{14!}{5!9!}=2002$.
Now G in my case is $G=D_{14}$, $|G|=id + text{13 rotations + symmetries(diagonal and perpendicular)}=14+14+14(?)$
Yet I’ve found that $D_{14}$ is order 28. What I’m missing here? Am I counting some actions twice?(I did)

Another step I am not sure is applying Burnside’s Lemma with specified number of beads.

I should count fixed points for each $gin G$.

Identity $g_{r_{14}}$ would is trivial and sends any $v$ back to itself $|fix(g_{r_{14}})|=|X|=2002$

First I can consider rotating bracelet by $frac{360}{14}^circ $ . For given colouring there are none, since permutation induced by $g_{r_{1}}$ maps initial set to one cycle(orbit) that should be in one colour: $r_1 rightarrow (1,2,3,4,5,6,7,8,9,10,11,12,13,14)$ (If we choose one vertex and colour it, we need all of them in the same colour).

Next $g_{r_{2}}$. For given colouring again there are none, since permutation induced by $g_{r_{2}}$ maps initial set to two cycles, both should be monochromatic: $r_2 rightarrow (1,3,5,7,9,11,13)(2,4,6,8,10,12,14)$ The orbits are order 7 and there are only 5 beads in one colour and 9 in the other.
I’ve found that $r_n$ has $gcd(n,14)$ orbits of equal size.

For $r_3$ I’ve found one: $r_3 rightarrow (1,4,7,10,13,2,5,8,11,14,3,6,9,12)$

And $r_4$ I’ve found again 2: $r_4 rightarrow (1,5,9,13,3,7,11)(2,6,10,14,4,8,12)$

Both intuitively cannot result in proper colouring. How to avoid writing all of them?
Can I note that $r_5$,$r_7$,$r_9$,$r_{11}$ and $r_{13}$ are coprime with 14 and do not allow for proper colouring. Same with $r_6$,$r_8$,$r_{10}$ and $r_{12}$, there would be only 2 orbits of even size and thus uncolouruable with given beads.
$r_{7}$ would result in 7 orbits of size 2. Since they should be monochromatic it’s impossible to find colouring.

And what about flips?
Do I correctly assume that 14 $s_d$ flips has 6 orbits of size 2 (vertices on both sizes of symmetry axis) and 2 orbits of size 1 (vertices that are immutable). And another 14 $s_p$ flips has 7 orbits of size 2 each. Eg. $s_d$ along 1-8 axis:
$$s_{d_1} rightarrow (1)(2,14)(3,13)(4,12)(5,11)(6,10)(7,9)(8)$$
Which allows us to make such colouring with fixed vertices being in two colours and assigning the colour to rest of them is possible because now, we have even number of each group of beads. It gives us 2 choices in first step and 15 ways of choosing 2 out of 6 orbits, and for following 4 and the last one is only one option. So $2cdot 15cdot1^5=30$

and $s_{p_{1}}$ on edges $1-2$ and $8-9$:
$$s_{p_1}rightarrow(1,2)(3,13)(4,13)(5,12)(6,11)(7,10)(8,9)$$
And in this case there are non, since all orbits are even.

$$N=frac{1}{left|Gright|}sum_{gin G} left|fix(g)right|$$
here it would be
$frac{1}{28}sum_{gin G} left |fix(g)right|=frac{1}{28}cdot(14cdot 15cdot2+2002) =$ 74 (?)

One Answer

Yet I've found that D14 is order 28. What I'm missing here?

Your count should be $(1+13)+(7+7)$. There are $7$ diagonal and $7$ perpendicular reflections.

Both intuitively cannot result in proper colouring. How to avoid writing all of them? Can I note that [...] Since they should be monochromatic it's impossible to find colouring.

Correct: instead of computing the fixed points for every $g$, you can group the $g$ according to cycle type (or conjugacy class, or by other similarity considerations in other problems) and simply compute the fixed points of one representative of each group.

It gives us 2 choices in first step and 15 ways of choosing 2 out of 6 orbits

Correct, $2cdotbinom{6}{2}=30$ is how many fixed points a diagonal reflection has.

And in this case there are non, since all orbits are even.

Correct, perpendicular reflections have only $2$-cycles so can only have an even number of beads of each color for a fixed bead configuration. (Also keep in mind an orbit of the cyclic subgroup $langle grangle$ is called a cycle so it doesn't get confused with an orbit of the whole group $G$.)

The corrected calculation should then be

$$ frac{1}{28}(2002+7cdot30)=79. $$

Answered by runway44 on February 12, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP