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.