# Count how many "free words" of a certain length reduce to the identity

Let $F_n$ be the free group with $n$ generators $g_1,\ldots,g_n$. I'm trying to settle the following:

Question. For a fixed even integer $m$, is there a systematic way to count how many words $w=w_1\ldots w_m$ with $m$ letters chosen among $\{g_1,\ldots,g_n,g_1^{-1},\ldots,g_n^{-1}\}$ will reduce to the identity?

It seems obvious that this will somehow be linked to the Catalan numbers. Indeed, to any word $w$ that reduces to $e$ can be associated a sequence $m$ correctly matched parentheses. Consider for example (with $m=4$) $$w=g_{1}g_{2}^{-1}g_{2}g_{1}^{-1}= (g_{1}(g_{2}^{-1}g_{2})g_{1}^{-1}).$$ Likewise, for any fixed sequence of $m$ correctly matched parentheses, we can find $(2n)^{m/2}$ distinct words that reduce to $e$ associated to the sequence of parentheses, for example (with $m=6$): $$()(())\to(h_1h_1^{-1})(h_2(h_3h_3^{-1})h_2^{-1}),$$ where $h_1,h_2,h_3$ can be chosen freely among $g_1,\ldots,g_n,g_1^{-1},\ldots,g_n^{-1}$, and there obviously is $(2n)^3$ ways of doing this.

Consequently, I initially thought that the answer to my question was $(2n)^{m/2}C_{m/2}$, where $C_p$ denotes the $p^{\text{th}}$ Catalan number. However, I soon noticed that there is some double counting going on in my method. For example, $g_1g_1^{-1}g_1g_1^{-1}$ will be counted by both $()()$ and $(())$, as we can write $$(g_1(g_1^{-1}g_1)g_1^{-1})\text{ and }(g_1g_1^{-1})(g_1g_1^{-1}).$$

Given my lack of experience on how do deal with multiple counting in combinatorial arguments I'm stuck on this question. Any hint or reference to solutions of similar problems would be greatly appreciated.

What you want to know is the coefficient of the neutral element in the term $$(g_1+g_1^{-1}+\cdots+g_n+g_n^{-1})^m$$ in the group ring $\mathbb{Z}F_n$.

Using GAP and this idea, I was able to compute enough values for a search in OEIS.

For $n=2$, it is OEIS-A035610. The series is described there as

Number of walks of length 2n on the 4-regular tree beginning and ending at some fixed vertex.

That is the same because the Cayley graph of $F_2$ is a 4-regular tree.

For the number of returning walks of length $2n\neq0$ we find there $$\frac{4}{n}\sum_{j=0}^{n-1}\binom{2n}{j}(n-j)3^j$$.

They also give generating functions for the numbers of returning walks for all $k$-regular trees (so for a group of rank $n$ set $k=2n$): $$\frac{2(k-1)}{k-2+k\sqrt{(1-4(k-1)x)}}$$

The corresponding series is in OEIS for $k$ up to 10, so for our problem it is there for free groups up to rank 5.

For $n=1$, it is the series of central binomial coefficients $\binom{2n}{n}$, which is OEIS-A000984, which has a lot of additional information.

The remaining cases covered in OEIS are:

According to the documentation for the Haskell function Math.Combinat.FreeGroups.countIdentityWordsFree, the generating function for this is $$Gf_n(u) = \frac{ 2n - 1 }{ n - 1 + n\sqrt{1 - (8n - 4)u^2} } .$$