Count distinct possible words without rotations or reflections

123 Views Asked by At

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
AD - 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
1

There are 1 best solutions below

0
On

After writing some python to find some numbers by brute force, then searching them on OEIS, I've found out that I'm looking at Bracelet numbers, with alphabet size = colours. Which makes sense, since bracelets (AKA turnover necklaces) allow identity under mirroring and rotation.

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

I've written a pure python implementation of this equation and it does match my brute force results for all numbers I've tried.

(See also my follow-up question: Count of bracelets with no adjacent colours the same)