# coloring with a dihedral group $D_n$ with n prime

I need to find out how many different colorings you can make with 2 colors in a dihedral group $$D_n$$ with $$n$$ prime and $$m$$ black and $$p-m$$ white beads. So first I compute the cycle index: The cycle index of a dihedral group with $$n$$ prime (odd) is equal to: $$Z(D_n) = \frac{1}{2}(\frac{1}{n}a_1^n + \frac{(n-1)}{n}a_n + a_1a_2^\frac{n-1}{2})$$ Now I fill in: $$a_1 = (b+w), a_2 = (b^2 + w^2), a_n = (b^n + w^n)$$ After that, I find the number before the $$b^mw^{p-m}$$ and that is the amount of different colorings with $$m$$ black and $$p-m$$ white beads. But is there a general formule to find that number?

Cycle index.

$$Z(D_p) = \frac{1}{2p} \left(a_1^{p} + (p-1) a_p + p a_1 a_2^{(p-1)/2}\right)$$

We are interested in

$$[B^m W^{p-m}] Z(D_p; B+W).$$

This has three components.

First component.

$$[B^m W^{p-m}] \frac{1}{2p} (B+W)^p = \frac{1}{2p} {p\choose m}.$$

Second component.

$$[B^m W^{p-m}] \frac{p-1}{2p} (B^p+W^p).$$

This is using an Iverson bracket:

$$\frac{p-1}{2p} [[m=0 \lor m=p]].$$

Third component.

$$[B^m W^{p-m}] \frac{1}{2} (B+W) (B^2+W^2)^{(p-1)/2}.$$

Now with $$p$$ prime we cannot have both $$m$$ and $$p-m$$ even, or both odd, so one is odd and the other one even. Supposing that $$m$$ is odd we get

$$[B^{m-1} W^{p-m}] \frac{1}{2} (B^2+W^2)^{(p-1)/2} \\ = [B^{(m-1)/2} W^{(p-m)/2}] \frac{1}{2} (B+W)^{(p-1)/2} = \frac{1}{2} {(p-1)/2 \choose (m-1)/2}.$$

Alternatively, if $$p-m$$ is odd we get

$$[B^{m} W^{p-m-1}] \frac{1}{2} (B^2+W^2)^{(p-1)/2} \\ = [B^{m/2} W^{(p-m-1)/2}] \frac{1}{2} (B+W)^{(p-1)/2} = \frac{1}{2} {(p-1)/2 \choose m/2}.$$

Closed form.

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2p} {p\choose m} + \frac{p-1}{2p} [[m=0 \lor m=p]] + \frac{1}{2} {(p-1)/2 \choose (m-[[m \;\text{odd}]])/2}.}$$

Sanity check.

With a monochrome coloring we should get one as the answer, and we find for $$m=0$$ ($$B^0 W^p = W^p$$)

$$\frac{1}{2p} {p\choose 0} + \frac{p-1}{2p} + \frac{1}{2} {(p-1)/2 \choose 0} = \frac{p}{2p} + \frac{1}{2} = 1.$$

Similarly we get for $$m=p$$ ($$B^p W^0 = B^p$$)

$$\frac{1}{2p} {p\choose p} + \frac{p-1}{2p} + \frac{1}{2} {(p-1)/2 \choose (p-1)/2} = \frac{p}{2p} + \frac{1}{2} = 1.$$

The sanity check goes through. Another sanity check is $$m=1$$ or $$m=p-1$$ which should give one coloring as well. We find

$$\frac{1}{2p} {p\choose 1} + \frac{1}{2} {(p-1)/2\choose 0} = 1$$

and

$$\frac{1}{2p} {p\choose p-1} + \frac{1}{2} {(p-1)/2\choose (p-1)/2} = 1.$$

• Great, thank you. But why do you fill in by the third component $m-1$ and $p-m-1$? Why the $-1$? – Hans Nov 14 '18 at 16:20
• The term in front $(B+W)$ which corresponds to $a_1$ absorbs a power of $B$ or $W$. – Marko Riedel Nov 14 '18 at 16:22