As the title reads I am trying to find a formula for the constant term of the above noncommutative polynomal expression,
$$[1](X+Y+(XY)^{-1})^{3n}\quad \bigg(\in \mathbb{C}\langle X^{\pm 1},Y^{\pm 1} \rangle \bigg)$$
The $3n$ is due to the fact than only these terms are worth looking at because the others are zero anyway. So far I've only been able to extrapolate the first 5 terms via CAS: $$ \begin{array}{|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 \\ \hline \# & 3 & 21 & 183 & 1773 & 18303\\ \hline \end{array} $$
And to give some geometric interpretations to the problem in terms of directed triangles, but this hasn't led me anywhere, yet here is the idea for the $n=1$ case:
$$1=XY(XY)^{-1}=Y(XY)^{-1}X=(XY)^{-1}XY$$
Does someone have an idea on what to try?
Answer summary: The generating function $r(u) = 1 + 3 u + 21 u^2 + 183 u^3 + 1773 u^4 \cdots$ is the unique solution to $$ 4 - 3 r(u)^2 - r(u)^3 + 27 r(u)^3 u=0 \qquad (\ast) $$ with $r(0)=1$. We can use this formula to generate many terms quickly, and to determine the asymptotic behavior of the sequence. To a first approximation, the sequence grows like $n^{-3/2} (27/2)^n$. That this function would be algebraic, and that the sequence would grow like $n^{-3/2} R^n$ follows from very general results of Lalley; our proofs are basically Lalley's techniques, but with a number of ad hoc tricks added in.
ADDED We can also use Lagrange inversion to get the following formulas, which are rapidly computable. You can decide whether or not to call them closed forms. The number you want is $$\frac{1}{n} [q^{n-1}] \left( \frac{27 (1+q)^3}{(3+q)^2} \right)^n$$ and can also be written as $$\sum_{m=0}^{n-1} \frac{(-1)^m 3^{n-m}}{n} \binom{3n}{n-1-m} \binom{2n+m-1}{m}$$
Problem set up: This is really a problem about random walks on groups. We start by cleaning up our notation. Let $\Gamma$ be the free group on generators $X$ and $Y$ and let $Z = (XY)^{-1}$, so $XYZ=ZXY=YZX=1$. For $\gamma_0$ and $\gamma_N$ in $\Gamma$, define a length $N$ path from $\gamma_0$ to $\gamma_N$ to be a sequence $(\gamma_0, \gamma_1, \ldots, \gamma_N)$ such that $\gamma_{i+1} = \gamma_i \cdot ( X, \ Y\ \mbox{or} \ Z)$. So we want to count the number of paths of length $3n$ from $1$ to $1$. We will define a first strike path $\gamma_0 \to \gamma_N$ to be a path for which $\gamma_N \not \in \{ \gamma_0, \gamma_1, \ldots, \gamma_{N-1} \}$.
More generally, for any $\gamma \in \Gamma$, let $G_{\gamma}(t) = \sum_{N=0}^{\infty} \# (\mbox{length $N$ paths}\ 1 \to \gamma ) t^N$. So $r(t^3) = G_1(t)$. We introduce the shorthand $R(t)$ for $G_1(t)$. Let $F_{\gamma}(t)$ be the similar generating function for first strike paths $1 \to \gamma$. For example, $F_X$ starts $t + 2 t^4 + \cdots$, corresponding to the words $X$, $YZXX$ and $ZXYX$. The word $XYZX$, for example, does not contribute to $F_X$, since the corresponding path $(1, X, XY, 1, X)$ strikes $X$ in the second position as well as the final one.
Observe that $G_{\gamma} = F_{\gamma} R$, since any path $1 \to \gamma$ strikes $\gamma$ some first time, and then travels in a closed cycle after that. (cf. Lalley eqn 2.1) By symmetry, $F_X=F_Y=F_Z$. We introduce the shorthand $F_X=S$.
We will say that a word in the alphabet $\{ X, Y, Z \}$ is in reduced form if it contains no substring of the form $XYZ$, $YZX$ or $ZXY$. It is clear that any element of $\Gamma$ can be represented by a reduced word, and I claim that it can be represented by a unique reduced word. (proof omitted). We will need the following lemma:
Lemma: Let $A_1 A_2 \cdots A_N$ be a reduced word with product $\gamma$, so each $A_i$ is one of $(X,Y,Z)$. Then $F_{\gamma} = S^N$ and $G_{\gamma} = S^N R$.
Proof Sketch: We prove the equation for $F_{\gamma}$, the case of $G_{\gamma}$ follows (and can also be proved similarly). We will actually show $F_{\gamma} = F_{A_1} F_{A_2} \cdots F_{A_{N-1}} F_{A_N}$. (cf. Lalley eqn 2.6) This says that every first strike path from $1$ to $\gamma$ is uniquely the concatenation of first strike paths $1 \to A_1$, $A_1 \to A_1 A_2$, $A_1 A_2 \to A_1 A_2 A_3$, etcetera. There is clearly at most one such decomposition: We must take any first strike path $1 \to A_1 A_2 \cdots A_N$ and cut it at the first time each of $A_1$, $A_1 A_2$, \dots appears.
We must prove that there is one such decomposition. In other words, we must show that each of the partial products does occur along the path. To this end, let $(1=w_0, w_1, w_2, \ldots, \gamma=w_N)$ be any path, and look at how the reduced word for $w_j$ changes. At each step, it either grows by one letter or loses its last two letters. In particular, in order to be $A_1 A_2 \cdots A_N$ when we get to the end, we must have seen all prefixes of $A_1 A_2 \cdots A_N$ at some earlier point in the word. $\square$
Generating function manipulations: We first note the following equations: $$ R = 1 + t(G_{YZ} + G_{ZX} + G_{XY}) \qquad F_X = t + t F_{ZXX} + t F_{XYX} . $$ The first equation says that any path $1 \to 1$ is either the zero path, or else is an $X$ followed by a path from $X$ to $XYZ=1$, or is a $Y$ followed by a path from $Y$ to $YXZ=1$, or is a $Z$ followed by a path from $Z$ to $ZXY=1$. The second equation says that any first strike path $1 \to X$ is either the simple path $(1, X)$, or else is a $Y$ followed by a path from $Y$ to $YZXX=X$, or is a $Z$ followed by a path from $Z$ to $ZXYX=X$.
But, by the Lemma, $G_{YZ} = G_{ZX} = G_{XY} = S^2 R$ and $F_{ZXX} = F_{XYX} = S^3$. So we deduce that: $$ R = 1 + 3 t S^2 R \qquad S = t + 2t S^3 .$$
Subtracting $2S$ times the first equation from $3R$ times the second equation, we get $RS = -2 S + 3 R t$ so $S = (3 R t)/(2+R)$. Plugging this into the first equation and clearing denominators gives $-4 + 3 R(t)^2 + R(t)^3 - 27 R(t)^3 t^3$. Note that $R(t)$ is a power series in $t^3$. Putting $u=t^3$, and $R(t) = r(u)$, we get the claimed cubic relation $(\ast)$.
Lagrange Inversion It is convenient to discard the constant term from $r$, so set $r=1+q$. Then we can rewrite $(\ast)$ as $$u=q \frac{(3 + q)^2}{27 (1 + q)^3}.$$ By Lagrange inversion, $$[u^n] q = \frac{1}{n} [q^{n-1}] \left( \frac{27 (1+q)^3}{(3+q)^2} \right)^n$$ as claimed.
We can rewrite this as $$\frac{1}{n} [q^{n-1}] \left( 3^n (1+q)^{3n} (1+q/3)^{-2n} \right)=$$ $$\frac{3^n}{n} [q^{n-1}] \left( \sum_{\ell=0}^{3n} \binom{3n}{\ell} q^{\ell} \right) \left( \sum_{m=0}^{\infty} (-1/3)^m \binom{2n+m-1}{m} q^m \right).$$ We get $q^{n-1}$ terms when $\ell+m = n-1$, which gives the other formula.
With this formula, we can generate more terms almost instantly. Here are the first $20$:
Asymptotics: The cubic equation $(\ast)$ is plotted below. I have drawn vertical lines at $u=1/27$ and $2/27$.
We are following the upper branch through $(u,r) = (0,1)$. The first singularity comes at $(u,r) = (2/27, 2)$, where we collide with a second branch . (This is when we become tangent to the second vertical line.) Therefore, the radius of convergence of $r(u)$ is $2/27$, so the rate of growth of the coefficients of $r(u)$ is roughly $(27/2)^n$. Since there are $27^n$ words of length $3n$, this is saying that the probably that the product is $1$ is roughly $2^{-n}$. More precisely, we have a singularity of square root type. Singularities of type $(x-R)^{\alpha}$ lead to growth of the form $R^{-n} n^{-\alpha-1}$ (for $\alpha$ not a positive integer). So we get the claimed $(27/2)^n n^{-3/2}$ growth rate.
It is fun to think about plugging in $t=1/3$, so $u=1/27$, corresponding to choosing a random walk. When $u=1/27$, equation $(\ast)$ becomes $4=3r(1/27)^2$, so $r(1/27) = \sqrt{4/3} \approx 1.1547$. (This is where we cross the first vertical line). So the expected number of returns to the origin is $1.1547$, including the fact that we start there. From the equation $S = F_X = (3 R t)/(2+R)$, we obtain $F_X(1/3) = R(1/3)/(2+R(1/3)) = \sqrt{4/3}/(2+\sqrt{4/3}) \approx 0.366025$. So the expected number of first strike paths to $X$ is $0.366025$. Since we can only hit $X$ at most once, we obtain that the probability that our random walk hits $X$ is $0.366025$, or slightly more than $1/3$.