4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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

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.