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.
