Counting non-repetitive words

Question

Let $S = \{a, b, c, \ldots \}$ be an alphabet, and let $S^N$ be the set of words with letters in $S$ of length $N$ that are not expressible as the repetition of any single word in $\bigcup_{M < N} S^M$.

For example, a, ab and aab are allowed, but aa, aaa and abab are disallowed.

What is $\left|S^N\right|$ in terms of $\left|S\right|$ and $N$?

I'm also interested in a formula for $\sum_{M = 1}^N \left|S^M\right|$.

Answer 1

http://oeis.org/A027375 gives the answer for $S$ of size two, with many links to the literature. http://oeis.org/A143324 gives the number of length $n$ primitive (that is, aperiodic, or period $n$) $k$-ary words ($n\ge1$, $k\ge1$) as $$\sum_{d\mid n}k^d\mu(n/d)$$ where the sum is over all $d$ dividing $n$, and $\mu$ is the Mobius function, which see.

Answer 2

You need to get all divisors of N (excluding N). If $N=30$ you need 1,2,3,5,6,10 and 15.

Then you count all the words of length N and remove all the words of length $d_1, d_2, ...,d_{n_N}$ where $d_i$ are divisors of N with $d_i < N$

$\left|S^{30}\right|=\left|S\right|^{30}-\left|S^1\right|-\left|S^2\right|-\left|S^3\right|-\left|S^5\right|-\left|S^6\right|-\left|S^{10}\right|-\left|S^{15}\right|$

If $N=1$

$\left|S^{1}\right|=\left|S\right|$

If $N>1$

$\left|S^N\right|=\left|S\right|^N-\sum_{M = 1}^{\left|Divisors\,of\,N\right|-1} \left|S^{d_M}\right|$

Some Examples: $N=2$

$\left|S^2\right|=\left|S\right|^2-\left|S^1\right|=\left|S\right|^2-\left|S\right|$

$N=3$

$\left|S^3\right|=\left|S\right|^3-\left|S^1\right|=\left|S\right|^3-\left|S\right|$

$N=4$

$\left|S^4\right|=\left|S\right|^4-\left|S^1\right|-\left|S^2\right|=\left|S\right|^4-\left|S\right|-(\left|S\right|^2-\left|S\right|)=\left|S\right|^4-\left|S\right|^2$

Answer 3

Not an answer, but some references to the main stream (the solution given by Gerry Myerson being correct). As a complement, remark that, if a word is a power (say $w=v^e$ with $e\geq 2$), all its (cyclic) conjugates are such. Your set to be enumerated is then an union of cyclic classes. A cyclic class is called primitive if it contains no power. Once the alphabet has been ordered, the minimal word (for the lexicographic ordring) of each primitive class is a Lyndon word. Have a look there, where one can read

``Lyndon words are named after mathematician Roger Lyndon, who investigated them in 1954, calling them standard lexicographic sequences. Anatoly Shirshov introduced Lyndon words in 1953 calling them regular words''

Your set, for length $N$ enumerates as $N$ times the number of Lyndon words of length $N$ over an alphabet of size $|S|$. Lyndon words are tightly linked with circular codes, questions about free Lie algebras and algebraic bases (Radford).