Reduced Words of Length $l$

Question

How many reduced words are there of length l the free groups of rank $r$? Moreover I want to know about the number of cyclically reduced words?

I think $r(r-1)^{l-1}$ is the answer for first question, but I am not sure. For second question, I think $r(r-1)^{l-2}(r-2)$. Please advise me

Answer 1

Well, I think you have to replace r by 2r in your formulas taking the inverses into account.

Answer 2

You seem to have the right idea for the number of reduced words, but for a free group of rank $r$, we have $2r$ letters (generators and their inverses) to consider. The first letter can be any, each following must not be the inverse of the previous. Also, the length zero is a special case. So for the number $a_n$ of reduced words of length $n$ we have \begin{align} a_0 & =1 \\ a_n & =2r(2r-1)^{n-1} \quad\text{(for $n\geq 1$)} \end{align}

For the number of cyclically reduced words, your idea seems to be to proceed as before except for the last position, where two letters are not allowed. Indeed, if we want to add a letter at the end of $ab$, we may neither chose $a^{-1}$ nor $b^{-1}$. However, if the word is $aa$ or $aba$, then the only letter to avoid is $a^{-1}$. So even replacing $r$ with $2r$ will not save your formula. Counting the number $b_n$ of cyclically reduced words of length $n$ is more difficult.

I found it easier to first count the number $c_n$ of reduced words of length $n$ that are not cyclically reduced. There are no such words of length below 3. Any such word must be of the form $x^{-1}wx$, where $w$ can be any reduced word. If $w$ is not cyclically reduced, then there is one letter that we must avoid for $x$, if $w$ is cyclically reduced there are two. So we have: \begin{align} b_n & = a_n - c_n \\ c_0 & = c_1 = c_2 = 0 \\ c_n & = (2r-1)c_{n-2} + (2r-2)b_{n-2} \quad\text{(for $n\geq 3$)} \end{align}

This allows us to compute $b_n$. For $r=2$ we get 1, 4, 12, 28, 84, 244, 732, 2188, 6564, ...

Apart from the first term, this is 4 times the series OEIS-A122983 with the recurrance $s_n=3s_{n-1}+s_{n-2}-3s_{n-3}$.

For $r=3$ we get 1, 6, 30, 126, 630, 3126, 15630, ..., which except for the first term is 6 times OEIS-A100284 with the recurrance $s_n=5s_{n-1}+s_{n-2}-5s_{n-3}$.

This leads to a conjecture about $b_n$, and we can indeed derive from our earlier equations that $b_n$ is given by \begin{align} b_0 & = 1, \quad b_1 = 2r, \quad b_2 = 2r(2r-1),\\ b_3 & = (2r-1)^3+1\\ b_n & = (2r-1)b_{n-1}+b_{n-2}-(2r-1)b_{n-3} \quad\text{(for $n\geq 4$)} \end{align}

From this we can get the closed formula $$ b_n = (2r-1)^n + r + (r-1)(-1)^n \quad\text{(for $n\geq 1$)} $$

There is a different derivation for that formula in proposition 17.2 of Avinoam Mann: How Groups Grow.