Комбинаторика в свободной группе

[Sonic86]

Пусть $F$ - свободная группа с базисом $S=\{ a,b \}$ (то есть любой элемент в ней является произведением элементов из $S \cup S^-$, причем $aa^{-1}=bb^{-1}=1$)
Найти число слов $T(n)$ длины $2n$ из $F$, в которых сумма степеней показателей по каждому элементу из $S$ равна нулю. (например $aba^{-1}b^{-1}$ - такое слово длины $4$, всего таких слов длины $4$ равно $8$). Найти в любом виде, чем короче и проще - тем лучше. Или оценить сверху и снизу.

Я может чего-то не знаю, но у меня пока просто не получилось

(грубая оценка)

$T(n) \approx 4 \cdot 3^{n-1}$

[maxal]

Ну так методом включений-исключений считается в лоб.

[Sonic86]

maxal, спасибо большое за подсказку. Про метод включений-исключений я как раз забыл. Но применить его у меня не получилось - я уперся в ту же проблему, что и при решении своим способом.
Метод я применял так: считаем число строк длины $2n$ в алфавите $S \cup S^-$ с нулевой суммой показателей для обоих элементов $S$ - это $\binom{2n}{n}^2$. Тогда по формуле включений-исключений $T(n)$ есть $\binom{2n}{n}^2$ минус число строк длины $2n$, содержащих хотя бы одну подстроку $xx^{-1}$ плюс число строк длины $2n$, содержащих хотя бы две подстроки $xx^{-1}$ минус и т.п. Но это число строк различно считается в зависимости от того, объединяются пары $xx^{-1}$ в группки типа $xx^{-1}x$ и т.п. или нет (в общем случае я не вижу, как это число считать) - у меня та же проблема.
Я что-то не вижу? Подскажите, плиз
И если оно там считается, не совсем ясно как асимптотику оценивать у знакочередующейся суммы с сильно прыгающими слагаемыми.

[maxal]

Я тут по случаю добавил формулу и обновил последовательность A007987.
Она отвечает на ваш вопрос?

-- Sat Jun 04, 2011 20:18:39 --

Если вкратце, то включения-исключения дают формулу вида:

$$[x^{2n} y^0 z^0] \sum_{k=0}^{\infty} (-1)^k (Tx + 4x^2 + Tx^3 + 4x^4 + Tx^5 + 4x^6 + \dots)^k,$$

где $T=y+y^{-1}+z+z^{-1}$. Ну а дальше уже дело техники...

[Sonic86]

Ого! Про производящие функции я тоже как-то забыл. Этого мне пока хватит. Спасибо большое!
Пока только один вопрос: $y,z$ - это переменные над $\mathbb{R}$ или $y,z \in F(y,z)$ - элементы свободной группы?

[maxal]

$y,z$ - переменные. В то время как $x^m$ (где $m$ нечетно) соответствует цепочке из чередующихся $a,a^{-1}$ или $b,b^{-1}$ длины $m$, выбор элемента из $T=y+y^{-1}+z+z^{-1}$ определяет "ориентацию" цепочки: либо $aa^{-1}a\dots$, либо $a^{-1}aa^{-1}\dots$, либо $bb^{-1}b\dots$, либо $b^{-1}bb^{-1}\dots$. Соответственно, степень $y$ определяет суммарную степень $a$ в цепочке, а степень $z$ - суммарную степень $b$ в цепочке.