#  $q$-Parikh Matrices and $q$-deformed binomial coefficients of words

Antoine Renard  Department of Mathematics, University of Liège, Liège, Belgium
Michel Rigo ORCID 0000-0001-7463-8507 Department of Mathematics, University of
Liège, Liège, Belgium  Markus A. Whiteland Supported by the FNRS Research
grant 1.B.466.21F, ORCID 0000-0002-6006-9902. Department of Mathematics,
University of Liège, Liège, Belgium

###### Abstract

We have introduced a $q$-deformation, i.e., a polynomial in $q$ with natural
coefficients, of the binomial coefficient of two finite words $u$ and $v$
counting the number of occurrences of $v$ as a subword of $u$. In this paper,
we examine the $q$-deformation of Parikh matrices as introduced by Eğecioğlu
in 2004.

Many classical results concerning Parikh matrices generalize to this new
framework: Our first important observation is that the elements of such a
matrix are in fact $q$-deformations of binomial coefficients of words. We also
study their inverses and as an application, we obtain new identities about
$q$-binomials.

For a finite word $z$ and for the sequence $(p_{n})_{n\geq 0}$ of prefixes of
an infinite word, we show that the polynomial sequence
$\binom{p_{n}}{z}_{\\!\\!q}$ converges to a formal series. We present links
with additive number theory and $k$-regular sequences. In the case of a
periodic word $u^{\omega}$, we generalize a result of Salomaa: the sequence
$\binom{u^{n}}{z}_{\\!\\!q}$ satisfies a linear recurrence relation with
polynomial coefficients. Related to the theory of integer partition, we
describe the growth and the zero set of the coefficients of the series
associated with $u^{\omega}$.

Finally, we show that the minors of a $q$-Parikh matrix are polynomials with
natural coefficients and consider a generalization of Cauchy’s inequality. We
also compare $q$-Parikh matrices associated with an arbitrary word with those
associated with a canonical word $12\cdots k$ made of pairwise distinct
symbols.

##  1 Introduction

In a recent paper [22], we have introduced $q$-deformations of binomial
coefficients of words. The $q$-binomial coefficient of two words over a finite
alphabet $A$ is a polynomial of $\operatorname{\mathbb{N}}[q]$ recursively
defined as follows. For all words $u$, $v\in A^{*}$ and letters $a,b\in A$, we
consider a $q$-deformation of Pascal’s identity:

$\binom{u}{\varepsilon}_{\\!\\!q}=1,\quad\binom{\varepsilon}{v}_{\\!\\!q}=0\text{
if }v\neq\varepsilon,\quad\text{and
}\quad\binom{ua}{vb}_{\\!\\!q}=\binom{u}{vb}_{\\!\\!q}\cdot
q^{|vb|}+\delta_{a,b}\binom{u}{v}_{\\!\\!q}.$ (1)

As usual when dealing with $q$-deformations of a combinatorial quantity,
letting $q$ tend to $1$ gives back the classical binomial coefficient
$\binom{u}{v}\in\mathbb{N}$ of the words $u$ and $v$ counting the number of
occurrences of $v$ as a subword of $u$. See, for instance, [17] for a survey.
As an example, for $u=u_{1}\cdots u_{6}=abaaba$ over the alphabet $\\{a,b\\}$,
we have

$\binom{u}{ba}_{\\!\\!q}=q^{6}+q^{5}+q^{3}+1\text{ and }\binom{u}{ba}=4$

because $u_{2}u_{3}=u_{2}u_{4}=u_{2}u_{6}=u_{5}u_{6}=ba$ and there are no
other occurrence of $ba$. It is quite evident that the polynomial
$q^{6}+q^{5}+q^{3}+1$ contains more information about the occurrences of $ba$
in $u$ than its evaluation at $1$, which tells us only about the appearance of
four subwords $ba$. Indeed, for example the constant term $1$ implies that
$ba$ is a suffix of $u$.

###  1.1 Parikh matrices

Let $k$ be the size of the alphabet $A$. For convenience (in particular, for
indexing matrix entries), we identify $A$ with $\\{1,\ldots,k\\}$. When
considering binomial coefficients of words, it is a quite natural question to
look at the so-called Parikh matrices introduced more than twenty years ago by
Mateescu et al. [18]. Associated with a finite word $u\in A^{*}$, it is an
upper triangular matrix $M(u)$ of size $(k+1)\times(k+1)$ whose elements are
binomial coefficients $\binom{u}{v}$ for words $v$ of the form $i\,(i+1)\cdots
j$, $1\leq i\leq j\leq k$. In particular, on the second diagonal
$(M_{i,i+1})$, one finds the $k$ coefficients $\binom{u}{d}$ for the letters
$d$ in the alphabet $A$. So the second diagonal encodes what is called the
Parikh vector or abelianization of $u$.

There is a vast literature on Parikh matrices. See, for instance, [18, 20,
24]. A particular question that has attracted a lot of attention is the
$M$-ambiguity problem or, injectivity problem, that is: characterize words
with the same Parikh matrix [13, 26, 29]. It can be related to the famous
reconstruction problem: does the knowledge of binomial coefficients
$\binom{u}{v}$ for some words $v$ permit to uniquely determine the word $u$?
See, for instance, [12, 23].

Şerbănuţă has generalized Parikh matrices to matrices induced by a word
$z=z_{1}\cdots z_{n}$ [7]. These matrices have size $(|z|+1)\times(|z|+1)$ and
they contain elements of the form $\binom{u}{v}$ for words $v$ of the form
$z_{i}\,z_{i+1}\cdots z_{j}$, $1\leq i\leq j\leq|z|$. Taking $z=12\cdots k$
leads back to the definition given by Mateescu et al.

###  1.2 $q$-Parikh matrices

Having at our disposal our own variation 1 of binomial coefficients of words,
we then wanted to define the corresponding $q$-deformation of Parikh matrices.
Several authors have already tackled this question by immediately considering
a convenient $q$-deformation of Parikh matrices. This approach has led to a
$q$-analogue of the $M$-ambiguity problem. However it was not linked nor aimed
to provide any $q$-analogue to the binomial coefficients of words. See, for
instance, [4, 10]

On the other hand, prior to [10], Eğecioğlu has introduced, for $d\in
A=\\{1,\ldots,k\\}$ and $j\geq 0$, an infinite family of $(k+1)\times(k+1)$
matrices $\mathcal{M}_{d,j}$ with $1$’s on the diagonal and the only other
non-zero element is $q^{j}$ in position $(d,d+1)$ on the second diagonal [9].
Multiplying together these matrices gives what we consider to be the
appropriate way of introducing $q$-deformations of Parikh matrices. For
instance, with $A=\\{1,2,3\\}$, the matrices $\mathcal{M}_{1,j}$,
$\mathcal{M}_{2,j}$ and $\mathcal{M}_{3,j}$ are

${\small\left(\begin{array}[]{cccccc}1&q^{j}&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&1\\\ \end{array}\right)},\
{\small\left(\begin{array}[]{cccccc}1&0&0&0\\\ 0&1&q^{j}&0\\\ 0&0&1&0\\\
0&0&0&1\\\ \end{array}\right)},\
{\small\left(\begin{array}[]{cccccc}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&q^{j}\\\
0&0&0&1\\\ \end{array}\right)}.$ Table 1: Three Eğecioğlu’s matrices for
$A=\\{1,2,3\\}$.

Indeed, with his definition which differs from the one found in [10], the
entries of the upper triangular matrices are $q$-binomial coefficients
$\binom{u}{i\cdots j}_{\\!\\!q}$ up to multiplication by some well-understood
powers of $q$ depending on the position within the matrix, for $1\leq i\leq
j\leq k$. They can therefore be linked to Section 1 and our combinatorial
object of interest.

The present paper is thus the occasion to shed some new light on Eğecioğlu’s
work [9]. We believe that a reason why the latter research work has not been
much explored could be that, with such a definition, the problem of
$M$-ambiguity does not arise. Indeed, Eğecioğlu has already noticed that two
distinct words have different associated matrices: it is an immediate result
on $q$-binomials that the knowledge of $\binom{u}{d}_{\\!\\!q}$ provides the
exact positions of the letter $d$ within $u$ (see Theorem 2.2). Consequently,
such a $q$-deformation does not provide any hint to the classical injectivity
problem of Parikh matrices. Our aim is thus to explore the connections with
our $q$-deformation of binomial coefficients of words.

###  1.3 Our contributions

In Section 2, similarly to Şerbănuţă we extend Eğecioğlu’s definition to
matrices induced by a word $z$. We first use basic linear algebra techniques
to obtain direct analogues of classical results on Parikh matrices: we discuss
the significance of the entries of these matrices and their inverse with
respect to $q$-binomial coefficients of words. Up to a multiplication by a
convenient power of $q$, the elements in the upper part of such a matrix are
of the form $\binom{u}{z_{i}\cdots z_{j}}_{\\!\\!q}$ for $1\leq i\leq
j\leq|z|$.

For results about inverses, we work under the assumption that the fixed word
$z$ has no factor $aa$ made of two identical letters. With Section 2.1 we see
why the inverse has a more intricate form when $z$ does not fulfill this
assumption. We also get that the inverse of a $q$-Parikh matrix associated
with $z$ is directly related (up to some reverse operation and sign
alternation) to the $q$-Parikh matrix associated with the reversal
$\widetilde{z}$.

As an application of our first results on $q$-Parikh matrices and their
inverses, we obtain new relations on those $q$-binomials. For instance, we
obtain identities such as

$\binom{u}{a}_{\\!\\!q}\binom{u}{cb}_{\\!\\!q}+q^{2}\binom{u}{abc}_{\\!\\!q}=\binom{u}{c}_{\\!\\!q}\binom{u}{ab}_{\\!\\!q}+q^{2}\binom{u}{cba}_{\\!\\!q},$

where $u$ is a word and $a,b,c$ are letters such that $a\neq b$ and $b\neq c$.
Section 2.3 generalizes this relation for more than three letters with the
restriction that adjacent letters are distinct.

Section 3 takes a different perspective, this time introducing new objects of
an algebraic nature. It is quite evident that with any left-infinite word
$\mathbf{x}$, if $p_{n}$ is the prefix of length $n$ of $\mathbf{x}$, then the
sequence $n\mapsto\binom{p_{n}}{z}_{\\!\\!q}$ converges to a formal power
series $\mathfrak{s}_{\mathbf{x},z}$ in $\mathbb{N}[[q]]$. If the infinite
word $\mathbf{x}$ is $k$-automatic, then $\mathfrak{s}_{\mathbf{x},z}$ is
shown to be $k$-regular. In particular, our considerations make it possible to
express certain sequences (A133009 from OEIS) encountered in additive number
theory, respectively, on the number of representations of an integer $n$ as
the sum of two _odious_ or _evil_ numbers [2, 6, 8, 11], in the framework of
$q$-binomial coefficients.

Let $u,z$ be finite words. Salomaa has shown that the integer sequence
$n\mapsto\binom{u^{n}}{z}$ satisfies a linear recurrence relation with
constant integer coefficients [25]. For this specific case, it is therefore
natural to ask what more can be said about the sequence of polynomials
$n\mapsto\binom{u^{n}}{z}_{\\!\\!q}$. As a generalization of Salomaa’s result,
we show that it satisfies a linear recurrence relation over
$\operatorname{\mathbb{N}}[q]$.

Finally for a periodic infinite word $\mathbf{u}=\cdots uuu$, we have a
precise description of the growth order of the coefficients of the series
$\mathfrak{s}_{\mathbf{u},z}(q)$. It will be observed by classical arguments
that these coefficients also satisfy a linear recurrence relation with integer
coefficients. We show that $n\mapsto[q^{n}]\mathfrak{s}_{\mathbf{u},z}$
vanishes periodically and those conditions are prescribed by a well understood
arithmetic relation. If it does not vanish then it is in $\Theta(n^{|z|-1})$.
Interestingly, this study also makes connection with the extensively studied
problems of partition of integers into distinct parts [15].

In the last section, with Section 4.2 we express a $q$-Parikh matrix
associated with an arbitrary word $z$ as a $q$-Parikh matrix (of the same
dimension) associated with a canonical word of the form $12\cdots|z|$. To that
end, we introduce a morphism $\sigma_{z}$ encoding the positions of a letter
occurring in $z$. In particular, such a word $12\cdots|z|$ satisfies the
assumption of Theorem 2.3 which permits us to also provide an expression for
the inverse. Then we consider minors of $q$-Parikh matrices. Interestingly,
they are polynomials with non-negative integer coefficients. This is an
alternative explanation of the fact that the inverse of a $q$-deformed Parikh
matrix has entries in $\pm\mathbb{N}[q]$. Finally, we discuss a $q$-analogue
of what Salomaa calls the Cauchy inequality [24]: for all words $x,y,z,w$, the
polynomial

$\binom{xy}{w}_{\\!\\!q}\binom{yz}{w}_{\\!\\!q}-\binom{xyz}{w}_{\\!\\!q}\binom{y}{w}_{\\!\\!q}$

has non-negative integer coefficients.

All these results tend to show that our definition of a $q$-deformation of
Parikh matrices is the right one, since we generalize results from several
different papers [7, 18, 24, 25].

##  2 $q$-deformation of Parikh matrices

We generalize Eğecioğlu’s definition using Şerbănuţă’s approach as described
in the introduction. We get matrices associated with a word $z$ and whose
entries are polynomials in $q$.

Let $z=z_{1}\cdots z_{\ell}$ be a word and $A$ be the alphabet of $z$, i.e.,
the set of letters occurring in $z$. For $d\in A$ and $j\geq 0$, we let
$\mathcal{M}_{d,j}$ denote the upper triangular matrix having $1$’s on the
diagonal and the only non-zero elements above the diagonal are
$(\mathcal{M}_{d,j})_{i,i+1}=q^{j}$ for all $i$ such that $z_{i}=d$. We now
define the map

$\mathcal{P}_{z}:A^{*}\to(\mathbb{N}[q])^{(|z|+1)\times(|z|+1)},\
w_{\ell}w_{\ell-1}\cdots
w_{1}w_{0}\mapsto\mathcal{M}_{w_{\ell},\ell}\cdots\mathcal{M}_{w_{0},0}.$

To avoid cumbersome notation, we do not refer to $z$ when it is clear from the
context. For a word $w$, we say that $\mathcal{P}_{z}(w)$ is the $q$-Parikh
matrix of $w$ induced by $z$.

With $A=\\{1,2,3\\}$, $z=12231$, the matrices $\mathcal{M}_{1,j}$,
$\mathcal{M}_{2,j}$ and $\mathcal{M}_{3,j}$ are

${\small\left(\begin{array}[]{cccccc}1&q^{j}&0&0&0&0\\\ 0&1&0&0&0&0\\\
0&0&1&0&0&0\\\ 0&0&0&1&0&0\\\ 0&0&0&0&1&q^{j}\\\ 0&0&0&0&0&1\\\
\end{array}\right)},\ {\small\left(\begin{array}[]{cccccc}1&0&0&0&0&0\\\
0&1&q^{j}&0&0&0\\\ 0&0&1&q^{j}&0&0\\\ 0&0&0&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&0&1\\\ \end{array}\right)},\
{\small\left(\begin{array}[]{cccccc}1&0&0&0&0&0\\\ 0&1&0&0&0&0\\\
0&0&1&0&0&0\\\ 0&0&0&1&q^{j}&0\\\ 0&0&0&0&1&0\\\ 0&0&0&0&0&1\\\
\end{array}\right)}$

Letting $w=1212312$, we find
$\mathcal{P}_{z}(w)=\mathcal{M}_{1,6}\mathcal{M}_{2,5}\mathcal{M}_{1,4}\mathcal{M}_{2,3}\mathcal{M}_{3,2}\mathcal{M}_{1,1}\mathcal{M}_{2,0}$
as

${\small\left(\begin{array}[]{cccccc}1&q^{6}+q^{4}+q&q^{11}+q^{9}+q^{7}+q^{6}+q^{4}+q&q^{14}+q^{11}+q^{9}+q^{7}&q^{16}&q^{17}\\\
0&1&q^{5}+q^{3}+1&q^{8}+q^{5}+q^{3}&q^{10}&q^{11}\\\
0&0&1&q^{5}+q^{3}+1&q^{7}+q^{5}&q^{8}+q^{6}\\\ 0&0&0&1&q^{2}&q^{3}\\\
0&0&0&0&1&q^{6}+q^{4}+q\\\ 0&0&0&0&0&1\\\ \end{array}\right)}$

The $q$-deformation version of [7, Thm. 13] is given below. For an integer
$r$, we let $\mathsf{s}(r)$ denote the sum of the first $r$ integers, i.e.,
$r(r+1)/2$.

######  Theorem 2.1.

Let $z$ be a word of length $\ell\geq 1$ whose alphabet is $A$. Let $w\in
A^{*}$. The corresponding $(\ell+1)\times(\ell+1)$ $q$-Parikh matrix is such
that

  * •

$(\mathcal{P}_{z}(w))_{i,j}=0$, for all $1\leq j<i\leq\ell+1$,

  * •

$(\mathcal{P}_{z}(w))_{i,i}=1$, for all $1\leq i\leq\ell+1$.

  * •

Let $r\in\\{1,\ldots,\ell\\}$. For all $1\leq i\leq\ell-r+1$,
$(\mathcal{P}_{z}(w))_{i,i+r}=q^{\mathsf{s}(r-1)}\binom{w}{z_{i}\,z_{i+1}\cdots
z_{i+r-1}}_{\\!\\!q}$.

Before proceeding with the proof, we consider an example to illustrate this
statement. The matrix obtained in Section 2 is indeed

${\small\begin{pmatrix}1&\binom{w}{1}_{\\!\\!q}&q\binom{w}{12}_{\\!\\!q}&q^{3}\binom{w}{122}_{\\!\\!q}&q^{6}\binom{w}{1223}_{\\!\\!q}&q^{10}\binom{w}{12231}_{\\!\\!q}\\\
0&1&\binom{w}{2}_{\\!\\!q}&q\binom{w}{22}_{\\!\\!q}&q^{3}\binom{w}{223}_{\\!\\!q}&q^{6}\binom{w}{2231}_{\\!\\!q}\\\
0&0&1&\binom{w}{2}_{\\!\\!q}&q\binom{w}{23}_{\\!\\!q}&q^{3}\binom{w}{231}_{\\!\\!q}\\\
0&0&0&1&\binom{w}{3}_{\\!\\!q}&q\binom{w}{31}_{\\!\\!q}\\\
0&0&0&0&1&\binom{w}{1}_{\\!\\!q}\\\ 0&0&0&0&0&1\\\ \end{pmatrix}}.$

We will often make use of the following combinatorial interpretation of the
$q$-binomials (and in particular in the proof of Theorem 2.1), we recall the
following statement for the sake of completeness.

######  Theorem 2.2 ([22, Thm. 4.1]).

Let $u=u_{n}\cdots u_{1}$ and $v=v_{k}\cdots v_{1}$ be words. Then

$\binom{u}{v}_{\\!\\!q}=\sum_{Y\in
A_{n,k}}q^{{\mathsf{s}}(Y)-\frac{k(k+1)}{2}}$

where $A_{n,k}=\\{n\geq y_{k}>\cdots>y_{1}\geq 1\mid u_{y_{k}}\cdots
u_{y_{1}}=v\\}$ and for all $Y\in A_{n,k}$, ${\mathsf{s}}(Y):=\sum_{y\in Y}y$.

It is often convenient to express the above result as follows. Any specific
occurrence of $v$ as a subword of $u$ contributes to $\binom{u}{v}_{\\!\\!q}$
with a term $q^{\alpha}$ where $\alpha$ is the sum over all letters of $v$ of
the number of letters at the right of them and not being part of that specific
occurrence of the subword $v$. In other words, if $Y=\\{n\geq
y_{k}>\cdots>y_{1}\geq 1\\}\in A_{n,k}$ corresponds to an occurrence of $v$ in
$u$, then $\alpha=\sum_{i=1}^{k}(y_{i}-i)$.

Since the argument will be repeated many times, we give an example. Consider
the word
$u=12\underline{2}1\underline{1}21\underline{2}1=12\underline{2}x\underline{1}y\underline{2}z$
and the subword $v=212$. For the highlighted occurrence of $v$ in $u$, we get
a term $q^{\alpha}$ with $\alpha=|xyz|+|yz|+|z|=|x|+2|y|+3|z|=8$. Indeed, to
the right of the leftmost $2$ of $v$, we see $xyz$ in $u$ (not taking into
account the suffix $12$ of $v$). To the right of $1$ in $v$, we see $yz$.
Finally, to the right of the rightmost $2$ of $v$, we see $z$. Another way of
obtaining the same counting is to notice that $|x|$ will be counted once
because of the prefix $2$ of $v$ to its left. Then $|y|$ will be counted twice
because of the prefix $21$ of $v$ to its left, and finally $|z|$ will be
counted three times because $v$ is entirely to its left.

###### Proof of Theorem 2.1.

Proceed by induction on the length of $w$. The result trivially holds if
$|w|=0,1$. Now assume that the result holds for words of length at most $n$
and consider the word $dw$ of length $n+1$ where $d\in A$ and $|w|=n$. We have
that

$M=\mathcal{P}_{z}(dw)=\mathcal{M}_{d,|w|}\mathcal{P}_{z}(w).$

Let $r\in\\{1,\ldots,\ell\\}$ and $1\leq i\leq\ell-r+1$. If $z_{i}\neq d$,
then $M_{i,i+r}=[\mathcal{P}_{z}(w)]_{i,i+r}$ and we may apply the induction
hypothesis.

Now, if $z_{i}=d$, then

$M_{i,i+r}=[\mathcal{P}_{z}(w)]_{i,i+r}+q^{|w|}[\mathcal{P}_{z}(w)]_{i+1,i+r}.$

By the induction hypothesis, we get

$M_{i,i+r}=q^{\mathsf{s}(r-1)}\binom{w}{z_{i}\,z_{i+1}\cdots
z_{i+r-1}}_{\\!\\!q}+q^{|w|}q^{\mathsf{s}(r-2)}\binom{w}{z_{i+1}\cdots
z_{i+r-1}}_{\\!\\!q}.$

The conclusion follows from the fact that

$\binom{dw}{dz_{i+1}\cdots z_{i+r-1}}_{\\!\\!q}=\binom{w}{dz_{i+1}\cdots
z_{i+r-1}}_{\\!\\!q}+q^{|w|-(r-1)}\binom{w}{z_{i+1}\cdots
z_{i+r-1}}_{\\!\\!q},$

which can be deduced using Theorem 2.2. ∎

We recall the following definition. The _Hadamard product_ of two $m\times p$
matrices $A$ and $B$ is the matrix $A\odot B$ whose elements are defined by

$[A\odot B]_{i,j}=A_{i,j}\cdot B_{i,j},\quad 1\leq i\leq m,1\leq j\leq p.$

Otherwise stated, the Hadamard product of two matrices corresponds to the
element-wise product of these matrices.

Theorem 2.1 permits us to see that $\mathcal{P}_{z}(w)$ can be expressed as
the Hadamard product of two upper triangular matrices, one made of
$q$-binomials $\binom{w}{z_{i}\cdots z_{i+r-1}}_{\\!\\!q}$ and one containing
powers of $q$.

In the context of (classical) Parikh matrices, Mateescu’s original definition
is a special case of Şerbănuţă’s one. The situation is similar in our context.
With the word $z=12\cdots k$ made of all letters of an alphabet, the matrices
$\mathcal{M}_{d,j}$ of Section 2 are the ones introduced by Eğecioğlu [9].
See, for instance, Table 1.

In the special case described in the above remark, we get back to Eğecioğlu’s
considerations. It deserves a particular notation. We let
$\mathcal{E}_{k}:A^{*}\to(\mathbb{N}[q])^{(k+1)\times(k+1)}$ denote the map
$\mathcal{P}_{z}$ when $z=12\cdots k$.

The function $\mathcal{P}_{z}$ is not a morphism from $A^{*}$ to
$\operatorname{\mathbb{N}}[q]^{(|z|+1)\times(|z|+1)}$. For instance,
$\mathcal{P}_{12}(12).\mathcal{P}_{12}(2)\neq\mathcal{P}_{12}(1).\mathcal{P}_{12}(22)$.
But as already observed in [9], for all $z$, $\mathcal{P}_{z}$ is injective:
if $w=w_{\ell}\cdots w_{0}\in A^{*}$ then $\binom{w}{d}_{\\!\\!q}$ has a non-
zero term $q^{j}$ if and only if $w_{j}=d$. So the second diagonal of
$\mathcal{P}_{z}(w)$ completely determines $w$.

###  2.1 Inverse of $q$-Parikh matrices

In the case where $z=12\cdots k$, there is a link between the inverse of a
Parikh matrix of a word $u$ and the Parikh matrix of its reversal
$\widetilde{u}$, see [18, Thm. 3.2]. This relationship still holds for
(classical) Parikh matrices induced by a word $z=z_{1}\cdots z_{\ell}$, where
$z_{i}\neq z_{i+1}$ for all $i\in\\{1,\ldots,\ell-1\\}$, see [7, Thm. 16].

For $q$-Parikh matrices, we obtain a similar result. Note that in the next
statement, $M_{i,j}(1/q)$ means that the polynomial entry $M_{i,j}$ is
evaluated at $1/q$. This is also the reason why we explicitly write a symbol
$\cdot$ limiting the scope of this evaluation. As a special case, note that
the word $z=12\cdots k$ trivially satisfies the assumption of the theorem.

######  Theorem 2.3.

Let $z=z_{1}\cdots z_{\ell}$ be a word whose alphabet is $A$ and such that
$z_{i}\neq z_{i+1}$, for all $1\leq i<\ell$. Let $u\in A^{*}$. Let
$N=(\mathcal{P}_{z}(u))^{-1}$ be the inverse of the $q$-Parikh matrix of $u$
and $M=\mathcal{P}_{z}(\widetilde{u})$ be the $q$-Parikh matrix of the
reversal of $u$,

  * •

$N_{i,j}=0$, for all $1\leq j<i\leq\ell+1$,

  * •

$N_{i,i}=1$, for all $1\leq i\leq\ell+1$.

  * •

With $1\leq i<j\leq\ell+1$, $N_{i,j}=(-1)^{i+j}q^{(j-i)(|u|-1)}\cdot
M_{i,j}\left(\frac{1}{q}\right)$.

###### Proof.

For the sake of readability, we assume that $z=12\cdots k$: we get simpler
notation but the arguments are the same. Moreover, we will highlight where the
assumption on $z$ plays a role.

Proceed by induction on the length of $u$. If $|u|=1$, then $u=d$ for some
$d\in\\{1,\ldots,k\\}$ and $M=\mathcal{P}(\widetilde{u})=\mathcal{M}_{d,0}$,
$N=(\mathcal{M}_{d,0})^{-1}$. Except on the diagonal, the only non-zero
element of $N$ is $N_{d,d+1}=-1$ and the statement holds true.

Assume that the result holds for words of length at most $n$ and consider the
word $dw$ of length $n+1$ where $d\in\\{1,\ldots,k\\}$ and $|w|=n$. We have

$(\mathcal{P}(dw))^{-1}=(\mathcal{M}_{d,|w|}\mathcal{P}(w))^{-1}=(\mathcal{P}(w))^{-1}\mathcal{M}_{d,|w|}^{-1}.$
(2)

Except on the diagonal, the only non-zero element of
$\mathcal{M}_{d,|w|}^{-1}$ is

$\left[\mathcal{M}_{d,|w|}^{-1}\right]_{d,d+1}=-q^{|w|}.$

For an arbitrary word $z$ satisfying the assumption of the statement, a
similar observation holds. For $d\in A$ and $j\geq 0$, the inverse of
$\mathcal{M}_{d,j}$ is an upper triangular matrix with the same structure: It
has $1$’s on the diagonal and the only non-zero elements above the diagonal
are $(\mathcal{M}_{d,j})_{i,i+1}=-q^{j}$ for all $i$ such that $z_{i}=d$. This
follows from the fact that on the second diagonal two non-zero elements are
not consecutive. We discuss the general situation in Section 2.1.

Let $1\leq i<j\leq k+1$. Assume first $j\neq d+1$, then considering the
product 2 and using the induction hypothesis, we get

$[(\mathcal{P}(dw))^{-1}]_{i,j}=[(\mathcal{P}(w))^{-1}]_{i,j}=(-1)^{i+j}q^{(j-i)(|w|-1)}\cdot[\mathcal{P}(\widetilde{w})]_{i,j}\left(\tfrac{1}{q}\right)$

On the other hand, by Theorem 2.1

$[\mathcal{P}(\widetilde{w})]_{i,j}=q^{\mathsf{s}(j-i-1)}\binom{\widetilde{w}}{i\cdots(j-1)}_{\\!\\!q}$

and from the definition of $q$-binomials

$\binom{\widetilde{dw}}{i\cdots(j-1)}_{\\!\\!q}=\binom{\widetilde{w}d}{i\cdots(j-1)}_{\\!\\!q}=q^{j-i}\binom{\widetilde{w}}{i\cdots(j-1)}_{\\!\\!q}+\underbrace{\delta_{d,j-1}}_{=0}\binom{\widetilde{w}}{i\cdots(j-2)}_{\\!\\!q}.$
(3)

Consequently,

$[\mathcal{P}(\widetilde{dw})]_{i,j}=q^{\mathsf{s}(j-i-1)}q^{j-i}\binom{\widetilde{w}}{i\cdots(j-1)}_{\\!\\!q}=q^{j-i}[\mathcal{P}(\widetilde{w})]_{i,j}.$

Hence

$[\mathcal{P}(\widetilde{dw})]_{i,j}\left(\tfrac{1}{q}\right)=\left(\tfrac{1}{q}\right)^{j-i}[\mathcal{P}(\widetilde{w})]_{i,j}\left(\tfrac{1}{q}\right)$

and

$[\mathcal{P}(\widetilde{w})]_{i,j}\left(\tfrac{1}{q}\right)=q^{j-i}\cdot[\mathcal{P}(\widetilde{dw})]_{i,j}\left(\tfrac{1}{q}\right)$

and the conclusion follows.

Now consider the case $j=d+1$, the product 2 provides us with two terms and we
make again use of the induction hypothesis, $[(\mathcal{P}(dw))^{-1}]_{i,j}$
is equal to

$-q^{|w|}(-1)^{i+j-1}q^{(j-1-i)(|w|-1)}\cdot[\mathcal{P}(\widetilde{w})]_{i,j-1}\left(\tfrac{1}{q}\right)+(-1)^{i+j}q^{(j-i)(|w|-1)}\cdot[\mathcal{P}(\widetilde{w})]_{i,j}\left(\tfrac{1}{q}\right).$
(4)

For convenience, we rewrite this as

$[(\mathcal{P}(dw))^{-1}]_{i,j}=(-1)^{i+j}q^{(j-i)(|w|-1)+1}\cdot[\mathcal{P}(\widetilde{w})]_{i,j-1}\left(\tfrac{1}{q}\right)+(-1)^{i+j}q^{(j-i)(|w|-1)}\cdot[\mathcal{P}(\widetilde{w})]_{i,j}\left(\tfrac{1}{q}\right).$

By Theorem 2.1 and several times using the trick that $q^{-k}\cdot
P(1/q)=(q^{k}P)(1/q)$, we get

$\displaystyle[(\mathcal{P}(dw))^{-1}]_{i,j}$
$\displaystyle=(-1)^{i+j}q^{(j-i)(|w|-1)}\cdot\left[q^{\mathsf{s}(j-i-2)}\left(q^{-1}\binom{\widetilde{w}}{i\cdots(j-2)}_{\\!\\!q}+q^{j-i-1}\binom{\widetilde{w}}{i\cdots(j-1)}_{\\!\\!q}\right)\right]\left(\tfrac{1}{q}\right)$
$\displaystyle=(-1)^{i+j}q^{(j-i)(|w|-1)}\cdot\left[q^{\mathsf{s}(j-i-2)}q^{-1}\binom{\widetilde{dw}}{i\cdots(j-1)}_{\\!\\!q}\right]\left(\tfrac{1}{q}\right)$
$\displaystyle=(-1)^{i+j}q^{(j-i)(|\widetilde{dw}|-1)}\cdot\left[q^{\mathsf{s}(j-i-1)}\binom{\widetilde{dw}}{i\cdots(j-1)}_{\\!\\!q}\right]\left(\tfrac{1}{q}\right),$

where on the second line, we use 3. We conclude by Theorem 2.1. ∎

The reader may wonder why the previous result is not extended to matrices
induced by an arbitrary word. The reason is the following one. If $z$ contains
a block of consecutive identical letters $d$, then the inverse of
$\mathcal{M}_{d,j}$ which contains a diagonal block of the form (for instance
with a factor $ddd$)

${\small\left(\begin{array}[]{cccc}1&q^{j}&0&0\\\ 0&1&q^{j}&0\\\
0&0&1&q^{j}\\\ 0&0&0&1\\\ \end{array}\right)}$

has a diagonal block

${\small\left(\begin{array}[]{cccc}1&-q^{j}&q^{2j}&-q^{3j}\\\
0&1&-q^{j}&q^{2j}\\\ 0&0&1&-q^{j}\\\ 0&0&0&1\\\ \end{array}\right)}$

and therefore, the expression corresponding to 4 has more than two terms. If
there are $t$ consecutive identical letters, then a row of the inverse has up
to $t+1$ non-zero entries leading to a sum with $t+1$ terms.

###  2.2 Computing inverse using reversal

For a square matrix $A\in\operatorname{\mathbb{Z}}^{n\times n}$, let
$A^{\angle}$ denote its _antitranspose_ obtained by mirroring the elements
along the antidiagonal; $A^{\angle}_{i,j}=A_{n-j,n-i}$. In the literature on
Parikh matrices, the _antitranspose_ operation on square matrices appears
naturally. Theorem 2.4 is an adaptation of [7, Thm. 17].

For the sake of completeness, we recall a result from [22, Cor. 4.6] which we
will often use. As usual, for a polynomial $P\in\mathbb{C}[q]$ or a formal
power series $P\in\mathbb{C}[[q]]$, we let $[q^{i}]\,P$ denote the coefficient
of the term in $q^{i}$. Let $u,v$ be words. We have, for all
$i\in\\{0,\ldots,|v|(|u|-|v|)\\}$,

$[q^{i}]\binom{u}{v}_{\\!\\!q}=[q^{|v|(|u|-|v|)-i}]\binom{\widetilde{u}}{\widetilde{v}}_{\\!\\!q}.$

Otherwise stated,

$q^{|v|(|u|-|v|)}\cdot\binom{\widetilde{u}}{\widetilde{v}}_{\\!\\!1/q}=\binom{u}{v}_{\\!\\!q}.$

Let $z$ be a word of length $\ell$ and $u$ be a word over the alphabet of $z$.
We have for all $i,j\in\\{1,\ldots,\ell+1\\}$

$[\mathcal{P}_{z}(\widetilde{u})]_{i,j}=q^{(j-i)(|u|-1)}\cdot[\mathcal{P}_{\widetilde{z}}(u)]_{\ell+2-j,\ell+2-i}\left(\tfrac{1}{q}\right).$

###### Proof.

From Section 2.2, for $j\geq i+1$,

$\binom{\widetilde{u}}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}=q^{(j-i)(|u|-j+i)}\cdot\binom{u}{z_{j-1}\cdots
z_{i}}_{\\!\\!1/q}.$

Hence,

$q^{\mathsf{s}(j-i-1)}\binom{\widetilde{u}}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}=q^{(j-i)(|u|-j+i)+2{\mathsf{s}(j-i-1)}}\cdot\left(q^{\mathsf{s}(j-i-1)}\binom{u}{z_{j-1}\cdots
z_{i}}_{\\!\\!q}\right)\left(\tfrac{1}{q}\right).$

Now observe that

$(j-i)(|u|-j+i)+2{\mathsf{s}(j-i-1)}=(j-i)|u|-(j-i)^{2}+2{\mathsf{s}(j-i-1)}$

and $(j-i)^{2}=2{\mathsf{s}(j-i-1)}+j-i$. ∎

As an example, with $z=23112311$ and $z=123$, we have

$\mathcal{P}_{z}(\widetilde{u})={\small\left(\begin{array}[]{cccc}1&q^{7}+q^{6}+q^{3}+q^{2}&q^{11}+q^{10}+q^{7}+q^{6}+q^{3}+q^{2}&q^{12}+q^{11}\\\
0&1&q^{4}+1&q^{5}\\\ 0&0&1&q^{5}+q\\\ 0&0&0&1\\\ \end{array}\right)}$

and

$\mathcal{P}_{\widetilde{z}}(u)={\small\left(\begin{array}[]{cccc}1&q^{6}+q^{2}&q^{9}&q^{10}+q^{9}\\\
0&1&q^{7}+q^{3}&q^{12}+q^{11}+q^{8}+q^{7}+q^{4}+q^{3}\\\
0&0&1&q^{5}+q^{4}+q+1\\\ 0&0&0&1\\\ \end{array}\right)}.$

On the three parallels above the diagonal, the exponent of the convenient
power of $q$ is given by $1.(|u|-1)=7$, $2.(|u|-1)=14$ and $3.(|u|-1)=21$.

######  Theorem 2.4.

Let $z=z_{1}\cdots z_{\ell}$ be a word whose alphabet is $A$ and such that
$z_{i}\neq z_{i+1}$, for all $1\leq i<\ell$. Let $u\in A^{*}$. Let
$N=(\mathcal{P}_{z}(u))^{-1}$ be the inverse of the $q$-Parikh matrix of $u$
and $R=\mathcal{P}_{\widetilde{z}}(u)$ be the $q$-Parikh matrix of $u$ but
associated with the reversal of $z$, for all $1\leq i,j\leq\ell+1$,

$N_{i,j}=(-1)^{i+j}R_{\ell+2-j,\ell+2-i}.$

In other words,
$\mathcal{P}_{z}(u)^{-1}=((-1)^{i+j})_{i,j}\odot\mathcal{P}_{\widetilde{z}}(u)^{\angle}$.

###### Proof.

This follows directly from Theorems 2.3 and 2.2, for $j\geq i+1$,

$N_{i,j}=(-1)^{i+j}q^{(j-i)(|u|-1)}\cdot\left(q^{(j-i)(|u|-1)}\cdot[\mathcal{P}_{\widetilde{z}}(u)]_{\ell+2-j,\ell+2-i}\left(\tfrac{1}{q}\right)\right)\left(\tfrac{1}{q}\right).$

∎

###  2.3 Some consequences and new relations on $q$-binomials

Theorem 2.3 has some interesting consequences. To help the reader to grasp the
idea, we first consider two particular cases with 5 and Section 2.3 before
stating the main result with Section 2.3.

Let $u$ be a word and $a,b$ be two distinct letters. Let $A_{u}$ be the
alphabet of $u$. Take a word $z$ containing the elements of
$A_{u}\cup\\{a,b\\}$ exactly once. Therefore, the assumption of Theorem 2.3 is
satisfied: all letters of $z$ are pairwise distinct. We can moreover assume
that $z$ has $ab$ as prefix. Computing the element
$[\mathcal{P}_{z}(u).\mathcal{P}_{z}(u)^{-1}]_{1,3}=0$, with $i<\ell$, we get
the identity

$q\left[\binom{u}{ab}_{\\!\\!q}+\binom{u}{ba}_{\\!\\!q}\right]=\binom{u}{a}_{\\!\\!q}\binom{u}{b}_{\\!\\!q}$
(5)

because on the first row of $\mathcal{P}_{z}(u)$ the first three non-zero
elements are $1$, $\binom{u}{a}_{\\!\\!q}$, $q\binom{u}{ab}_{\\!\\!q}$ and by
Theorem 2.3 the corresponding three non-zero elements on the third column of
$\mathcal{P}_{z}(u)^{-1}$ are
$q^{2(|u|-1)}\cdot\left[q\binom{\widetilde{u}}{ab}_{\\!\\!q}\right]\left(\frac{1}{q}\right)$,
$-q^{|u|-1}\cdot\binom{\widetilde{u}}{b}_{\\!\\!1/q}$, and $1$, but by Section
2.2,

$q^{|u|-1}\cdot\binom{\widetilde{u}}{b}_{\\!\\!1/q}=\binom{u}{b}_{\\!\\!q}$

and

$q^{2(|u|-2)}\cdot\binom{\widetilde{u}}{ab}_{\\!\\!1/q}=\binom{u}{ba}_{\\!\\!q}.$

So 5 holds true and we have obtained this relation without relying on the
combinatorial interpretation of the coefficients. The second identity is
obtained by considering the element $1,4$ and assuming that $z$ has $abc$ as
prefix. Let $a,b,c$ be letters such that $a\neq b$ and $b\neq c$. We have

$\binom{u}{a}_{\\!\\!q}\binom{u}{cb}_{\\!\\!q}+q^{2}\binom{u}{abc}_{\\!\\!q}=\binom{u}{c}_{\\!\\!q}\binom{u}{ab}_{\\!\\!q}+q^{2}\binom{u}{cba}_{\\!\\!q}.$

More generally, we have the following result. Let $z=z_{1}\cdots z_{n}$ be a
word over $A$ where $z_{i}\neq z_{i+1}$ for all $1\leq i<n$. For all words
$u$, we have

$\sum_{\begin{subarray}{c}z=xy\\\ x,y\in
A^{*}\end{subarray}}(-1)^{|y|}q^{\mathsf{s}(|x|-1)+\mathsf{s}(|y|-1)}\binom{u}{x}_{\\!\\!q}\binom{u}{\widetilde{y}}_{\\!\\!q}=0$

or equivalently,

$\sum_{i=0}^{n}(-1)^{n-i}q^{\mathsf{s}(i-1)+\mathsf{s}(n-i-1)}\binom{u}{z_{1}\cdots
z_{i}}_{\\!\\!q}\binom{u}{z_{n}\cdots z_{i+1}}_{\\!\\!q}=0.$

###### Proof.

If $u$ contains some letters $d_{1}$, …, $d_{s}$ not appearing in $z$, instead
of $z$ we consider $z^{\prime}=zd_{1}\cdots d_{s}$ (otherwise, we set
$z^{\prime}=z$). Since we append new letters to $z$, this word $z^{\prime}$
still satisfies the assumption of Theorem 2.3.

The result comes directly from the computation of the element
$[\mathcal{P}_{z^{\prime}}(u).\mathcal{P}_{z^{\prime}}(u)^{-1}]_{1,n+1}=0$.
Indeed, carrying out the matrix product and using Theorem 2.1 and Theorem 2.3,
since $[\mathcal{P}_{z^{\prime}}(u)^{-1}]_{i,n+1}=0$ whenever $i>n+1$, we get

$\displaystyle[\mathcal{P}_{z^{\prime}}(u).\mathcal{P}_{z^{\prime}}(u)^{-1}]_{1,n+1}$
$\displaystyle=\sum_{i=1}^{n+1}[\mathcal{P}_{z^{\prime}}(u)]_{1,i}\cdot[\mathcal{P}_{z^{\prime}}(u)^{-1}]_{i,n+1}$
$\displaystyle=[\mathcal{P}_{z^{\prime}}(u)^{-1}]_{1,n+1}+\sum_{i=2}^{n}[\mathcal{P}_{z^{\prime}}(u)]_{1,i}\cdot[\mathcal{P}_{z^{\prime}}(u)^{-1}]_{i,n+1}+[\mathcal{P}_{z^{\prime}}(u)]_{1,n+1}$
$\displaystyle=(-1)^{n}q^{n(|u|-1)}[\mathcal{P}_{z^{\prime}}(\widetilde{u})]_{1,n+1}\left(\tfrac{1}{q}\right)$
$\displaystyle\qquad+\sum_{i=2}^{n}q^{\mathsf{s}(i-2)}\binom{u}{z_{1}\cdots
z_{i-1}}_{\\!\\!q}\cdot(-1)^{i+n+1}q^{(n+1-i)(|u|-1)}\cdot[\mathcal{P}_{z^{\prime}}(\widetilde{u})]_{i,n+1}\left(\tfrac{1}{q}\right)$
$\displaystyle\qquad\qquad+q^{\mathsf{s}(n)}\binom{u}{z_{1}\cdots
z_{n}}_{\\!\\!q}.$

Let us focus on one particular term of the sum. For all
$i\in\\{1,\ldots,n\\}$, we have

$\displaystyle
q^{(n+1-i)(|u|-1)}\cdot[\mathcal{P}_{z^{\prime}}(\widetilde{u})]_{i,n+1}\left(\tfrac{1}{q}\right)$
$\displaystyle=q^{(n+1-i)(|u|-1)}\cdot\left(q^{\mathsf{s}(n-i)}\binom{\widetilde{u}}{z_{i}\cdots
z_{n}}_{\\!\\!q}\right)\left(\tfrac{1}{q}\right)$
$\displaystyle=q^{-\mathsf{s}(n-i)}q^{(n+1-i)(|u|-1)}\cdot\binom{\widetilde{u}}{z_{i}\cdots
z_{n}}_{\\!\\!1/q}$
$\displaystyle=q^{-\mathsf{s}(n-i)}q^{(n-i)(n+1-i)}q^{(n+1-i)(|u|-(n+1-i))}\cdot\binom{\widetilde{u}}{z_{i}\cdots
z_{n}}_{\\!\\!1/q}$
$\displaystyle=q^{-\mathsf{s}(n-i)}q^{(n-i)(n+1-i)}\binom{u}{z_{n}\,z_{n-1}\cdots
z_{i}}_{\\!\\!q}$
$\displaystyle=q^{\mathsf{s}(n-i)}\binom{u}{z_{n}\,z_{n-1}\cdots
z_{i}}_{\\!\\!q},$

where the second to last equality comes from Section 2.2. Hence,

$\displaystyle[\mathcal{P}_{z^{\prime}}(u).\mathcal{P}_{z^{\prime}}(u)^{-1}]_{1,n+1}$
$\displaystyle=(-1)^{n}q^{\mathsf{s}(n-1)}\binom{u}{z_{n}\,z_{n-1}\cdots
z_{1}}_{\\!\\!q}$
$\displaystyle\qquad+\sum_{i=2}^{n}(-1)^{i+n+1}q^{\mathsf{s}(i-2)}\binom{u}{z_{1}\cdots
z_{i-1}}_{\\!\\!q}q^{\mathsf{s}(n-i)}\binom{u}{z_{n}\,z_{n-1}\cdots
z_{i}}_{\\!\\!q}$
$\displaystyle\qquad\qquad+q^{\mathsf{s}(n)}\binom{u}{z_{1}\cdots
z_{n}}_{\\!\\!q}.$

For a given factorization $z=xy$, let us denote $x=z_{1}\cdots z_{i-1}$ and
$y=z_{i}\cdots z_{n}$, and notice that

$n+1+i=|z|+1+|x|-1=|z|+|x|=2|z|-|y|,$

so that $(-1)^{i+n+1}=(-1)^{|y|}$. We can finally rewrite the above sum as

$[\mathcal{P}_{z^{\prime}}(u).\mathcal{P}_{z^{\prime}}(u)^{-1}]_{1,n+1}=\sum_{\begin{subarray}{c}z=xy\\\
x,y\in
A^{*}\end{subarray}}(-1)^{|y|}q^{\mathsf{s}(|x|-1)+\mathsf{s}(|y|-1)}\binom{u}{x}_{\\!\\!q}\binom{u}{\widetilde{y}}_{\\!\\!q}.$

∎

##  3 Convergence to a formal power series

We first observe that with any left-infinite word $\mathbf{x}=\cdots
x_{2}x_{1}x_{0}$, if $p_{n}=x_{n-1}\cdots x_{0}$ is the prefix of length $n$
of this word, then the polynomial sequence
$n\mapsto\binom{p_{n}}{z}_{\\!\\!q}$ converges to a formal power series
$\mathfrak{s}_{\mathbf{x},z}$. If the infinite word is moreover $k$-automatic,
then by classical arguments the limit series is shown to be $k$-regular.

To make a connection with what is known in the classical setting, Salomaa has
shown that the integer sequence $n\mapsto\binom{u^{n}}{z}$ satisfies a linear
recurrence relation [25]. It is therefore natural to ask what more can be said
about the sequence of polynomials $n\mapsto\binom{u^{n}}{z}_{\\!\\!q}$. As a
generalization of Salomaa’s result, we show that it satisfies a linear
recurrence with polynomial coefficients. Finally for a periodic infinite word
$\mathbf{u}=\cdots uuu$, we have a precise description of the growth order of
the coefficients of the series $\mathfrak{s}_{\mathbf{u},z}$.

###  3.1 Convergence and automaticity

Due to Section 1 and relation 1 where the focus is on the rightmost letter, it
is more convenient to consider a left-infinite word $\cdots x_{n}x_{n-1}\cdots
x_{0}=\mathbf{x}$. We say that $x_{t-1}\cdots x_{0}$ is the prefix of length
$t$ of $\mathbf{x}$.

Let $\cdots x_{n}x_{n-1}\cdots x_{0}=\mathbf{x}$ be a left-infinite word and
$z$ be a finite word. For all $r\geq 0$, there exists $N$ such that the
coefficient of $q^{r}$ in the $q$-binomials $\binom{x_{n}\cdots
x_{0}}{z}_{\\!\\!q}$ is the same for all $n\geq N$. Otherwise stated, the
sequence $\left([q^{r}]\binom{x_{n}\cdots x_{0}}{z}_{\\!\\!q}\right)_{n\geq
0}$ is eventually constant.

###### Proof.

If $z$ occurs as a subword of some prefix of length $N$ of $\mathbf{x}$, then
it will occur within all longer prefixes of $\mathbf{x}$. Let $n\geq N-1$.
Take a specific occurrence of $z=z_{1}\cdots z_{\ell}$ such that

$x_{n}\cdots x_{0}=z_{1}y_{1}z_{2}y_{2}\cdots z_{\ell}y_{\ell},$

where $y_{1}$, …, $y_{\ell}\in A^{*}$. By Theorem 2.2 it provides
$\binom{x_{n}\cdots x_{0}}{z}_{\\!\\!q}$ with some monomial $q^{r}$ where

$r=\sum_{i=1}^{\ell}i\,|y_{i}|\geq|y_{1}\cdots y_{\ell}|=n+1-|z|.$

Roughly speaking, the further to the left occurs the first letter of $z$
(i.e., the larger $n$ is such that $x_{n}=z_{1}$), the larger the
corresponding exponent is.

Instead of focusing on a specific occurrence of $z$, let us focus on a
specific exponent of the $q$-binomial. From the above discussion, for each
given $r$ and for large enough $n$, the coefficient of $q^{r}$ in
$\binom{x_{n}\cdots x_{0}}{z}_{\\!\\!q}$ is completely determined by a suffix
of $\mathbf{x}$ whose length is bounded by $r+|z|$. Hence, for all $n\geq
r+|z|-1$, the polynomials $\binom{x_{n}\cdots x_{0}}{z}_{\\!\\!q}$ have the
same coefficient for $q^{r}$. ∎

This result legitimates the next definition.

Let $\mathbf{x}$ be a left-infinite word and $z$ be a finite word. For all
$r\geq 0$, we let $c_{r}$ denote the coefficient of $q^{r}$ in the
$q$-binomials $\binom{x_{n}\cdots x_{0}}{z}_{\\!\\!q}$ for all $n\geq
r+|z|-1$. We let $\mathfrak{s}_{\mathbf{x},z}$ denote the formal series
defined by $\sum_{r\geq 0}c_{r}\,q^{r}$.

As an example, consider the (left) Thue–Morse sequence $\cdots
110010110=\mathbf{t}$ and the word $z=00$. We obtain the (right-infinite)
sequence of coefficients whose first terms are

$00101101211211412313324323525505635534844655764765957847\cdots$

i.e.,

$\mathfrak{s}_{\mathbf{t},00}=q^{2}+q^{4}+q^{5}+q^{7}+2q^{8}+q^{9}+\cdots$

For instance, this means that, for large enough $n$, in every $q$-binomial
$\binom{t_{n}\cdots t_{0}}{00}_{\\!\\!q}$ the monomial of least degree with a
non-zero coefficient is $q^{2}$. This is (up to a shift) the sequence A133009
from OEIS counting the number $c(n)$ of pairs $(x,y)$ of integers such as
their base-$2$ expansions contain an odd number of ones (the Thue–Morse word
is the characteristic sequence of the set of integers with this property),
$x<y$ and $x+y=n$. For instance, $c(3)=1$ because there is only one pair
$(1,2)$ such that $1+2=3$. This sequence was introduced in [11] and the
connection with automatic sequences was studied in [2].

We assume the reader familiar with $k$-automatic and $k$-regular sequences [1,
27]. For instance, the Thue–Morse sequence is $2$-automatic. When the infinite
word considered in Section 3.1 is $k$-automatic, we obtain a $k$-regular
sequence of coefficients.

Let $\cdots x_{2}x_{1}x_{0}=\mathbf{x}$ be a (left-infinite) $k$-automatic
sequence over an alphabet $A$ and $z$ be a word. The sequence of coefficients
of the series $\mathfrak{s}_{\mathbf{x},z}$ is $k$-regular.

###### Proof.

Since $\mathbf{x}$ is $k$-automatic, for all $a\in A$, there is a first-order
formula $\varphi_{a}(i)$ in $\langle\mathbb{N},+,V_{k}\rangle$ which holds
true if and only if $x_{i}=a$. Let $z=z_{\ell}\cdots z_{1}$. The next formula
permits to detect occurrences of $z$ as a subword of $\mathbf{x}$:

$\Psi_{z}(i_{\ell},\ldots,i_{1})\equiv
i_{\ell}>\cdots>i_{1}\wedge\varphi_{z_{\ell}}(i_{\ell})\wedge\cdots\wedge\varphi_{z_{1}}(i_{1})$

Since $z$ is given, note that $\mathsf{s}(\ell-1)$ is a constant. For all
$n\geq 0$, the set

$T_{n}:=\\{(i_{\ell},\ldots,i_{1})\mid\Psi_{z}(i_{\ell},\ldots,i_{1})\wedge
n=i_{\ell}+\cdots+i_{1}-\mathsf{s}(\ell-1)\\}$

is definable in $\langle\mathbb{N},+,V_{k}\rangle$. By Theorem 2.2 the number
of $\ell$-tuples in $T_{n}$ gives the coefficient of $q^{n}$ in the series

$\\#T_{n}=[q^{n}]\mathfrak{s}_{\mathbf{x},z}.$

By classical enumeration arguments about $k$-automatic formulas (for a proof,
see [5] ; for details, see [27, Chap. 9] or [2, Sec. 2]), the sequence
$n\mapsto\\#T_{n}$ is $k$-regular. ∎

[[27, Thm. 9.7.1]] Let $\mathbf{x}$ be a (left-infinite) $k$-automatic
sequence and $z$ be a word. There exists a real number $\alpha>0$ such that
$[q^{n}]\mathfrak{s}_{\mathbf{x},z}$ is in $\mathcal{O}(n^{\alpha})$.

###  3.2 A fine analysis of the periodic case

Let $u,z$ be finite non-empty words. The left-infinite periodic word
$\mathbf{u}=\cdots uuu$ is $k$-automatic for all $k\geq 2$, hence the series
$\mathfrak{s}_{\mathbf{u},z}$ is $k$-regular for all $k\geq 2$. A
generalization of Cobham’s theorem implies that the sequence of coefficients
of $\mathfrak{s}_{\mathbf{u},z}$ satisfies a linear recurrence relation [3].

Our aim in this section is to get a precise description of the polynomial
$\binom{u^{n}}{z}_{\\!\\!q}$ not reducing ourselves to the limit case given by
$\mathfrak{s}_{\mathbf{u},z}$. From this, we obtain a generalization of
Salomaa’s result with Section 3.2: The sequence of $q$-binomials
$(\binom{u^{n}}{z}_{\\!\\!q})_{n\geq 0}$ satisfies a linear recurrence
relation over $\mathbb{Z}[q]$. In particular, our developments are here
independent of the general theory of automatic and regular sequences.

Given two words $u,z$ where $u$ is over the alphabet $A$ of $z$ and a non-
negative integer $k$, let us define the square matrix Pow${}_{z}(k)$ of
dimension $|z|+1$ as follows:

$[\operatorname{Pow}_{z}(k)]_{i,j}=\begin{cases}0&\text{if }i>j\\\ 1&\text{if
}i=j\\\ q^{(j-i)k}&\text{if }i<j,\\\ \end{cases}\quad\text{ i.e.,
}\quad\operatorname{Pow}_{z}(k)={\small\begin{pmatrix}1&q^{k}&q^{2k}&\cdots&q^{|z|k}\\\
0&1&q^{k}&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\ddots&q^{2k}\\\
\vdots&&\ddots&1&q^{k}\\\ 0&\cdots&\cdots&0&1\\\ \end{pmatrix}}.$

Finally, we let $H_{z,k}(u)$ denote the Hadamard product
$\mathcal{P}_{z}(u)\odot\operatorname{Pow}_{z}(k)$.

The following result allows us to express the Parikh matrix of $u^{n}$ induced
by $z$ using the matrices $H_{z,k}(u)$ we just defined. Let
$k\in\operatorname{\mathbb{N}}$, and let us write $u=u_{\ell}\cdots u_{0}$
with $u_{i}\in A$ for all $i\in\\{0,\ldots,\ell\\}$. We have

$H_{z,k}(u)=\mathcal{M}_{u_{\ell},k+\ell}\cdot\mathcal{M}_{u_{\ell-1},k+\ell-1}\cdots\mathcal{M}_{u_{1},k+1}\cdot\mathcal{M}_{u_{0},k}.$

###### Proof.

We proceed by induction on $|u|\geq 1$. If $|u|=1$, then $u=a\in A$ and, using
the definition of the Parikh matrix $\mathcal{P}_{z}(a)$, we have

$\displaystyle H_{z,k}(a)$
$\displaystyle=\mathcal{P}_{z}(a)\odot\operatorname{Pow}_{z}(k)=\mathcal{M}_{a,0}\odot\operatorname{Pow}_{z}(k)=\mathcal{M}_{a,k}.$

Let us now assume that the result is true for all words $u$ of length
$\ell\geq 1$, and show that it still holds for a word $w=w_{\ell}\cdots w_{0}$
of length $\ell+1$. If $|w|=\ell+1$, then there exist $u\in A^{*}$ and $a\in
A$ such that $|u|=\ell$ and $w=au=au_{\ell-1}\cdots u_{0}$. By induction
hypothesis,

$\displaystyle\mathcal{M}_{w_{\ell},k+\ell}\cdot\mathcal{M}_{w_{\ell-1},k+\ell-1}\cdots\mathcal{M}_{w_{0},k}$
$\displaystyle=\mathcal{M}_{a,k+\ell}\cdot\mathcal{M}_{u_{\ell-1},k+\ell-1}\cdots\mathcal{M}_{u_{0},k}$
$\displaystyle=\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u).$

We thus have to show that $\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u)=H_{z,k}(w)$.
By definition,

$[\mathcal{M}_{a,k+\ell}]_{i,j}=\begin{cases}1,&\text{if }i=j;\\\
q^{k+\ell},&\text{if }i+1=j\text{ and }z_{i}=a;\\\
0,&\text{otherwise};\end{cases}$

and

$[H_{z,k}(u)]_{i,j}=\begin{cases}0,&\text{if }i>j;\\\ 1,&\text{if }i=j;\\\
q^{(j-i)k+\mathsf{s}(j-i-1)}\binom{u}{z_{i}\cdots z_{j-1}}_{\\!\\!q},&\text{if
}i<j.\end{cases}$

It is clear that $[\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u)]_{i,j}=\delta_{i,j}$
for every pair $(i,j)$ such that $1\leq j\leq i\leq|z|+1$. Now assume that
$i<j$, and let us consider two cases. If $z_{i}\neq a$, then

$\displaystyle[\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u)]_{i,j}$
$\displaystyle=q^{(j-i)k+\mathsf{s}(j-i-1)}\binom{u}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}$
$\displaystyle=q^{(j-i)k+\mathsf{s}(j-i-1)}\binom{au}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}$ $\displaystyle=[H_{z,k}(w)]_{i,j},$

and if $z_{i}=a$, then

$\displaystyle[\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u)]_{i,j}$
$\displaystyle=q^{(j-i)k+\mathsf{s}(j-i-1)}\binom{u}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}+q^{k+\ell}q^{(j-i-1)k+\mathsf{s}(j-i-2)}\binom{u}{z_{i+1}\cdots
z_{j-1}}_{\\!\\!q}$
$\displaystyle=q^{(j-i)k+\mathsf{s}(j-i-1)}\left(\binom{u}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}+q^{\ell-(j-i-1)}\binom{u}{z_{i+1}\cdots
z_{j-1}}_{\\!\\!q}\right)$
$\displaystyle=q^{(j-i)k+\mathsf{s}(j-i-1)}\binom{w}{z_{i}\cdots
z_{j-1}}_{\\!\\!q}$ $\displaystyle=[H_{z,k}(w)]_{i,j},$

where the second to last equality comes from Theorem 2.2, since $|u|=\ell$ and
$|z_{i+1}\cdots z_{j-1}|=j-i-1$. In any case, we find that
$[\mathcal{M}_{a,k+\ell}\cdot H_{z,k}(u)]_{i,j}=[H_{z,k}(w)]_{i,j}$ for all
$1\leq i,j\leq|z|+1$, which completes the proof. ∎

For any positive integer $n$ and $u\in A^{*}$, we have

$\mathcal{P}_{z}(u^{n})=H_{z,(n-1)|u|}(u)\cdot H_{z,(n-2)|u|}(u)\cdots
H_{z,|u|}(u)\cdot H_{z,0}(u).$

###### Proof.

This is an immediate consequence of the definition of $\mathcal{P}_{z}(u^{n})$
and Section 3.2. Let $u=u_{\ell}\cdots u_{0}$. Indeed, by definition we have

$\displaystyle\mathcal{P}_{z}(u^{n})$
$\displaystyle=(\mathcal{M}_{u_{\ell},n|u|-1}\cdots\mathcal{M}_{u_{0},(n-1)|u|})\cdots(\mathcal{M}_{u_{\ell},2|u|-1}\cdots\mathcal{M}_{u_{0},|u|})(\mathcal{M}_{u_{\ell},|u|-1}\cdots\mathcal{M}_{u_{0},0})$
$\displaystyle=H_{z,(n-1)|u|}(u)\cdots H_{z,|u|}(u)\cdot H_{z,0}(u).$

∎

######  Theorem 3.1.

The $q$-binomial $\binom{u^{n}}{z}_{\\!\\!q}$ can be expressed as

$\frac{1}{q^{\mathsf{s}(|z|-1)}}\sum_{k=1}^{m}R_{k}(q)\,\frac{1-q^{c_{k}n|u|}}{1-q^{c_{k}|u|}}$

where $m$ and $c_{k}$ are positive integers and $R_{k}$ are rational functions
whose denominators only have factors of the form $(1-q^{t|u|})$ for some
integer $t$. Moreover, these quantities $c_{k}$ and $R_{k}$ can be effectively
computed. In particular, the sequence $(\binom{u^{n}}{z}_{\\!\\!q})_{n\geq 0}$
converges in $\mathbb{N}[[q]]$ to the formal power series
$\mathfrak{s}_{\mathbf{u},z}(q)$ expressed by the rational function

$\frac{1}{q^{\mathsf{s}(|z|-1)}}\sum_{k=1}^{m}R_{k}(q)\,\frac{1}{1-q^{c_{k}|u|}}.$

###### Proof.

For all $n\geq 1$, we let $\overrightarrow{p_{n}}$ denote the last column of
$\mathcal{P}_{z}(u^{n})$, i.e.,

$\overrightarrow{p_{n}}=\begin{pmatrix}p_{n,\ell}\\\ p_{n,\ell-1}\\\ \vdots\\\
p_{n,1}\\\ p_{n,0}\\\
\end{pmatrix}:=\begin{pmatrix}q^{\mathsf{s}(\ell-1)}\binom{u^{n}}{z_{1}\cdots
z_{\ell}}_{\\!\\!q}\\\ q^{\mathsf{s}(\ell-2)}\binom{u^{n}}{z_{2}\cdots
z_{\ell}}_{\\!\\!q}\\\ \vdots\\\ \binom{u^{n}}{z_{\ell}}_{\\!\\!q}\\\ 1\\\
\end{pmatrix}.$

In particular, $\overrightarrow{p_{1}}$ is the last column of
$\mathcal{P}_{z}(u)$ and, for convenience, we set $\overrightarrow{p_{0}}$ to
be the column vector made of zeroes with only a $1$ in last position. Section
3.2 shows that, for all $n\geq 0$,

$\overrightarrow{p_{n+1}}=H_{z,n|u|}\cdot\overrightarrow{p_{n}}.$ (6)

Since $H_{z,n|u|}$ is upper triangular, we determine the elements of
$\overrightarrow{p_{n}}$ from bottom to top. First, we have $p_{n,0}=1$ for
all $n$. Next, from 6

$p_{n+1,1}=p_{n,1}+\binom{u}{z_{\ell}}_{\\!\\!q}q^{n|u|}\,p_{n,0}$

and we deduce from the above recurrence that

$p_{n+1,1}=\binom{u}{z_{\ell}}_{\\!\\!q}\sum_{i=0}^{n}q^{i|u|}=\binom{u}{z_{\ell}}_{\\!\\!q}\frac{1-q^{(n+1)|u|}}{1-q^{|u|}}.$

Let us produce one extra element, again from 6

$\displaystyle p_{n+1,2}$ $\displaystyle=$ $\displaystyle
p_{n,2}+\binom{u}{z_{\ell-1}}_{\\!\\!q}q^{n|u|}\,p_{n,1}+q\binom{u}{z_{\ell-1}z_{\ell}}_{\\!\\!q}q^{2n|u|}\,p_{n,0}$
$\displaystyle=$ $\displaystyle
p_{n,2}+\binom{u}{z_{\ell-1}}_{\\!\\!q}\binom{u}{z_{\ell}}_{\\!\\!q}\frac{1}{1-q^{|u|}}\left(q^{n|u|}-q^{2n|u|}\right)+\binom{u}{z_{\ell-1}z_{\ell}}_{\\!\\!q}q^{2n|u|+1}.$

We deduce that

$p_{n+1,2}=\binom{u}{z_{\ell-1}}_{\\!\\!q}\binom{u}{z_{\ell}}_{\\!\\!q}\left(\frac{1-q^{(n+1)|u|}}{(1-q^{|u|})^{2}}-\frac{1-q^{2(n+1)|u|}}{(1-q^{|u|})(1-q^{2|u|})}\right)+q\binom{u}{z_{\ell-1}z_{\ell}}_{\\!\\!q}\frac{1-q^{2(n+1)|u|}}{(1-q^{2|u|})}.$

To get a better grasp of the statement, let us rewrite the polynomial as

$p_{n+1,2}=R_{2,1}(q)\,\frac{1-q^{(n+1)|u|}}{1-q^{|u|}}+R_{2,2}(q)\,\frac{1-q^{2(n+1)|u|}}{1-q^{2|u|}}$

with the rational functions

$R_{2,1}(q)=\frac{\binom{u}{z_{\ell-1}}_{\\!\\!q}\binom{u}{z_{\ell}}_{\\!\\!q}}{1-q^{|u|}},\quad
R_{2,2}(q)=\frac{-\binom{u}{z_{\ell-1}}_{\\!\\!q}\binom{u}{z_{\ell}}_{\\!\\!q}+q\binom{u}{z_{\ell-1}z_{\ell}}_{\\!\\!q}(1-q^{|u|})}{1-q^{|u|}}.$

Let $1\leq j\leq\ell$, we prove by induction on $j$ (already shown for
$j=1,2$) that

$p_{n+1,j}=\sum_{k=1}^{m_{j}}R_{j,k}(q)\,\frac{1-q^{c_{j,k}(n+1)|u|}}{1-q^{c_{j,k}|u|}}$

where $m_{j}$ and $c_{j,k}$ are positive integers and $R_{j,k}$ are rational
functions whose denominators only have factors of the form $(1-q^{t|u|})$ for
some integer $t$. We have using 6

$p_{n+1,j}=p_{n,j}+\sum_{k=1}^{j}\binom{u}{z_{\ell-j+1}\cdots
z_{\ell-j+k}}_{\\!\\!q}q^{kn|u|+\mathsf{s}(k-1)}p_{n,j-k}$

by the induction hypothesis, we have already expressed
$p_{n,0},\ldots,p_{n,j-1}$ so

$p_{n+1,j}=p_{n,j}+\sum_{k=1}^{j}\binom{u}{z_{\ell-j+1}\cdots
z_{\ell-j+k}}_{\\!\\!q}q^{kn|u|+\mathsf{s}(k-1)}\sum_{i=1}^{m_{j-k}}R_{j-k,i}(q)\,\frac{1-q^{c_{j-k,i}n|u|}}{1-q^{c_{j-k,i}|u|}}.$

Hence $p_{n+1,j}$ is equal to

$\sum_{k=1}^{j}q^{\mathsf{s}(k-1)}\binom{u}{z_{\ell-j+1}\cdots
z_{\ell-j+k}}_{\\!\\!q}\sum_{i=1}^{m_{j-k}}\frac{R_{j-k,i}(q)}{{1-q^{c_{j-k,i}|u|}}}\,\left(\frac{1-q^{k(n+1)|u|}}{1-q^{k|u|}}-\frac{1-q^{(c_{j-k,i}+k)(n+1)|u|}}{1-q^{(c_{j-k,i}+k)|u|}}\right)$
(7)

which has the desired form as we now explain.

$\displaystyle p_{n+1,j}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{j}\overbrace{\sum_{i=1}^{m_{j-k}}q^{\mathsf{s}(k-1)}\binom{u}{z_{\ell-j+1}\cdots
z_{\ell-j+k}}_{\\!\\!q}\frac{R_{j-k,i}(q)}{{1-q^{c_{j-k,i}|u|}}}}\,\frac{1-q^{k(n+1)|u|}}{1-q^{k|u|}}$
$\displaystyle+\sum_{k=1}^{j}\sum_{i=1}^{m_{j-k}}\underbrace{-q^{\mathsf{s}(k-1)}\binom{u}{z_{\ell-j+1}\cdots
z_{\ell-j+k}}_{\\!\\!q}\frac{R_{j-k,i}(q)}{{1-q^{c_{j-k,i}|u|}}}}\,\frac{1-q^{(c_{j-k,i}+k)(n+1)|u|}}{1-q^{(c_{j-k,i}+k)|u|}}$

where the braced factors are $j+m_{0}+\cdots+m_{j-1}$ new rational functions
$R_{j,\cdot}$ having, by induction hypothesis, the right form.

To conclude with the proof, $\binom{u^{n}}{z}_{\\!\\!q}$ is equal up to a
multiplicative factor $q^{\mathsf{s}(|z|-1)}$ to the upper right corner of
$\mathcal{P}_{z}(u^{n})$ which is equal to $p_{n,\ell}$. ∎

Let $u=0110$ and $z=01$. We have

$H_{z,0}=\mathcal{P}_{z}(u)=\begin{pmatrix}1&q^{3}+1&q^{5}+q^{4}\\\
0&1&q^{2}+q\\\ 0&0&1\\\ \end{pmatrix}\text{ and
}\overrightarrow{p_{1}}=\begin{pmatrix}q^{5}+q^{4}\\\ q^{2}+q\\\ 1\\\
\end{pmatrix}.$

Hence, with the notation of the previous proof, we can express
$\binom{u^{n+1}}{1}_{\\!\\!q}$ as

$p_{n+1,1}=\binom{z}{1}_{\\!\\!q}\frac{1-q^{4(n+1)}}{1-q^{4}}=(q^{2}+q)\frac{1-q^{4(n+1)}}{1-q^{4}}.$

and

$p_{n+1,2}=p_{n,2}+\binom{z}{0}_{\\!\\!q}(q^{2}+q)q^{4n}\frac{1-q^{4n}}{1-q^{4}}+q\binom{z}{01}_{\\!\\!q}q^{8n}.$

So, we have an expression for $q\binom{u^{n+1}}{z}_{\\!\\!q}$ as

$p_{n+1,2}=(q^{3}+1)(q^{2}+q)\left(\frac{1-q^{4(n+1)}}{(1-q^{4})^{2}}-\frac{1-q^{8(n+1)}}{(1-q^{4})(1-q^{8})}\right)+(q^{5}+q^{4})\frac{1-q^{8(n+1)}}{1-q^{8}}$

which can be rewritten as

$p_{n+1,2}=\frac{(q^{3}+1)(q^{2}+q)}{1-q^{4}}\frac{1-q^{4(n+1)}}{1-q^{4}}+\left(\frac{(q^{3}+1)(q^{2}+q)}{1-q^{4}}+(q^{5}+q^{4})\right)\frac{1-q^{8(n+1)}}{1-q^{8}}$
(8)

Now consider the corresponding series (obtained by discarding the term
$q^{4(n+1)}$ and $q^{8(n+1)}$ appearing on the numerators)

$\frac{(q^{3}+1)(q^{2}+q)(q^{4}-q^{8})}{(1-q^{4})^{2}(1-q^{8})}+\frac{q^{5}+q^{4}}{1-q^{8}}=\frac{q^{4}}{(q-1)^{2}\left(q^{2}+1\right)^{2}\left(q^{4}+1\right)}:=\frac{q^{4}}{D(q)}.$

If we first divide by $q$, the series expansion $\sum_{r\geq 0}c_{r}q^{r}$ is
of the form

$q^{3}+2q^{4}+q^{5}+q^{7}+2q^{8}+q^{9}+2q^{11}+4q^{12}+2q^{13}+2q^{15}+4q^{16}+2q^{17}+3q^{19}+6q^{20}+3q^{21}+\cdots$

and those coefficients match exactly those of $\binom{u^{n+1}}{z}_{\\!\\!q}$
for large enough $n$. By taking the reciprocal (or reflected polynomial as
called in [14]) $q^{10}D(1/q)$ of the denominator

$D(q)=q^{10}-2q^{9}+3q^{8}-4q^{7}+4q^{6}-4q^{5}+4q^{4}-4q^{3}+3q^{2}-2q+1,$

it is a routine technique to see that $c_{n}$ satisfies the order-$10$
recurrence relation

$c_{n}=2c_{n-1}-3c_{n-2}+4c_{n-3}-4c_{n-4}+4c_{n-5}-4c_{n-6}+4c_{n-7}-3c_{n-8}+2c_{n-9}-c_{n-10}.$

The fact that the coefficient of $q^{2+4n}$ is vanishing will be explained by
Section 3.3

Since the limit formal power series $\mathfrak{s}_{\mathbf{u},z}$ is a
rational function, as we have shown in the above example, it is not surprising
that its coefficients satisfy a linear recurrence relation with constant
coefficients. We now turn to the polynomial sequence
$(\binom{u^{n}}{z}_{\\!\\!q})_{n}$ and show that it too satisfies a recurrence
relation, but this time with (constant) polynomial coefficients. We make use
of classical arguments about linear recurrences. See, for instance [14], for a
general reference.

Let $R_{j}(q)$ be given rational functions and $c_{j}$ be pairwise distinct
non-negative integers. The sequence $(p_{n})_{n\geq 0}$

$\left(\sum_{j=1}^{s}R_{j}(q)\,q^{c_{j}n}\right)_{n\geq 0}$

satisfies the following linear recurrence relation of order $s$ with
polynomial coefficients

$p_{n+s}=\sum_{k=1}^{s}\underbrace{(-1)^{k-1}\left(\sum_{1\leq
i_{1}<\cdots<i_{k}\leq
s}q^{c_{i_{1}}+\cdots+c_{i_{k}}}\right)}_{:=\mathfrak{D}_{k}}p_{n+s-k}$

###### Proof.

The linear recurrent sequences $\left(q^{c_{j}n}\right)_{n\geq 0}$ and
$\left(R_{j}(q)q^{c_{j}n}\right)_{n\geq 0}$ have both a characteristic
polynomial of the form $X-q^{c_{j}}$. It is a well-known result that the
characteristic polynomial of the sum of linear recurrent sequences (with
distinct roots) is the product of the corresponding characteristic
polynomials. Hence, the characteristic polynomial of the sequence of interest
is

$\prod_{j=1}^{s}\left(X-q^{c_{j}n}\right)=X^{s}+\sum_{k=1}^{s}\mathfrak{D}_{k}X^{s-k}.$

∎

Let $R_{j}(q)$ be given rational functions and $c_{j}$ be pairwise distinct
non-negative integers. The sequence $(p_{n})_{n\geq 0}$

$\left(\sum_{j=1}^{s}R_{j}(q)\,\sum_{i=0}^{n}q^{c_{j}i}\right)_{n\geq
0}=\left(\sum_{j=1}^{s}R_{j}(q)\,\frac{1-q^{c_{j}(n+1)}}{1-q^{c_{j}}}\right)_{n\geq
0}$

satisfies the following linear recurrence relation of order $s+1$ with
polynomial coefficients

$p_{n+s+1}=\sum_{k=1}^{s+1}(\mathfrak{D}_{k}-\mathfrak{D}_{k-1})\,p_{n+k}$

setting $\mathfrak{D}_{0}=-1$ and $\mathfrak{D}_{s+1}=0$.

###### Proof.

This follows from the classical result that if $f(t)$ is the rational function
equal to the series $\sum_{n\geq 0}u_{n}\,t^{n}$ where $u_{n}$ satisfies a
linear recurrence relation, then $\frac{1}{1-t}.f(t)$ encodes the series of
the partial sums and one can get a linear relation from the denominator of the
series. ∎

Letting $q=1$ we recover Salomaa’s result [25, Thm. 3] as a special case of
our results.

The sequence of $q$-binomials $(\binom{u^{n}}{z}_{\\!\\!q})_{n\geq 0}$
satisfies a linear recurrence relation with polynomial coefficients. In
particular, the sequence of binomials $(\binom{u^{n}}{z})_{n\geq 0}$ satisfies
a linear recurrence relation with constant coefficients.

Let us continue Section 3.2. With the notation of Section 3.2 looking at 8, we
have $c_{1}=4$ and $c_{2}=8$, $\mathfrak{D}_{1}=q^{4}+q^{8}$ and
$\mathfrak{D}_{2}=-q^{12}$. Hence, with Section 3.2, the sequence
$\left(\binom{(0110)^{n}}{01}_{\\!\\!q}\right)_{n\geq 0}$ satisfies the
relation

$p_{n+3}=(1+q^{4}+q^{8})p_{n+2}-(q^{4}+q^{8}+q^{12})p_{n+1}+q^{12}p_{n}.$

Now the integer sequence $\left(\binom{(0110)^{n}}{01}\right)_{n\geq 0}$ whose
first terms are $0,2,8,18,32,50,72,98,128,162,200$ satisfies the relation

$p_{n+3}=3p_{n+2}-3p_{n+1}+p_{n}.$

###  3.3 Growth of the coefficients of the series in the periodic case

Let $\mathbf{u}=\cdots uuu$. Consider again the series
$\mathfrak{s}_{\mathbf{u},z}(q)=\sum_{i\geq 0}c_{i}\,q^{i}$ which is the limit
of the sequence of $q$-binomials $\binom{u^{n}}{z}_{\\!\\!q}$ considered in
Theorem 3.1. We have already observed with Section 3.1 that $i\mapsto c_{i}$
has a polynomial growth. In this section, we obtain some more information
about the growth order and the indices for which $c_{i}$ vanishes.

Let $\mathfrak{s}_{\mathbf{u},z}(q)=\sum_{i\geq 0}c_{i}\,q^{i}$. The function
$i\mapsto c_{i}$ is in $\mathcal{O}(i^{|z|-1})$.

###### Proof.

Proceeding as in the proof of Theorem 3.1, we can express

$\binom{u^{n}}{z}_{\\!\\!q}=\sum_{j=1}^{r}\frac{P_{j}(q)}{\prod_{i=1}^{|z|}(1-q^{j_{i}|u|})^{\alpha_{j_{i}}}}$

where $P_{j}$’s are polynomials and for all $i$,
$\sum_{i=1}^{|z|}\alpha_{j_{i}}\leq|z|$. Indeed, in the expression 7 to get
$p_{n,j}$ from $p_{n,j-1}$ in the induction step, a multiplication by
$\frac{1}{1-q^{(c_{j-k,i}+k)|u|}}$ occur. So, at each stage, we create a
factor $1/(1-q^{j_{i}|u|})$, and some of these factors may be equal and
collected together thanks to the exponent $\alpha_{j,i}$. One concludes by
considering the partial fraction decomposition and recalling that the $n$th
coefficient in the series expansion of $\frac{1}{(1-q)^{t}}$ is in
$\mathcal{O}(n^{t-1})$. ∎

######  Theorem 3.2.

Let $\mathfrak{s}_{\mathbf{u},z}(q)=\sum_{i\geq 0}c_{i}\,q^{i}$. Let
$r\in\\{0,\ldots,|u|-1\\}$. Either $c_{r+i|u|}$ is zero for all large enough
$i$, or the growth order of the function $r+i|u|\mapsto c_{r+i|u|}$ is in
$\Theta(i^{|z|-1})$. Moreover, the two kinds of behavior are completely
determined by the words $u$ and $z$.

###### Proof sketch.

The previous lemma already gives the upper bound, so it suffices to give the
lower bound of correct order. Let $z=z_{\ell}\cdots z_{1}$ with $\ell=|z|$.
For $j\in\\{1,\ldots,\ell\\}$, we let

$u=p_{j}z_{j}s_{j}\quad\text{and}\quad|s_{j}|=t_{j}.$ (9)

(Here we assume that each letter of $z$ appears in $u$, as otherwise
$\binom{u^{k}}{z}_{\\!\\!q}=0$ for all $k\geq 0$.) These $\ell$ factorizations
of $u$ are not necessarily unique. Let us consider one such $\ell$-tuple
$(t_{\ell},\ldots,t_{1})$ of non-negative integers. We will discuss later on
the possible choices: each such tuple will provide a periodic sequence of
indices of period $|u|$ for which the corresponding coefficients growth
polynomially.

######  Claim 1.

For all large enough $n$, if $[q^{n}]\binom{u^{n+\ell}}{z}_{\\!\\!q}\neq 0$,
then there exists an occurrence of $z$ in $u^{n+\ell}$ such that the letters
of $z$ appear in distinct copies of $u$.

######  Proof of claim 1:

Let $t$ be the maximal over all possible $t_{j}$s as in (9), and assume that
$n\geq\ell t+(|u|-1)\frac{\ell(\ell-1)}{2}$. Let us write
$u^{n+\ell}=u_{n+\ell}\cdots u_{1}$. Since the coefficient is assumed
positive, there is an occurrence of $z$ in $u^{n+\ell}$ contributing the
monomial $q^{n}$. Let $m_{i}$ indicate the copy $u_{m_{i}}$ in which the
letter $z_{i}$ of this particular occurrence of $z$ appears in, and let
$(t_{\ell},\ldots,t_{1})$ be the corresponding set of factorizations as in
(9). Then we have that

$n=\sum_{i=1}^{\ell}t_{i}+(|u|-1)\frac{\ell(\ell-1)}{2}+|u|\cdot\sum_{i=1}^{\ell}(m_{i}-i).$
(10)

Indeed, for each $i=1$, …, $\ell$, the number of letters to the right of
$z_{i}$ no appearing in this occurrence of $z$ equals
$t_{i}+(m_{i}-1)|u|-(i-1)$. Summing over all $i$ and rearranging yields the
claimed form of $n$. Since $n\geq\ell t+(|u|-1)\frac{\ell(\ell-1)}{2}$, we
deduce that $\sum_{i=1}^{\ell}(m_{i}-i)\geq 0$. Therefore,
$r:=\sum_{i=1}^{\ell}m_{i}\geq\ell(\ell+1)/2$. There thus exist integers
$r_{\ell}>r_{\ell-1}>\cdots>r_{1}\geq 1$ such that $r=\sum_{i=1}^{\ell}r_{i}$.
If we consider the occurrence of $z$ in $u^{n+\ell}$ such that the letter
$z_{i}$ appears in the copy $u_{r_{i}}$, we get a contribution of $q^{n}$ as
in (10). This suffices for the claim.

Assume that $[q^{n}]\binom{u^{n+\ell}}{z}_{\\!\\!q}\neq 0$ with $n$ so large
that the above claim holds. Then there exist tuples $(t_{\ell},\ldots,t_{1})$
and $(m_{\ell},\ldots,m_{1})$, with the $m_{i}$ distinct, such that $n$ is as
in (10). Let $m=\sum_{i=1}(m_{i}-i)$ and let $\alpha_{m}$ denote the
coefficient $[q^{m}]\binom{m+\ell}{\ell}_{\\!\\!q}$. Now $\alpha_{m}$ is the
number of index-tuples $(m_{\ell},\ldots,m_{1})$ such that
$\sum_{i=1}^{\ell}m_{i}-i=m$. For $\ell$ fixed, we have
$\alpha_{m}\sim\frac{m^{\ell-1}}{\ell!(\ell-1)!}+\mathcal{O}(m^{\ell-2})=\Omega(n^{\ell-1})$
by [28, Thm. 2.4] (since the $t_{i}$ are bounded and $|u|$ is constant). By
(10), the $\alpha_{m}$ index tuples $(m_{\ell},\ldots,m_{1})$ give distinct
occurrences of $z$ in $\binom{u^{n+\ell}}{z}_{\\!\\!q}$, each of which
contribute $q^{n}$ to the $q$-binomial coefficient. We have thus showed that
$[q^{n}]\binom{u^{n+\ell}}{z}_{\\!\\!q}\geq\alpha_{m}=\Omega(n^{k-1})$.

Let us now discuss which term $q^{n}$ of the series appear with a non-zero
coefficient. Consider an arbitrary occurrence of $z$ as a subword of $u^{n}$
providing a non-zero coefficient for some $q^{n}$ with associated
factorizations as in (9). By reducing (10) modulo $|u|$, we conclude that

$n\equiv\sum_{j=1}^{\ell}t_{j}-\frac{\ell(\ell-1)}{2}\pmod{|u|}$

for some admissible $\ell$-tuple $(t_{1},\ldots,t_{\ell})$. If this is not the
case, then the corresponding coefficient in the series is vanishing.

As a conclusion, we have thus shown that the coefficient of every large enough
power $q^{n}$ is non-zero if and only if there exists a $\ell$-tuple
associated with some factorization of the form 9 such that $n$ is congruent to
$\sum_{j=1}^{\ell}t_{j}-\ell(\ell-1)/2$ modulo $|u|$. ∎

In Section 3.2, with $z=01$ and $u=0110$, we have two choices for
$t_{1}\in\\{1,2\\}$ (the positions of $z_{1}=1$ in $u$) and also two choices
for $t_{2}\in\\{0,3\\}$ (the positions of $z_{2}=0$ in $u$). So the pairs
$(t_{1},t_{2})$ are $(1,0)$, $(1,3)$, $(2,0)$ and $(2,3)$. Modulo $4$, the sum
$t_{1}+t_{2}-1$ may take the values $0,1,3$ and we see that the coefficient
$\langle\mathfrak{s}_{(0110)^{\omega},01},q^{2+4n}\rangle=0$ for all $n$.

##  4 Extra properties of $q$-Parikh matrices

In this section we consider some other properties of $q$-Parikh matrices, as
well as some inequalities that follow.

###  4.1 Properties of minors and other relations

A minor of a matrix is the determinant of a square submatrix obtained by
removing one (or more) of its rows and columns. The value of each minor of an
arbitrary Parikh matrix is a non-negative integer [19, Thm. 6] and it still
holds true for Parikh matrix induced by a word [7, Cor. 21]. This is an easy
application in linear algebra. We have a similar result in the $q$-deformed
case and we provide the proof for the sake of completeness. Any minor of
$\mathcal{P}_{z}(u)$ is a polynomial with non-negative integer coefficients.

###### Proof.

Proceed by induction on the length of $u$. The result trivially holds if
$|u|=0,1$. Now assume that the result holds for words of length at most $n$
and consider the word $dw$ of length $n+1$ where $d$ is a letter and $|w|=n$.
We have that

$\mathcal{P}_{z}(dw)=\mathcal{M}_{d,|w|}\mathcal{P}_{z}(w).$

Assume that $d$ occurs in $z$ in positions $i_{1},\ldots,i_{s}$. This means
that the row of index $i_{j}$ in $\mathcal{P}_{z}(dw)$, for
$j\in\\{1,\ldots,s\\}$ is equal to the sum of the $i_{j}$th row of
$\mathcal{P}_{z}(w)$ and $q^{|w|}$ times the $(i_{j}+1)$st row of
$\mathcal{P}_{z}(w)$. By linearity of the determinant, any minor of
$\mathcal{P}_{z}(dw)$ can thus be expressed as a linear combination of minors
of $\mathcal{P}_{z}(w)$ with coefficients $1$ or $q^{|w|}$. By induction
hypothesis, minors of $\mathcal{P}_{z}(w)$ are polynomials with non-negative
integer coefficients. ∎

The following corollary is an immediate consequence.

Let $M=(\mathcal{P}_{z}(u))^{-1}$ and $1\leq i\leq j\leq|z|+1$,
$(-1)^{i+j}M_{i,j}$ is a polynomial with non-negative integer coefficients.

Let us focus on $2\times 2$ minors occurring above the main diagonal. They are
of the form

$\displaystyle\begin{split}\begin{vmatrix}q^{\mathsf{s}(|vw|-1)}\binom{u}{vw}_{\\!\\!q}&q^{\mathsf{s}(|vwx|-1)}\binom{u}{vwx}_{\\!\\!q}\\\
q^{\mathsf{s}(|w|-1)}\binom{u}{w}_{\\!\\!q}&q^{\mathsf{s}(|wx|-1)}\binom{u}{wx}_{\\!\\!q}\end{vmatrix}=&q^{\mathsf{s}(|vw|-1)+\mathsf{s}(|wx|-1)}\binom{u}{vw}_{\\!\\!q}\binom{u}{wx}_{\\!\\!q}\\\
&-q^{\mathsf{s}(|w|-1)+\mathsf{s}(|vwx|-1)}\binom{u}{w}_{\\!\\!q}\binom{u}{vwx}_{\\!\\!q}.\end{split}$
(11)

for some factors $v,w,x$ of $z$ such that $z=pvwxs$, $p,s\in A^{*}$. We
observe that in the context of $q$-deformed rational numbers, it is shown in
[21, Thm. 2] that if $r(q)/s(q)$ and $r^{\prime}(q)/s^{\prime}(q)$ are two
$q$-rationals, then $rs^{\prime}-r^{\prime}s$ is a polynomial in $q$ with
positive integer coefficients. The fact that 11 belongs to $\mathbb{N}[q]$ is
the $q$-analogue of what Salomaa calls the Cauchy inequality [24]

$\binom{u}{vw}\binom{u}{wx}\geq\binom{u}{w}\binom{u}{vwx}.$

It would be interesting to see if such a polynomial 11 has a combinatorial
interpretation, or corresponds to (the product of) other $q$-deformed binomial
coefficients. The following example shows that this is at least not the
product of some Gaussian binomial coefficients

Take $u=ababba$ and $z=bba$, $v=w=b$ and $x=a$. One can verify that the minor
associated to those factors is $q^{13}+q^{12}+q^{10}$. Since the power
$q^{11}$ is missing, this cannot be a product of Gaussian coefficients (if it
were the case, we would have consecutive powers of $q$ in the polynomial
because of the unimodality of Gaussian binomials).

In [24], a “dual” of the Cauchy inequality is considered. In our setting, we
get the following. For all words $x,y,z,w$, the polynomial

$\binom{xy}{w}_{\\!\\!q}\binom{yz}{w}_{\\!\\!q}-\binom{xyz}{w}_{\\!\\!q}\binom{y}{w}_{\\!\\!q}$

has non-negative integer coefficients.

###### Proof.

We list all pairs of occurrences of $w$ as a subword of both $xyz$ and $y$ and
injectively match these pairs of occurrences with distinct occurrences in $xy$
and $yz$. So every contribution to the second term is always compensated by a
contribution to the first term. There are three cases.

If we focus on an occurrence of $w$ in $xyz$ where all the selected letters
appear in $yz$, then the same occurrence appears in $yz$ and they contribute
equally to $\binom{xyz}{w}_{\\!\\!q}$ and respectively
$\binom{yz}{w}_{\\!\\!q}$. Similarly, any occurrence of $w$ in $y$ appears in
the same position in $xy$. They contribute equally to $\binom{y}{w}_{\\!\\!q}$
and respectively $\binom{xy}{w}_{\\!\\!q}$.

If we focus on an occurrence of $w$ in $xyz$ where all the selected letters
appear in $xy$ (and at least a letter of $x$ is selected, because the case
where $w$ is a subword of $y$ has been treated above), then the same
occurrence appears in $xy$. The contribution of the first to
$\binom{xyz}{w}_{\\!\\!q}$ has an extra factor $q^{|w|\,|z|}$ compared with
the contribution of the second to $\binom{xy}{w}_{\\!\\!q}$. Similarly, any
occurrence of $w$ in $y$ appears in $yz$. They contribute to
$\binom{y}{w}_{\\!\\!q}$ and respectively $\binom{yz}{w}_{\\!\\!q}$ and the
second one has an extra factor $q^{|w|\,|z|}$.

Finally, the remaining occurrences of $w$ in $xyz$ are such that at least one
letter is selected in both $x$ and $z$. We use the same notation as Salomaa.
Let $xyz=x_{m}\cdots x_{0}y_{\ell}\cdots y_{0}z_{k}\cdots z_{0}$. Let us
consider the occurrence given by

$w=x_{i_{|w|}}\cdots x_{i_{p+q+1}}y_{i_{p+q}}\cdots y_{i_{p+1}}z_{i_{p}}\cdots
z_{i_{1}}$

where $p\geq 1$, $p+q+1\leq|w|$ and $k\geq i_{p}>\cdots>i_{1}\geq 0$,
$\ell\geq i_{p+q}>\cdots>i_{p+1}\geq 0$, $m\geq i_{|w|}>\cdots>i_{p+q+1}\geq
0$. We also consider any occurrence $y_{j_{|w|}}\cdots y_{j_{1}}$ of $w$
within $y$, $\ell\geq j_{|w|}>\cdots>j_{1}\geq 0$. Let
$\gamma_{p+n}=\min(i_{p+n},j_{p+n})$ and $\delta_{p+n}=\max(i_{p+n},j_{p+n})$
for $n=1,\ldots,q$. Now $w$ occurs in $xy$ as

$x_{i_{|w|}}\cdots x_{i_{p+q+1}}y_{\gamma_{p+q+1}}\cdots
y_{\gamma_{p+1}}y_{j_{p}}\cdots y_{j_{1}}$

and $w$ occurs in $yz$ as

$y_{j_{|w|}}\cdots y_{j_{p+q+1}}y_{\delta_{p+q+1}}\cdots
y_{\delta_{p+1}}z_{i_{p}}\cdots z_{i_{1}}.$

As in the previous case a common power $q^{(|w|-p)}$ appears. To conclude with
the proof, the reader may observe that the considered pairs of occurrences of
$w$ within $xy$ and $yz$ and pairwise distinct. ∎

###  4.2 On expressing generalized $q$-Parikh matrices with Eğecioğlu’s

Recall the notation $\mathcal{E}_{k}$ from Section 2 in which we consider the
specific word $12\cdots k$. As pointed out by Şerbănuţă [7], elements of a
Parikh matrix $\mathcal{P}_{z}(u)$ associated with a word $z$ can be related
to elements of a classical111classical in the sense that it is a matrix like
those studied initially in [18]. Note here that this is achieved by adopting a
larger alphabet to avoid the redundancies that can appear in $z$. Parikh
matrix $\mathcal{E}_{|z|}(\sigma_{z}(u))$ for which the author considers a
particular morphism that we recall below. Hence algebraic properties of Parikh
matrices can be transferred to matrices associated with a word. We investigate
this question for our $q$-deformations.

As a preliminary comment, for an arbitrary non-erasing morphism
$\varphi:A^{*}\to B^{*}$ and words $w\in A^{*}$, $u\in B^{*}$, there is a
formula to compute $\binom{\varphi(w)}{u}_{\\!\\!q}$ as

$\sum_{\ell=1}^{|u|}\sum_{\begin{subarray}{c}u_{1},\ldots,u_{\ell}\in B^{+}\\\
u=u_{1}\cdots
u_{\ell}\end{subarray}}\sum_{\begin{subarray}{c}w=w_{0}a_{1}w_{1}\cdots
a_{\ell}w_{\ell}\\\ a_{1},\ldots a_{\ell}\in A\\\ w_{1},\ldots,w_{\ell}\in
A^{*}\end{subarray}}\binom{\varphi(a_{1})}{u_{1}}_{\\!\\!q}\cdots\binom{\varphi(a_{\ell})}{u_{\ell}}_{\\!\\!q}q^{\sum_{i=1}^{\ell}|u_{i}|(|\varphi(w_{i}a_{i+1}\cdots
a_{\ell}w_{\ell})|-|u_{i+1}\cdots u_{\ell}|)}.$

In particular, if the morphism is $r$-uniform, then the exponent can be
rewritten as

$\sum_{i=1}^{\ell}|u_{i}|(r(\ell-i)+r|w_{i}\cdots w_{\ell}|-|u_{i+1}\cdots
u_{\ell}|).$

This is the $q$-analogue of [16, Thm. 24] and it can be deduced form Theorem
2.2. The idea is to highlight subwords $u_{i}$ forming an occurrence of $u$
within blocks of the form $\varphi(a_{i})$ for some of the letters $a_{i}$
constituting $w$. The information about the exponent corresponding to such an
occurrence of $u_{i}$ in $\varphi(a_{i})$ is encoded by
$\binom{\varphi(a_{i})}{u_{i}}_{\\!\\!q}$. It still needs to be corrected by
the number of letters to the right of the block $\varphi(a_{i})$, i.e.,
$|\varphi(w_{i}a_{i+1}\cdots a_{\ell}w_{\ell})|$ and different from the last
letters of $u$ that still needs to be taken into account.

Let $z=z_{1}\cdots z_{\ell}$ be a word of length $\ell$ over $A$. For all
$a\in A$, we define the morphism $\sigma_{z}:A^{*}\to\\{1,\ldots,\ell\\}^{*}$
by

$\sigma_{z}(a)=j_{1}\cdots j_{r}\quad\text{ whenever
}z_{j_{1}}=\cdots=z_{j_{r}}=a,$

i.e., $\sigma_{z}$ maps a letter to the word encoding the positions of its
occurrences within $z$. As an example, with $z=121323$, we have

$\sigma_{z}:1\mapsto 13,\ 2\mapsto 25,\quad 3\mapsto 46.$

Notice that $\sigma_{z}(z_{i})$ always contains $i$. Conversely, every
$i\in\\{1,\ldots,\ell\\}$ appears in exactly one of the images
$\sigma_{z}(j)$, the one such that $z_{i}=j$.

Let $z$ be a word such that $z_{i}\neq z_{i+1}$ for all $1\leq i<|z|$. Let
$1\leq i\leq j\leq|z|$, the $q$-binomial

$\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots j}_{\\!\\!q}$

is a monomial of the form $q^{n}$ for some $n$. Otherwise stated, $i\cdots j$
appears exactly once in $\sigma_{z}(z_{i}\cdots z_{j})$.

###### Proof.

By assumption $z_{k}\neq z_{k+1}$, $i\leq k<j$. Hence the letters $k$ and
$k+1$ cannot both appear in the image of a letter. To get an occurrence of
$i\cdots j$ in $\sigma_{z}(z_{i}\cdots z_{j})$, we must have that the
occurrence of $k$ is the occurrence of $k$ in $\sigma_{z}(z_{k})$. Since $k$
appears only once in $\sigma_{z}(z_{k})$ by definition of the morphism
$\sigma_{z}$, the claim follows.

∎

Let $A$ be an alphabet of size $k$. Let $z$ be a word of length $k.r$ such
that $|z|_{a}=r$ for all $a\in A$ and $z_{i}\neq z_{i+1}$ for all $1\leq
i<k.r$. We have

$\displaystyle\binom{\sigma_{z}(u)}{i\cdots j}_{\\!\\!q}$
$\displaystyle=\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots
j}_{\\!\\!q}\cdot\binom{u}{z_{i}\cdots z_{j}}_{\\!\\!q^{r}}\quad\text{ and }$
(12) $\displaystyle\binom{\sigma_{z}(u)^{R}}{i\cdots j}_{\\!\\!q}$
$\displaystyle=\binom{\sigma_{z}(z_{i}\cdots z_{j})^{R}}{j\cdots
i}_{\\!\\!q}\binom{\widetilde{u}}{z_{i}\cdots z_{j}}_{\\!\\!q^{r}}$ (13)

for all $1\leq i\leq j\leq k.r$. Here we have $x^{R}=\widetilde{x}$ for the
sake of readability.

###### Proof.

We first prove first (12). There is a one-to-one correspondence between the
occurrences of $z_{i}\cdots z_{j}$ in $u$ and $i\cdots j$ in $\sigma_{z}(u)$.
Consider one such occurrence and write $u=x_{i-1}z_{i}x_{i}\cdots
x_{j-1}z_{j}x_{j}$ where $x_{k}$ are words. From Theorem 2.2, the contribution
of this occurrence to $\binom{u}{z_{i}\cdots z_{j}}_{\\!\\!q}$ is

$q^{\sum_{m=i}^{j}(m-i+1)|x_{m}|}.$

This particular occurrence corresponds to an occurrence of $i\cdots j$ within
$\sigma_{z}(u)$ as factorized below

$\sigma_{z}(u)=\sigma_{z}(x_{i-1})\alpha_{i}\,i\,\beta_{i}\sigma_{z}(x_{i})\cdots\sigma_{z}(x_{j-1})\alpha_{j}\,j\,\beta_{j}\sigma_{z}(x_{j})$

where we have highlighted the occurrence of $k\in\\{i,\ldots,j\\}$ within
$\sigma_{z}(z_{k})=\alpha_{k}k\beta_{k}$. The contribution of this occurrence
to $\binom{\sigma_{z}(u)}{i\cdots j}_{\\!\\!q}$ is

$q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\sigma_{z}(x_{m})\alpha_{m+1}|}=q^{r\sum_{m=i}^{j}(m-i+1)|x_{m}|}.q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\alpha_{m+1}|},$

where we set $\alpha_{j+1}=\varepsilon$ and we used the fact that $\sigma_{z}$
is an $r$-uniform morphism. To conclude with the proof, observe that the
second factor on the r.h.s. is the contribution to
$\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots j}_{\\!\\!q}$ of the occurrence
of $i\cdots j$ within
$\alpha_{i}\,i\,\beta_{i}\cdots\alpha_{j}\,j\,\beta_{j}$.

We then prove (13) . There is a one-to-one correspondence between the
occurrences of $z_{j}\cdots z_{i}$ in $u$ and $z_{i}\cdots z_{j}$ in
$\widetilde{u}$ (and occurrences of $i\cdots j$ in $\sigma_{z}(u)^{R}$).
Consider one such occurrence and write $u=x_{j}z_{j}x_{j-1}\cdots
x_{i}z_{i}x_{i-1}$ where the $x_{k}$ are words. We thus have

$\displaystyle\widetilde{u}$
$\displaystyle=\widetilde{x}_{i-1}z_{i}\widetilde{x}_{i}\cdots\widetilde{x}_{j-1}z_{j}\widetilde{x}_{j}\quad\text{and}$
$\displaystyle\sigma_{z}(u)^{R}$
$\displaystyle=\sigma_{z}(x_{i-1})^{R}\sigma_{z}(z_{i})^{R}\sigma_{z}(x_{i})^{R}\cdots\sigma_{z}(x_{j-1})^{R}\sigma_{z}(z_{j})^{R}\sigma_{z}(x_{j})^{R}.$

From Theorem 2.2, the contribution of the occurrence of $z_{i}\cdots z_{j}$ to
$\binom{\widetilde{u}}{z_{i}\cdots z_{j}}_{\\!\\!q}$ is
$q^{\sum_{m=i}^{j}(m-i+1)|\widetilde{x}_{m}|}$. For each
$k\in\\{i,\ldots,j\\}$, write $\sigma(z_{k})^{R}=\alpha_{k}k\beta_{k}$. Then
the corresponding occurrence of $i\cdots j$ in $\sigma_{z}(u)^{R}$ contributes

$q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\sigma_{z}(x_{m})^{R}\alpha_{m+1}|}=q^{r\sum_{m=i}^{j}(m-i+1)|x_{m}|}.q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\alpha_{m+1}|}$

to $\binom{\sigma_{z}(u)^{R}}{i\cdots j}_{\\!\\!q}$. (Again we set
$\alpha_{j+1}=\varepsilon$ and we have used the fact that $\sigma_{z}$ is
$r$-uniform.) We thus find

$\binom{\sigma_{z}(u)^{R}}{i\cdots
j}_{\\!\\!q}=\binom{\widetilde{u}}{z_{i}\cdots z_{j}}_{\\!\\!q^{r}}\cdot
q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\alpha_{m+1}|}.$

It remains to show that

$q^{\sum_{m=i}^{j}(m-i+1)|\beta_{m}\alpha_{m+1}|}=\binom{\sigma_{z}(z_{i}\cdots
z_{j})^{R}}{j\cdots i}_{\\!\\!q}.$ (14)

Notice that $\sigma_{z}(z_{i}\cdots
z_{j})^{R}=\alpha_{j}j\beta_{j}\cdots\alpha_{i}i\beta_{i}$, so that the right-
hand-side of 14 is

$q^{\sum_{m=i}^{j}(j-m+1)|\beta_{m}\alpha_{m-1}|}.$

Here we set $\alpha_{i-1}=\varepsilon$.

On the other hand, we observe that the term on the left-hand-side of 14 is
also equal to

$\displaystyle\binom{(\sigma_{z}((z_{i}\cdots z_{j})^{R}))^{R}}{i\cdots
j}_{\\!\\!q}$
$\displaystyle=q^{(r-1)(j+1-i)^{2}}\binom{\sigma_{z}((z_{i}\cdots
z_{j})^{R})}{j\cdots i}_{\\!\\!1/q}$
$\displaystyle=q^{(r-1)(j+1-i)^{2}-\sum_{m=i}^{j}(j-m+1)|\widetilde{\alpha}_{m}\widetilde{\beta}_{m-1}|},$

where we let $\beta_{i-1}=\varepsilon$ and the first equality comes from
Section 2.2. Now to show that (14) is true, it is enough to show that

$\sum_{m=i}^{j}(j-m+1)|\widetilde{\alpha}_{m}\widetilde{\beta}_{m-1}|+\sum_{m=i}^{j}(j-m+1)|\beta_{m}\alpha_{m-1}|=(r-1)(j+1-i)^{2}.$

Indeed, joining the sums on the left-hand-side, we simplify to

$\displaystyle\sum_{m=i}^{j}(j-m+1)|\alpha_{m}\beta_{m}\alpha_{m-1}\beta_{m-1}|$
$\displaystyle=(r-1)(j-i+1)+2(r-1)\sum_{m=i+1}^{j}(j-m+1)$
$\displaystyle=(r-1)(j-i+1)+2(r-1)\sum_{k=1}^{j-i}k$
$\displaystyle=(r-1)(j-i+1+(j-i)(j-i+1))=(r-1)(j+1-i)^{2}.$

Thus the proof is complete. ∎

In the next statement if $M$ is a matrix whose entries are polynomials in $q$,
an expression of the form $M(q^{r})$ means that we have substituted $q$ by
$q^{r}$ in every entry.

Let $z$ be as in Section 4.2. Let further $Z$ (resp. $C$) be the upper
triangular matrix whose above-diagonal entries $Z_{i,j+1}$ (resp.,
$C_{i,j+1}$), $i\leq j\leq|z|+1$, are of the form
$\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots j}_{\\!\\!q}$ (resp.
$q^{\mathsf{s}(j-i)}$). Then

$C(q^{r-1})\odot\mathcal{E}_{|z|}(\sigma_{z}(u))=Z\odot\mathcal{P}_{z}(u)(q^{r})$

and

$C(q^{r-1})\odot\mathcal{E}_{|z|}(\sigma_{z}(u))^{-1}=Z\odot(\mathcal{P}_{z}(u)(q^{r}))^{-1}.$

###### Proof.

We inspect the element at position $i$, $j+1$, the right-hand-side of the
first equality is

$\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots
j}_{\\!\\!q}q^{r\cdot\mathsf{s}(j-i)}\binom{u}{z_{i}\cdots
z_{j}}_{\\!\\!q^{r}}=q^{(r-1)\cdot\mathsf{s}(j-i)}q^{\mathsf{s}(j-i)}\binom{\sigma_{z}(u)}{i\cdots
j}_{\\!\\!q}$

where we used 12.

For the second equality, inspecting the element at position $i$, $j+1$, and
using Theorem 2.3, the equality is equivalent to

$q^{(r-1)\cdot\mathsf{s}(j-i)}\cdot(-1)^{i+j+1}q^{(j+1-i)(r|u|-1)}q^{-\mathsf{s}(j-i)}\binom{\sigma_{z}(u)^{R}}{i\cdots
j}_{\\!\\!1/q}\\\ =\binom{\sigma_{z}(z_{i}\cdots z_{j})}{i\cdots
j}_{\\!\\!q}(-1)^{i+j+1}q^{r(j+1-i)(|u|-1)}q^{-r\cdot\mathsf{s}(j-i)}\binom{\widetilde{u}}{z_{i}\cdots
z_{j}}_{\\!\\!1/q^{r}}.$

Rearranging gives

$\displaystyle\binom{\sigma_{z}(u)^{R}}{i\cdots j}_{\\!\\!1/q}$
$\displaystyle=q^{-(r-1)(j+1-i)^{2}}\binom{\sigma_{z}(z_{i}\cdots
z_{j})}{i\cdots j}_{\\!\\!q}\binom{\widetilde{u}}{z_{i}\cdots
z_{j}}_{\\!\\!1/q^{r}}$ $\displaystyle=\binom{(\sigma_{z}(z_{i}\cdots
z_{j}))^{R}}{j\cdots i}_{\\!\\!1/q}\cdot\binom{\widetilde{u}}{z_{i}\cdots
z_{j}}_{\\!\\!1/q^{r}}$

by Section 2.2. This is equivalent to (13) by replacing $1/q$ with $q$ in the
argument. ∎

With $z=121323$, $u=1121323$, we have $\sigma_{z}(z)=132513462546$ and
$\sigma_{z}(u)=02021402351435$. Verifying the above theorem, we have $r=2$,

$Z=\left(\begin{smallmatrix}1&q&q^{3}&q^{5}&q^{9}&q^{13}&q^{18}\\\
0&1&q&q^{2}&q^{5}&q^{8}&q^{12}\\\ 0&0&1&1&q^{2}&q^{4}&q^{7}\\\
0&0&0&1&q&q^{2}&q^{4}\\\ 0&0&0&0&1&1&q\\\ 0&0&0&0&0&1&1\\\ 0&0&0&0&0&0&1\\\
\end{smallmatrix}\right),\quad\text{and}\quad
C=\left(\begin{smallmatrix}1&1&q&q^{3}&q^{6}&q^{10}&q^{15}\\\
0&1&1&q&q^{3}&q^{6}&q^{10}\\\ 0&0&1&1&q&q^{3}&q^{6}\\\ 0&0&0&1&1&q&q^{3}\\\
0&0&0&0&1&1&q\\\ 0&0&0&0&0&1&1\\\ 0&0&0&0&0&0&1\end{smallmatrix}\right).$

Further,

$\mathcal{P}_{z}(u)=\left(\begin{smallmatrix}1&q^{6}+q^{5}+q^{3}&q^{10}+q^{9}+q^{7}+q^{6}+q^{4}&q^{13}+q^{12}&q^{15}+q^{14}+q^{13}+q^{12}&q^{16}+q^{15}&q^{16}+q^{15}\\\
0&1&q^{4}+q&q^{7}&q^{9}+q^{7}&q^{10}&q^{10}\\\
0&0&1&q^{6}+q^{5}+q^{3}&q^{8}+q^{7}+q^{6}+2q^{5}+q^{3}&q^{9}+q^{8}+q^{6}&q^{9}+q^{8}+q^{6}\\\
0&0&0&1&q^{2}+1&q^{3}&q^{3}\\\ 0&0&0&0&1&q^{4}+q&q^{6}+q^{4}+q\\\
0&0&0&0&0&1&q^{2}+1\\\ 0&0&0&0&0&0&1\end{smallmatrix}\right),$

and finally $\mathcal{E}_{6}(\sigma_{z}(u))$ is computed as

$\left(\\!\\!\begin{smallmatrix}1&q^{13}+q^{11}+q^{7}&q^{22}+q^{20}+q^{16}+q^{14}+q^{10}&q^{28}+q^{26}&q^{33}+q^{31}+q^{29}+q^{27}&q^{35}+q^{33}&q^{35}+q^{33}\\\
0&1&q^{9}+q^{3}&q^{15}&q^{20}+q^{16}&q^{22}&q^{22}\\\
0&0&1&q^{12}+q^{10}+q^{6}&q^{17}+q^{15}+q^{13}+2q^{11}+q^{7}&q^{19}+q^{17}+q^{13}&q^{19}+q^{17}+q^{13}\\\
0&0&0&1&q^{5}+q&q^{7}&q^{7}\\\ 0&0&0&0&1&q^{8}+q^{2}&q^{12}+q^{8}+q^{2}\\\
0&0&0&0&0&1&q^{4}+1\\\ 0&0&0&0&0&0&1\end{smallmatrix}\\!\\!\\!\\!\right).$

One can then verify that
$C(q)\odot\mathcal{E}_{6}(\sigma_{z}(u))=Z\odot\mathcal{P}_{z}(u)(q^{2})$.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit.  Automatic sequences.  Cambridge University Press, Cambridge, 2003.  Theory, applications, generalizations.  doi:10.1017/CBO9780511546563.
  * [2] Jean-Paul Allouche and Jeffrey Shallit.  Additive properties of the evil and odious numbers and similar sequences, 2022.  arXiv:2112.13627.
  * [3] Jason P. Bell.  A generalization of Cobham’s theorem for regular sequences.  Séminaire Lotharingien de Combinatoire, 54A:B54Ap, 15 p., electronic only–B54Ap, 15 p., 2005.  URL: http://eudml.org/doc/222849.
  * [4] Somnath Bera and Kalpana Mahalingam.  Some algebraic aspects of Parikh $q$-matrices.  Internat. J. Found. Comput. Sci., 27(4):479–499, 2016.  doi:10.1142/S0129054116500118.
  * [5] Émilie Charlier, Narad Rampersad, and Jeffrey Shallit.  Enumeration and decidable properties of automatic sequences.  Internat. J. Found. Comput. Sci., 23(5):1035–1066, 2012.  doi:10.1142/S0129054112400448.
  * [6] Yong-Gao Chen and Bin Wang.  On additive properties of two special sequences.  Acta Arith., 110(3):299–303, 2003.  doi:10.4064/aa110-3-7.
  * [7] Traian-Florin Şerbănuţă.  Extending Parikh matrices.  Theoret. Comput. Sci., 310(1-3):233–246, 2004.  doi:10.1016/S0304-3975(03)00396-7.
  * [8] Gergely Dombi.  Additive properties of certain sets.  Acta Arith., 103(2):137–146, 2002.  doi:10.4064/aa103-2-3.
  * [9] Ömer Eğecioğlu.  A q-matrix encoding extending the Parikh matrix mapping.  In Proc. Int. Conf. on Computers and Communications (Oradea, Romania), 2004.
  * [10] Ömer Eğecioğlu and Oscar H. Ibarra.  A matrix $q$-analogue of the Parikh map.  In Exploring new frontiers of theoretical informatics. IFIP 18th world computer congress, TC1 3rd international conference on theoretical computer science (TCS2004), 22–27 August 2004, Toulouse, France., pages 125–138. Boston, MA: Kluwer Academic Publishers, 2004.
  * [11] P. Erdős, A. Sárközy, and V. T. Sós.  Problems and results on additive properties of general sequences. IV.  In Number theory (Ootacamund, 1984), volume 1122 of Lecture Notes in Math., pages 85–104. Springer, Berlin, 1985.  doi:10.1007/BFb0075753.
  * [12] Pamela Fleischmann, Marie Lejeune, Florin Manea, Dirk Nowotka, and Michel Rigo.  Reconstructing words from right-bounded-block words.  Int. J. Found. Comput. Sci., 32(6):619–640, 2021.  doi:10.1142/S0129054121420016.
  * [13] S. Fossé and G. Richomme.  Some characterizations of Parikh matrix equivalent binary words.  Inf. Process. Lett., 92(2):77–82, 2004.  doi:10.1016/j.ipl.2004.06.011.
  * [14] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete mathematics.  Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.  A foundation for computer science.
  * [15] Charles Knessl and Joseph B. Keller.  Partition asymptotics from recursion equation.  SIAM J. Appl. Math., 50(2):323–338, 1990.  doi:10.1137/0150020.
  * [16] Marie Lejeune, Julien Leroy, and Michel Rigo.  Computing the $k$-binomial complexity of the Thue-Morse word.  J. Combin. Theory Ser. A, 176:105284, 44, 2020.  doi:10.1016/j.jcta.2020.105284.
  * [17] M. Lothaire.  Combinatorics on Words.  Cambridge Mathematical Library. Cambridge University Press, 1997.  doi:10.1017/CBO9780511566097.
  * [18] Alexandru Mateescu, Arto Salomaa, Kai Salomaa, and Sheng Yu.  A sharpening of the Parikh mapping.  Theor. Inform. Appl., 35(6):551–564, 2001.  A tribute to Aldo de Luca.  doi:10.1051/ita:2001131.
  * [19] Alexandru Mateescu, Arto Salomaa, and Sheng Yu.  Subword histories and parikh matrices.  Technical Report 442, Turku Centre for Computer Science, 2002.  URL: http://oldtucs.abo.fi/publications/view/?pub_id=tMaYu02a.
  * [20] Alexandru Mateescu, Arto Salomaa, and Sheng Yu.  Subword histories and Parikh matrices.  J. Comput. System Sci., 68(1):1–21, 2004.  doi:10.1016/j.jcss.2003.04.001.
  * [21] Sophie Morier-Genoud and Valentin Ovsienko.  $q$-deformed rationals and $q$-continued fractions.  Forum Math. Sigma, 8:Paper No. e13, 55, 2020.  doi:10.1017/fms.2020.9.
  * [22] Antoine Renard, Michel Rigo, and Markus Whiteland.  Introducing $q$-deformed binomial coefficients of words, 2024.  arXiv.
  * [23] Gwenaël Richomme and Matthieu Rosenfeld.  Reconstructing Words Using Queries on Subwords or Factors.  In Petra Berenbrink et al., editors, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1–52:15, Dagstuhl, Germany, 2023.  doi:10.4230/LIPIcs.STACS.2023.52.
  * [24] Arto Salomaa.  Counting (scattered) subwords.  Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (81):165–179, 2003\.
  * [25] Arto Salomaa.  Subword histories and associated matrices.  Theoret. Comput. Sci., 407(1-3):250–257, 2008.  doi:10.1016/j.tcs.2008.05.023.
  * [26] Arto Salomaa.  Criteria for the matrix equivalence of words.  Theoret. Comput. Sci., 411(16-18):1818–1827, 2010.  doi:10.1016/j.tcs.2010.01.036.
  * [27] Jeffrey Shallit.  The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut.  London Mathematical Society Lecture Note Series. Cambridge University Press, 2022.  doi:10.1017/9781108775267.
  * [28] Richard P. Stanley and Fabrizio Zanello.  Some asymptotic results on q-binomial coefficients.  Annals of Combinatorics, 20:623–634, 2016.  doi:10.1007/s00026-016-0319-8.
  * [29] Wen Chean Teh, K. G. Subramanian, and Somnath Bera.  Order of weak $M$-relation and Parikh matrices.  Theoret. Comput. Sci., 743:83–92, 2018.  doi:10.1016/j.tcs.2018.04.042.