2 ROLAND BACHER AND CHRISTOPHE REUTENAUER
Chapter 11 treats a few aspects of right congruences (mostly over {x,
y}∗)
a
combinatorial analogue of right ideals.
2. Catalan numbers and q-analogues
The n-th Catalan number Cn is classically given by the formula
1
n+1
(
2n
n
)
.
It counts several combinatorial objects, including trees, triangulations by diag-
onals of a convex polygon and Dyck paths. Exercise 6.19 of [St] consists of a
huge list of such objects. Carlitz and Riordan introduced a polynomial Cn(q)
of degree
n(n−1)
2
which reduces to Cn for q = 1 and is therefore called a q-
analogue of Cn. These polynomials are defined by the recursion C0(q) = 1 and
Cn+1(q) =
∑n
k=0
q(k+1)(n−k)Ck(q)Cn−k(q) and have a combinatorial interpretation
in terms of Dyck paths and their area.
Notice that a second polynomial q-analogue of Catalan numbers exists in the
literature. It is obtained by replacing every occurence of an integer i by its q-
analogue 1 + q + · · · + qi−1 in the classical definition
(2n)!
n!(n + 1)!
=
(n + 2)(n + 3) · · · (2n 1)(2n)
1 · 2 · · · (n 1) · n
of Cn. For all this, see [St] page 235.
3. Enumeration of right ideals
We denote by F x, y the ring of noncommutative polynomials in two variables
x, y over the field F = Fq with q elements. We write An(q) for the number of right
ideals with codimension n of F x, y .
Theorem 1. The polynomials A0(q),A1(q),... with An(q) counting the num-
ber of right-ideals of codimension n in Fq x, y satisfy the recursion A0(q) = 1 and
An+1(q) =
∑n
k=0
q(k+1)(n+2−k)Ak(q)An−k(q).
The polynomial An(q) is a q-analogue of the Catalan number Cn related to the
q-analogue Cn(q) of Carlitz and Riordan by the formula An(q) = qn(n+1)Cn(1/q).
The first few values of An(q) are A1(q) = q2, A2(q) = q5(1 + q), A3(q) =
q9(1 + 2q + q2 + q3), A4(q) = q14(1 + 3q + 3q2 + 3q3 + 2q4 + q5 + q6). It is easy
to verify that the degree of An(q) is n(n + 1) and that its lowest monomial is of
degree
n(n+3)
2
.
Theorem 1 will be proved in Section 9.
For the number Am,n(q) of right ideals of codimension n in Fq x1,...,xm we
have the following generalization:
Theorem 2. The number Am,n(q) of right ideals of codimension n in the free
associative algebra Fq x1,...,xm on m generators is a q-analogue of the Fuß-
Catalan number
1
(m−1)n+1
(
mn
n
)
enumerating m-ary trees with n interior vertices.
It satisfies the recurrence: Am,0(q) = 1 and
Am,n+1(q) =
n1+···+nm=n
Am,n1 (q) · · · Am,nm
(q)qN(n1,...,nm)
where N(n1,...,nm) = m + (2m 2)n1 + (2m 3)n2 + · · · (m 1)nm + (m
1)(n1n2 + n1n3 + · · · + n1nm + · · · + nm−1nm).
Section 10 contains the proof and a remark on computational aspects.
Previous Page Next Page