q-deformations of binomial coefficients of words

Let A be a finite alphabet and A^* be the free monoid of words over A with the concatenation product (in other words, A^* is the set of all finite words over A). Generalizing the usual binomial coefficient of integers, the binomial coefficient of two finite words u and v counts the number of occurrences of v as a (scattered) subword of u. The purpose of this work is to properly define a q-deformation of these coefficients, and to investigate their properties. Recall that a q-analog or q-deformation of some mathematical object is a generalization of this one involving a new parameter q, such that the limit for q -> 1 gives back the original object. For example, there exist q-deformed binomial coefficients of integers, also known as Gaussian binomial coefficients.

Driven by this idea, we define what we call the q-deformation of the binomial coefficient of words recursively, using a Pascal-like formula: for all words u, v in A^* and all letters a, b in A,
\[
\binom{ua}{vb}_q = \binom{u}{vb}_q \cdot q^{|vb|}+\delta_{a,b}\binom{u}{v}_q,
\]
with initial conditions $\binom{u}{\varepsilon}_q=1$ and $\binom{\varepsilon}{v}_q=0$ if $v\neq\varepsilon$. For instance, one can compute the binomial coefficient of abaabba and abb and find q^10+q^9+q^6+q^4+q^3.
We give a combinatorial interpretation of these q-analogs and generalize several classical formulas. We then study a q-deformation of the shuffle and infiltration products of two words. Finally, we consider Eilenberg's theorem characterizing p-group languages in terms of q-deformed binomial coefficients.

This is a joint work with Michel Rigo and Markus A. Whiteland.