0
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – user614287
    Apr 19, 2020 at 14:47
  • $\begingroup$ 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. $\endgroup$ Apr 19, 2020 at 15:32
  • $\begingroup$ Thanks @DanielMathias, fixed my question $\endgroup$
    – occulus
    Apr 19, 2020 at 15:40

1 Answer 1

0
$\begingroup$

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)

$\endgroup$

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.