q-Polynomial Invariant of Rooted Trees

We know well the Newton binomial formula:

Of course we assume here that the variables commute, that is $ yx=xy$.

We can also visualize formulas for coefficients of $ (x+y)^n$ by considering the tree $ T_{b,a}$ of two long branches of length $ b$ and $ a$ respectively, coming from the root (Fig. 1). We can ask now how many different ways there are to “pluck” the tree $ T_{b,a}$ one leaf at a time. Of course we can tear (like in the child’s play “likes not like”) the left or right branch. In total: the left should be torn $ b$ times and the right $ a$ times so the answer about the number of different pluckings is clearly $ {a+b \choose a}$. Our notes present a dramatic generalization of this example.

We can ask now what happens with the binomial formula if we weaken commutativity by replacing it with $ yx=qxy$ ($ q$ commutes with $ x$ and $ y$). In applications in physics, $ q$ is often taken to be a complex number but it is better to work generally with the ring $ Z[q]$ and q-commutative¹¹By $ q$-commutative we understand exactly $ yx=qxy$. polynomials of variables $ x$ and $ y$ over this ring (we call this ring of polynomials the quantum plane or noncommutative plane). The formula for $ (x+y)^n$ in the quantum plane was known already in the XIX century, but if we do not know the result it is good to first work out small examples: $$(x+y)^2= y^2+ xy +yx + x^2= y^2 + (1+q)xy +x^2,$$ \begin{multline*} (x+y)^3= y^3+ xy^2+ yxy +y^2x + x^2y+ xyx + yx^2 +x^3\\ = y^3 + (1+q+q^2)xy^2 + (1+q+q^2)x^2y+ y^3, \end{multline*} \begin{multline*} (x+y)^4= y^4 + xy^3+ yxy^2 +y^2xy + y^3x + x^2y^2 + xyxy\\ + xy^2x + yx^2y + yxyx + y^2x^2 + x^3y+ x^2yx + xyx^2 + yx^3 + x^4 \\= y^4 + (1+q+q^2+q^3)xy^3 + (1+ q + 2q^2+ q^3 + q^4)x^2y^2 + (1+q+q^2+q^3)x^3y +x^4 \\= y^4+(1+q+q^2+q^3)xy^3 + (1+q^2)(1+q+q^2)x^2y^2+ (1+q+q^2+q^3)x^3y +x^4 .\end{multline*} Observe that we can think of $ 1+q+\cdots+q^{n-1}$ as a $ q$-analogue of the number $ n$. We define formally $ [n]_q=1+q+\cdots+q^{n-1}$. In particular, for $ q=1$, $ [n]_q=n$. In the same vein we define $ q$ factorial of the $ q$-number $ [n]_q$ as: $ [n]_q!=[n]_q[n-1]_q\cdots [2]_q[1]_q$, and $ q$-analogue of the binomial coefficient²²Called also the Gaussian polynomial, $ q$-polynomial of Gauss, Gaussian binomial coefficient, Gaussian coefficient, or $ q$-binomial coefficient. by $ \binom{n}{i}_q = \frac{[n]_q!}{[i]_q! [n-i]_q!}$. Sometimes to stress symmetry, $ i \leftrightarrow n-i$, of the Gaussian polynomial we write $ \binom{n}{i,n-i}_q$. We also observe that the coefficient of $ x^2y^2$ in $ (x+y)^4$ is $ (1+q^2)(1+q+q^2)= \frac{1+q+q^2+q^3}{1+q}(1+q+q^2)=\frac{[4]_q[3]_q}{[2]_q}= \binom{4}{2}_q$.

In the notation we introduced, our calculations can be concisely written as:

Now it is not difficult to guess the general formula for $ (x+y)^n$ in the quantum plane:

$ \square$

We can now go back to the tree $ T_{b,a}$ and play the game in the $ q$-fashion that is the leaf taken from the right ($ a$) branch is counted as $ 1$ but the leaf taken from the left is counted with the weight $ q^a$. Thus we eventually get not the plucking number but the plucking polynomial $ Q(T_{b,a})$ which by definition satisfies the recursive relation $ Q(T_{b,a})= Q(T_{b,a-1}) + q^aQ(T_{b-1,a})$. We also notice that $ Q(T_{0,a})=Q(T_{b,0})=1$, thus we immediately recognize that the plucking polynomial is $ Q(T_{b,a})= \binom{a+b}{a,b}_q$. This is the starting point to our definition of the polynomial of plane rooted trees mentioned in the title of the note.

We can repeat our considerations with many variables, $ x_1,x_2,\ldots,x_k$. If variables commute we get the familiar multinomial formula (e.g. familiar to every student taking multivariable calculus):

where $ {n \choose a_1,\ldots,a_k} = \frac{[n]!}{[a_1]!\ldots[a_k]!}$. As before the pleasant interpretation of $ {n \choose a_1,\ldots,a_k}$ is the number of pluckings of a tree $ T_{a_k,\ldots,a_2,a_1}$ of $ k$ long branches of length $ a_k,\ldots,a_2,a_1$, respectively, as illustrated in Fig. 2.

We can now consider a noncommutative space with $ x_jx_i=qx_ix_j$, for $ i

where $ {n \choose a_1,\ldots,a_k}_q = \frac{[n]_q!}{[a_1]_q!\ldots[a_k]_q!}$. To prove the formula we can again use an induction on $ n$ and again the following two properties are of value:

1. (i)

   $ [a_1+a_2+\cdots+a_k]_q= [a_1]_q + q^{a_1}[a_2]_q + q^{a_1+a_2}[a_2]_q+\cdots+q^{a_1+a_2+\cdots+a_{k-1}}[a_k]_q.$

2. (ii)

   $\displaystyle \begin{eqnarray*} {a_1+a_2+\cdots+a_k \choose a_1,a_2,\ldots,a_k}_q =& {a_1+a_2+\cdots+a_k-1 \choose a_1-1,a_2,\ldots,a_k}_q\\ &+\, q^{a_1}{a_1+a_2+\cdots+a_k-1 \choose a_1,a_2-1,\ldots,a_k}_q\\ &+\cdots + q^{a_1+a_2+\cdots+a_{k-1}} {a_1+a_2+\cdots+a_k-1 \choose a_1,a_2,\ldots,a_k-1}_q. \end{eqnarray*}$

As in the $ q$-binomial case, we can interpret the $ q$-multinomial coefficients by $ q$-plucking the tree $ T_{a_k,\ldots,a_2,a_1}$, that is assuming the following plucking formula

The recursion is the same as for the $ q$-multinomial coefficient so we conclude that

One can find more properties of $ q$-binomial coefficients in [Kac and Cheung2002] and [Mansour and Schork2016]. The quantum plane relation $ yx=qxy$ can be generalized to the $ q$-deformed or quantized Weyl algebra where $ yx-qxy=h$; see Chapter 7 of [Mansour and Schork2016]. The generalization to rooted trees is not clear, or at least it is not unique. Our $ q$-polynomial is motivated by the Kauffman bracket relation in knot theory ([Dabkowski et al.2015]; [Dabkowski and Przytycki2016]). Possibly a connection of $ q$-deformed Weyl algebra to other quantum invariants of knots, developed by [Fenn and Turaev2007], can lead to other $ q$-polynomial invariants of trees. I would encourage readers to look in this direction. In [Asakly et al.2013] the relation of the Weyl algebra to labeled rooted trees is given but I do not see a clear relation with our work.