A unique question in combinatorics and non-commutative variables. Let $x,y$ be two variables that satisfy:
$xy=yx+1$ (they are not commutative).
Find $(xy)^2 ,(xy)^3, (yx)^2, (yx)^3$ as a linear  combination in terms of $y^jx^j$.
Then find a formula for $(xy)^n$ and $(yx)^n$.
After some calculations we get:
$(xy)^2=y^2x^2+3yx+1$.
$(xy)^3=y^3x^3+6y^2x^2+7yx+1$.
$(xy)^4=y^4x^4+10y^3x^3+25y^2x^2+15yx+1$.
$(yx)^2=y^2x^2+yx$.
$(yx)^3=y^3x^3+3y^2x^2+y$
Now, given $xy=yx+1$ we can use the binomial formula:
$(xy)^n=\sum_{k=0}^{n} {n \choose k} (yx)^k$.
Denote:
$(yx)^{n}=\sum a_{n,k} y^kx^k$.
Then,
$(yx+1)^n=(yx)(yx)^n=\sum {n\choose k} yxy^kx^k$.
After computing we get,
$(yx)^{n+1}= \sum a_{n,k} (ky^kx^k+y^{k+1}x^{k+1})$.
By comparing the coefficient of $[y^kx^k]$ in $(yx)^{n+1}$:
$a_{n,k}=ka_{n-1,k}+a_{n-1,k-1}$
 A: I found different formulas, namely
\begin{align*}
(xy)^1 & = yx+1 \\
(xy)^2 & = y^2x^2+3yx+1\\
(yx)^3 & = y^3x^3+6y^2x^2+7yx+1\\
(yx)^4 & = y^4x^4+10y^3x^3+25y^2x^2+15yx+1\\
(yx)^5 & = y^5x^5+15y^4x^4+65y^3x^3+90y^2x^2+31yx+1
\end{align*}
if correct, can you guess a general formula?
A: The following is valid for $n\geq 0$:
\begin{align*}
\color{blue}{(xy)^n=\sum_{k=0}^n{n+1\brace k+1}y^kx^k}\tag{1}
\end{align*}
where ${n\brace k}$ are the Stirling numbers of the second kind. We show (1) by deriving the recurrence relation
\begin{align*}
&{n+1\brace k}=k{n\brace k}+{n\brace k-1}\qquad\qquad n, k\geq 1\\
&{0\brace 0}=1,\qquad\quad {n\brace 0}={0\brace n}=0\qquad \ n\geq 1\tag{2}
\end{align*}
for the Stirling numbers of the second kind. We do this in two steps and start with the relation $xy=yx+1$. We get for $k\geq 1$:
\begin{align*}
\color{blue}{xy^k}&=(xy)y^{k-1}\\
&=(yx+1)y^{k-1}=yxy^{k-1}+y^{k-1}\\
&=y(yx+1)y^{k-2}=y^2xy^{k-2}+2y^{k-1}\\
&=y^3xy^{k-3}+3y^{k-1}\\
&=\cdots\\
&\,\,\color{blue}{=y^kx+ky^{k-1}}\tag{3}
\end{align*}
Now we consider
\begin{align*}
(xy)^n=\sum_{k=0}^na_{n,k}y^kx^k\qquad\qquad n\geq 0\tag{4}
\end{align*}
and derive a recurrence relation for $a_{n,k}, n,k\geq 0$ with the help of (3).

We obtain for $n\geq 0$:
\begin{align*}
\color{blue}{\sum_{k=0}^{n+1}a_{n+1,k}y^kx^k}&=(xy)^{n+1}=xy(xy)^n\\
&=xy\sum_{k=0}^na_{n,k}y^kx^k\tag{5}\\
&=\sum_{k=0}^na_{n,k}\left(xy^{k+1}\right)x^k\\
&=\sum_{k=0}^na_{n,k}\left((k+1)y^{k+1}x^k+y^{k+1}x^{k+1}\right)\tag{6}\\
&=\sum_{k=0}^na_{n,k}(k+1)y^kx^k+\sum_{k=1}^{n+1}a_{n,k-1}y^kx^k\tag{7}\\
&\,\,\color{blue}{=\sum_{k=0}^{n+1}\left((k+1)a_{n,k}+a_{n,k-1}\right)y^kx^y}\tag{8}
\end{align*}

Comment:

*

*In (5) we use the representation (4).


*In (6) we apply (3).


*In (7) we split the sum and shift the index of the right-hand sum to also have terms $y^kx^k$.


*In (8) we collect the sums by setting $a_{n,-1}=a_{n,n+1}=0, n\geq 0$.

We obtain from (8) the following recurrence relation for $a_{n,k}, n,k\geq 0$
\begin{align*}
a_{n+1,k}&=(k+1)a_{n,k}+a_{n,k-1}\\
\\
{n+2\brace k+1}&=(k+1){n+1\brace k+1}+{n+1\brace k}
\end{align*}
and since the boundary conditions in (2) can also be shown, the claim (1) follows.

Notes:

*

*We can easily derive from (1) for $n\geq 1$ the identity
\begin{align*}
\color{blue}{(yx)^n}&=y(xy)^{n-1}x\\
&=y\left(\sum_{k=0}^{n-1}{n\brace k+1}y^kx^k\right)x\\
&=\sum_{k=0}^{n-1}{n\brace k+1}y^{k+1}x^{k+1}\\
&\,\,\color{blue}{=\sum_{k=1}^n{n\brace k}y^kx^k}
\end{align*}


*A well-known instantiation of (1) is connected with the product rule of differentiation: $D(fg)=(Df)g+f(Dg)$. Considering the differential operator $(Df)(x)=\frac{d}{dx}f(x)$ and the multiplication operator $X$ with $(Xf)(x)=xf(x)$, we have
\begin{align*}
(xD)^n=\sum_{k=1}^n{n\brace k}x^kD^x
\end{align*}
See also chapter 4 in the referenced paper below.


*A nice paper providing many informations and insights around this theme is Combinatorial models of creation-annihilation by P. Blasiak and P. Flajolet.
