Number of trivializations of a trivial word in the free group

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...

• You should be able to write an ambiguous context-free grammar for the type of trivialization you define and use the Chomsky -Schutzenberger method to get an algebraic generating function Mar 23 '15 at 13:41
• @BenjaminSteinberg Yes, $xYyX$ is a trivialization with $k=1$ (unique for this word) since $yX=\overline{xY}$. Mar 23 '15 at 17:25
• And thank you for the suggestion! I did some googling but cannot find any step-by-step instructions for dummies (I am to be considered one as I only heard about context-free grammars but had no idea that ambiguous ones may be treated purely formally, and having definitely heard of Chomsky and Schützenberger, have never seen their names written together). Could you please suggest some text? Mar 23 '15 at 17:29
• I think Richard Stanley's enumerative combinatorics volume 2 has it. There is also the Sedgwick-Flajolet book on analytic combinatorics. A more technical book is Salomaa's book on formal power series in formal language theory (there is a coauthor but I forget who). Mar 23 '15 at 20:25
• Just to see if I understand correctly: for $t=xyYzZX$, we have $\tau(t)=0$ (although $t\in\mathrm{Ker}(\pi)$), is that correct? for this reason the terminology "trivialization" sounds misleading to me.
– YCor
Apr 25 '15 at 8:08

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}.$$

• Your final result doesn't seem right. The number of trivializable words of length $2N$ equals the number of Palstars (concatenations of palindroms of even length) of length $2N$ with alphabet size $2n$. For $n\in\{1,2\}$, they correspond to OEIS-A246019 and OEIS-A246021. At the beginning of your question, you use $T$ for the set of all words that represent 1. For its number of words of length $2N$, see this MSE question Jul 27 '16 at 8:53
• @ChristianSievers Thank you very much for many very interesting links! Concerning your last observation - note that, as mentioned in the comment by YCor, trivializations in my sense do not hit all words representing 1, they are "trivial trivializations". That comment contains an example: $xyYzZX$ does not have any such "trivial" trivialization. Jul 27 '16 at 9:16
• Yes, I understand that, and my first remark uses "trivializable" in your sense. I only wanted to indicate that you use $T$ in two different ways. Jul 27 '16 at 9:32
• @ChristianSievers I agree that it is confusing. Intention was to have $T$ for all words representing 1 but then many of them would have no "trivial trivializations", and I wanted enumeration of such trivializations only on words which possess them. I mean, I am not so much interested in enumerating words according to numbers of trivializations as enumerating trivializations according to words. Jul 27 '16 at 9:40