Enumeration of bead color arrangements

Question

We are to thread $n$ beads of $c$'s colors onto a string. The color arrangement of the beads is such as to be symmetric with respect to the center of the string. Yet the color arrangement of beads on the whole string cannot be comprised of a natural number multiple translating copies of that of the first few beads on the string. More specifically, let the color arrangement of the whole string be $(x_i)_{i=1}^n$. There should be no natural numbers $a$ and $b>1$ such that $n=ab$ and $x_{ak+i}=x_i, \forall\,k\in\{1,2,\cdots,b-1\}, i\in\{1,2,\cdots,a\}$. How many distinct color arrangements are there for the beads?

A succinct way to state this problem is to find the cardinality of the set of sequences $\big\{x:=(x_i)_{i=0}^{n-1}\in\{1,2,\cdots,c\}^n\,\big|\, x_i=x_{n-1-i},\,\forall i\in\{0,1,\cdots,n-1\} \bigwedge T^lx\ne x,\forall l\in\mathbf Z-\{0\} \big\}$ where $(Tx)_i=x_{i+1\mod n}$.

If $n=4p$ where $p$ is a natural number, the answer would be $c^{2p}-c^p$.

Answer 1

If the string color configuration is comprised of the translations of the first $a$ colors, the $a$ colors is also reflectively symmetric about its center. Given a string color configuration, call such first color segment a template and call the smallest length of such template the period of the string color configuration. Let $C(p)$ denote the set of configurations comprised of the first $p$ colors and $D(p)$ the set with period $p$. Obviously $D(p)\subseteq C(p)$.

We will compute the cardinality $|D(p)|$. The period $p=\prod_{i=1}^m p_i^{k_i}$ uniquely where $p_i$'s are distinct prime numbers and $k_i$ are natural numbers.

Lemma: $$D(p)=C(p)-\bigcup_{i=1}^m C\Big(\frac p{p_i}\Big).$$

Proof: $C(p)=D(p)\bigcup_{q|p\atop q\ne p} D(q)$. It is obvious that $D(q)$'s here are all disjoint as no configuration has two distinct periods. For any given $q<p$ and $q|p$, $q\big|\frac p{p_i}$ for some $i$ in the unique prime decomposition of $p$. A configuration with period $q$ has the first $\frac p{p_i}$ color as a template. So $\bigcup_{q|p\atop q\ne p} D(q)\subseteq \bigcup_{i=1}^m C\Big(\frac p{p_i}\Big)$. On the other hand, a configuration with a template of length $\frac p{p_i}$ for some $i$ must have a period that is a proper divisor of $p$. So $\bigcup_{q|p\atop q\ne p} D(q)\supseteq \bigcup_{i=1}^m C\Big(\frac p{p_i}\Big)$. Thus $\bigcup_{q|p\atop q\ne p} D(q)= \bigcup_{i=1}^m C\Big(\frac p{p_i}\Big)$. $\quad$ QED

Let $M=\{1,2,\cdots, m\}$. By the inclusion exclusion principle, \begin{align} s&:=\bigg|\bigcup_{i=1}^m C\Big(\frac p{p_i}\Big)\bigg| \\ &=\sum_{\emptyset\neq J\subseteq M} (-1)^{|J|-1}\bigg|\bigcap_{j\in J} C\Big(\frac p{p_j}\Big)\bigg| \\ &=\sum_{\emptyset\neq J\subseteq M} (-1)^{|J|-1}\bigg|C\Big(\prod_{i\in M-J} p_i^{k_i}\prod_{i\in J}p_i^{k_i-1}\Big)\bigg|. \end{align} The last equality comes from $\displaystyle\bigcap_{j\in J} C\Big(\frac p{p_j}\Big)=C\Big(\frac p{\prod_{j\in J}p_j}\Big)= C\Big(\prod_{i\in N-J} p_i^{k_i}\prod_{i\in J}p_i^{k_i-1}\Big)$. This statement can be easily seen by bearing in mind that $C(p)=\bigcup_{q|p}D(q)$. $|C(p_J)|=c^{\left\lceil \frac{p_J}2\right\rceil}$ where $\displaystyle p_J:=\prod_{i\in N-J} p_i^{k_i}\prod_{i\in J}p_i^{k_i-1}=\frac p{\prod_{j\in J}p_j}$. So we have $$s=\sum_{\emptyset\neq J\subseteq N} (-1)^{|J|-1}c^{\left\lceil \frac{p_J}2\right\rceil}$$ and $$|D(p)|=\sum_{J\subseteq N} (-1)^{|J|}c^{\left\lceil \frac{p_J}2\right\rceil}.$$

Answer 2

Let $z_n$ be the number of possible necklaces of length $n$. The number of symmetric necklaces on $c$ colors is $$ c^{\frac{n+1}{2}} \text{ for odd}\ n \\ c^{\frac{n}{2}} \text{ for even}\ n $$ However, this overcounts $z_n$ since it includes necklaces that have the property described ("comprised a natural number multiple translating copies of that of the first few beads on the string"). The number of symmetric necklaces of length $n$ that have this property is $$ \sum_{\substack{\forall a, \text{ } a<n \\ a|n }}z_a $$ where each $z_a$ is the number of possible necklaces on $a$ beads.

Note that $z_1=c$. Then the number of possible necklaces is $$ z_n=\begin{cases} c^{\frac{n+1}{2}}-\left(\sum_{\substack{\forall a, \text{ } a<n \\ a|n }}z_a\right) \text{ for odd}\ n \\ c^{\frac{n}{2}}-\left(\sum_{\substack{\forall a, \text{ } a<n \\ a|n }}z_a\right) \text{ for even}\ n \end{cases} $$ The first few values of $z_n$ are $$ z_1=c \\ z_2=0 \\ z_3=c^2-c \\ z_4=c^2-c \\ z_5=c^3-c \\ z_6=c^3-c^2 \\ z_7=c^4-c \\ z_8=c^4-c^2 \\ \vdots $$