A unique question in combinatorics and non-commutative variables.

Question

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

Answer 1

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.

Answer 2

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?