Number of trivializations of a trivial word in the free group

Question

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ sending $X_i$ to $x_i^{-1}$ ($i=1,...n$).

Call a $\textit{trivialization}$ of an element $t\in T$ an equality $$ t=w_1\bar w_1\cdots w_k\bar w_k\ (k\geqslant0) $$ with nonempty $w_i\in M$ where $w\mapsto\bar w$ is the involutive antiautomorphism of $M$ reversing the word and interchanging $x_i\leftrightarrow X_i$ (so $\pi(\bar w)=\pi(w)^{-1}$).

E. g. for $t=(xYyX)^3$, $$ t=xYyXxY\overline{xYyXxY} $$ and $$ t=xY\overline{xY}xYyX\overline{xYyX} $$ are two different trivializations (with $k=1$ and $2$ respectively).

For $t\in T$, let $\tau(t)$ be the number of trivializations of $t$.

I need as much information as possible about the behavior of the function $\tau$ on $T$. Ideally I would like to have a formula (or generating function) for the numbers $\tau_{N,m}$ of words $t\in T$ of length $2N$ with $\tau(t)=m$ (clearly all words in $T$ are of even length). Or at least statistics - how are values of $\tau(t)$ distributed among $t$ of the same (very large) length, this kind of thing. I would also greatly benefit from any kind of (group, monoid) actions on $T$ with explicit description of behavior of $\tau$ under these actions.

I also have vague feeling that this might be formulated homotopy-theoretically (a trivialization being a contracting homotopy of a homotopically trivial loop), maybe somebody has encountered something similar.

It should be relatively easy to give a formula for the cardinality $C_N$ of the subset of $T$ made of words of length $2N$. In fact $T$ is a free submonoid of $M$, freely generated by words having unique trivializations. What may also be useful is that $T$ is also an $M$-submonoid of $M$ (with $M$ acting "by conjugation"). However already all this is not quite trivial, so I expect my question to be rather difficult. Still maybe somebody can point to relevant sources/existing methods to deal with similar problems.

I only managed to find one related question here Probability that a word in the free group becomes (much) shorter? but somehow cannot figure out whether I can use the answers there.

The literature on combinatorics of words is so vast I lost my way in it.

Concerning my motivation for this - well it is a long story but Don Zagier suggested an approach to the problem formulated here in "Special" meanders which can be viewed (among others) in above terms too.

AFTER A DISCUSSION IN COMMENTS - what I need finally is $$ \bar\tau_N:=\sum_{w\textrm{ of length }2N}\tau(w)^2; $$ I did not mention it as I somehow presumed that all $\tau_{N,m}$ are needed for that; but maybe it can be found without knowing them...

Answer 1

Following suggestions of Benjamin Steinberg in comments, I have tried to approach this using context free grammars. Actually after seeing the method I realized this is more or less one of the steps suggested by Don. Anyway, I've got something, but cannot figure out how to extract useful information from it. So this is at best an incomplete answer, I am posting it in hope somebody can tell me what to do next.

The grammar that generates $T$ is fairly easy in fact - the terminal symbols are $x_i$, $\bar x_i$ ($i=1,...,n$) and derivations are \begin{align*} &S\to x_i\bar x_i\mid\bar x_ix_i\mid x_iS\bar x_i\mid\bar x_iSx_i\qquad (i=1,...,n)\\ &T\to1\mid ST \end{align*} (where 1 is the empty word).

This grammar is ambiguous, and in fact it is precisely its ambiguity that I am interested in - that is, for each word I want to know in how many different ways can it be obtained.

Thus viewing $S$ and $T$ as elements of $\mathbb Z[\![M]\!]$, one may (sort of) characterize them by $$ S=\sum_{i=1}^nx_i(1+S)\bar x_i+\bar x_i(1+S)x_i $$ and writing $$ \frac1{1-S}=\sum_{w\in M}\tau(w)w $$ we then have $$ T=\{t\in M\mid\tau(t)\ne0\} $$ and $$ \tau_{N,m}=\#\{w\in M_{2N}\mid\tau(w)=m\} $$ ($M_{2N}$ being the subset of all words of length $2N$).

OK but how to extract anything tangible from this?? Note that $T$ as a language is not inherently ambiguous - denoting by $F$ the free group on $x_1,...,x_n$ let $S_F\subset S$ be the set of words $w\bar w$ for $w\in F\setminus\{1\}$ (which is easy to describe unambiguously). Then viewing again $S_F$ as $\sum_{w\in F\setminus\{1\}}w\bar w\in\mathbb Z[\![M]\!]$, one has $$ \frac1{1-S_F}=\sum_{t\in T}t, $$ i. e. $T$ is a free monoid on $S_F$; so "the whole ambiguity is in redundancies of $S$ over $S_F$". But I don't know how to use it.

The only thing I could compute is the cardinality of $T_{2N}$ but that's not what I want, and I more or less knew how to do it from the beginning. Anyway, let me do at least this - in case already there I am doing something in a wrong way and somebody can point to it.

Observe (if I am right that $T$ is the free monoid on $S_F$ above) $$ \sum_{N\geqslant0}\#(T_{2N})t^N=\sum_{N\geqslant0}\left(\sum_{k>0}\#(F_k)t^k\right)^N=\frac1{1-\sum\limits_{k>0}\#(F_k)t^k}. $$ Now $\#(F_k)$ is $2n(2n-1)^{k-1}$ for $k>0$, so $$ \sum_{k>0}\#(F_k)t^k=\frac{2nt}{1-(2n-1)t} $$ and $$ \sum_{N\geqslant0}\#(T_{2N})t^N=\frac1{1-\frac{2nt}{1-(2n-1)t}}=\frac{1-(2n-1)t}{1-(4n-1)t}, $$ i. e. $$ \#(T_{2N})=(4n-1)^N-(2n-1)(4n-1)^{N-1}=2n(4n-1)^{N-1}. $$