# Count distinct possible words without rotations or reflections

Suppose I have an alphabet $${\{A, B, C, D\}}$$ and I want to count all possible words of length $$n$$. Easy: it's $$4^n$$.

What should I do if I want to count all possible words that:

a) are unique given any rotation, and

b) are unique including mirroring

For example:

$$AAAA$$ would definitely be included part of the total (there are no other strings that are rotations or mirrors of it).

Only one of $$BAAA$$ or $$ABAA$$ or $$AABA$$ or $$AAAB$$ would count towards the total (as they're all the same under some rotation).

Only one of $$ABCD$$ or $$CDBA$$ would count towards the total (as they're mirrors of each other).

Only one of $$ABCD$$ or $$ADCB$$ would count towards the total (as you can go between them via a rotation and a mirror).

A small illustration

With the above alphabet and words of length 2, there are 10 possible words:

AA - counted
AB - counted
AC - counted
BA - not counted (a reversal and also rotation of AB)
BB - counted
BC - counted
BD - counted
CA - not counted (a reversal and also rotation of AC)
CB - not counted (a reversal and also rotation of BC)
CC - counted
CD - counted
DA - not counted (a reversal and also rotation of AD)
DB - not counted (a reversal and also rotation of BD)
DC - not counted (a reversal and also rotation of CD)
DD - counted

• Consider the set of ordering of the letter. let $Z/nZ$ act on the set by shifting. We want to count the number of orbit. By Cauchy-Frobinius lemma this is sum of the number of elements fixed by the shifts over n. Then I 'm stuck Apr 19, 2020 at 14:47
• Only 10 words of length 2 as CB == BC. I have not devised a method for counting, but enumeration gives 10, 20, 55 and 136 for lengths 2, 3, 4 and 5. Apr 19, 2020 at 15:32
• Thanks @DanielMathias, fixed my question Apr 19, 2020 at 15:40

To summarise the equation I found at OEIS, for $$k$$ symbols and word length $$n$$, the count is found by:
$$T(n, k) = \frac{k^{\lfloor (n+1)/2 \rfloor} + k^{\lceil (n+1)/2 \rceil}} {4} + \frac{ \sum_{d|n} \phi (d) \cdot k^{n/d} } {2n}$$