Count of bracelets with no adjacent colours the same

Question

I already know how to calculate the amount of bracelets of length $n$ and $k$ colours.

I'd like to add a condition: only count bracelets with no adjacent colours the same.

For context, this is a follow-on to this question.

Answer 1

We use the data from the following MSE link as pointed out in the comments. Now with bracelets we have dihedral symmetry so we need the two cycle indices for the cyclic group and the dihedral group. We have for the former

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$

and the latter

$$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2} & n \text{ odd} \\ \frac{1}{4} \left( a_1^2 a_2^{n/2-1} + a_2^{n/2} \right) & n \text{ even.} \end{cases}$$

Observe that when $n$ odd and $n\ge 3$ the reflections map the two vertices opposite the fixed vertex to each other. Burnside says the coloring must be constant on the pair, but this is not possible in a proper coloring because they are adjacent. Therefore when $n$ is odd we get

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) P_d(k).}$$

The same phenomenon occurs when $n$ is even and the reflection partitions everything into two-cycles. (The coloring must be constant on the two two-cycles that are intersected by the axis of reflection and consist of adjacent beads, which is not possible in a proper coloring.) On the other hand when there are two fixed points we can use any proper coloring connecting them say counterclockwise and reflect its interior points across the axis connecting the fixed points to get the colors on the right side so that the assignment is fixed as required by Burnside. The length of this path is $(n-2)/2+2 = n/2+1$ so we get for $n$ even

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) P_d(k) + \frac{1}{4} k (k-1)^{n/2}.}$$

We can implement this in Maple, as follows.

with(numtheory);

P := (d,k) -> (k-1)^d+(-1)^d*(k-1);

C :=
proc(n, k)
local d;

    1/2/n*add(phi(n/d)*P(d,k), d in divisors(n))
    + `if`(type(n,even), 1/4*k*(k-1)^(n/2), 0);
end;

We get for $n\ge 2$ and three colors the sequence

$$3, 1, 6, 3, 13, 9, 30, 29, 78, 93, 224, 315, \ldots$$

which points us to OEIS A208539, which looks to be a match. Four colors yields

$$6, 4, 21, 24, 92, 156, 498, 1096, 3210, 8052, 22913, 61320,\ldots$$

which points to OEIS A208540, which looks correct as well. The OEIS assumes that a singleton can have $k$ proper colorings while the above formulae produce zero colorings for $n=1$, regarding a singleton cycle having the singleton connected to itself, for no proper colorings.

Remark. Note that the term $\sum_{d|n} \varphi(n/d) (-1)^d$ appearing in the cyclic component

$$P_d(k) = (k-1)^d + (-1)^d\times (k-1)$$

can be simplified as follows. We have $\sum_{d|n} \varphi(d) = n$ so that

$$\sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$

Moreover $\sum_{n\ge 1} (-1)^n/n^s = (2/2^s-1) \zeta(s)$ so that at last

$$L(s) = \sum_{n\ge 1} \frac{1}{n^s} \sum_{d|n} \varphi(n/d) (-1)^d = (2/2^s-1) \zeta(s-1).$$

It follows that for $n$ odd we have $[n^{-s}] L(s) = -n$ and for $n$ even $[n^{-s}] L(s) = 0.$ This gives the closed forms for $n$ odd

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) (k-1)^d - \frac{1}{2} (k-1)}$$

and for $n$ even

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) (k-1)^d + \frac{1}{4} k (k-1)^{n/2}.}$$