« t

n

x

= bn ,

n!

n≥0

xn xn

Put t = ’1 to get

where exp n≥1 cn n! = n≥0 bn n! .

« ’1

n n

x x

= bn ,

(’1)n r(An )

n! n!

n≥0 n≥0

from which it follows that

« ’t

xn xn

= (’1)n r(An )

χAn (t) .

n! n!

n≥0 n≥0

For a generalization of Theorem 5.17, see Exercise 10.

5.4. The Catalan arrangement

De¬ne the Catalan arrangement Cn in K n , where char(K) = 2, by

(xi ’ xj )(xi ’ xj ’ 1)(xi ’ xj + 1).

QCn (x) =

1¤i<j¤n

Equivalently, the hyperplanes of Cn are given by

xi ’ xj = ’1, 0, 1, 1 ¤ i < j ¤ n.

Thus Cn has 3 n hyperplanes, and rank(Cn ) = n ’ 1.

2

Assume now that K = R. The symmetric group Sn acts on Rn by permuting

coordinates, i.e.,

w · (x1 , . . . , xn ) = (xw(1) , . . . , xw(n) ).

Here we are multiplying permutations left-to-right, e.g., (1, 2)(2, 3) = (1, 3, 2) (in

cycle form), so vw · ± = v · (w · ±). Both Bn and Cn are Sn -invariant, i.e., Sn

permutes the hyperplanes of these arrangements. Hence Sn also permutes their

regions, and each region xw(1) > xw(2) > · · · > xw(n) of Bn is divided “in the same

way” in Cn . In particular, if r0 (Cn ) denotes the number of regions of Cn contained

in some ¬xed region of Bn , then r(Cn ) = n!r0 (Cn ) . See Figure 3 for C3 in the

ambient space ker(x1 + x2 + x3 ), where the hyperplanes of B3 are drawn as solid

lines and the remaining hyperplanes as dashed lines. Each region of B3 contains

¬ve regions of C3 , so r(C3 ) = 6 · 5 = 30.

We can compute r(Cn ) (or equivalently r0 (Cn )) by a direct combinatorial ar-

gument. Let R0 denote the region x1 > x2 > · · · > xn of Bn . The regions of Cn

contained in R0 are determined by those i < j such that xi ’ xj < 1. We need only

specify the maximal intervals [i, j] such that xi ’ xj < 1, i.e., if a ¤ i < j ¤ b and

xa ’ xb < 1, then a = i and b = j. It is easy to see that any such speci¬cation of

maximal intervals determines a region of Cn contained in R0 . Thus r0 (Cn ) is equal

LECTURE 5. FINITE FIELDS 69

Figure 3. The Catalan arrangement C3 in ker(x1 + x2 + x3 )

to the number of antichains A of strict intervals of [n], i.e., sets A of intervals [i, j],

where 1 ¤ i < j ¤ n, such that no interval in A is contained in another. (“Strict”

means that i = j is not allowed.) It is known (equivalent to [19, Exer. 6.19(bbb)])

that the number of such antichains is the Catalan number Cn = n+1 2n . For 1

n

the sake of completeness we give a bijection between these antichains and a stan-

dard combinatorial structure counted by Catalan numbers, viz., lattice paths from

(0, 0) to (n, n) with steps (1, 0) and (0, 1), never rising above the line y = x ([19,

Exer. 6.19(h)]). Given an antichain A of intervals of [n], there is a unique lattice

path of the claimed type whose “outer corners” (a step (1, 0) followed by (0, 1))

consist of the points (j, i ’ 1) where [i, j] ∈ A, together with the points (i, i ’ 1)

where no interval in A contains i. Figure 4 illustrates this bijection for n = 8 and

A = {[1, 4], [3, 5], [7, 8]}.

We have therefore proved the following result. For a re¬nement, see Exercise 11.

Proposition 5.14. The number of regions of the Catalan arrangement Cn is given

by r(Cn ) = n!Cn . Each region of Bn contains Cn regions of Cn .

In fact, there is a simple formula for the characteristic polynomial χCn (t).

Theorem 5.18. We have

χCn (t) = t(t ’ n ’ 1)(t ’ n ’ 2)(t ’ n ’ 3) · · · (t ’ 2n + 1).

70 R. STANLEY, HYPERPLANE ARRANGEMENTS

86

65

52

40

Figure 4. A bijection corresponding to A = {[1, 4], [3, 5], [7, 8]}

Proof. Clearly the sequence (C1 , C2 , . . . ) is an ESA, so by Theorem 5.17 we have

« ’t

n n

x x

= (’1)n n!Cn

χCn (t)

n! n!

n≥0 n≥0

« ’t

(’1)n Cn xn

= .

n≥0

One method for expanding this series is to use the Lagrange inversion formula

[19, Thm. 5.4.2]. Let F (x) = a1 x + a2 x2 + · · · be a formal power series over K,

where char(K) = 0 and a1 = 0. Then there exists a unique formal power series

F ’1 = a’1 x + · · · satisfying

1

’1 ’1

F (F (x)) = F (F (x)) = x.

Let k, t ∈ Z. The Lagrange inversion formula states that

t

x

’1

t k t’k

(42) t[x ]F (x) = k[x ] .

F (x)

Let y = n≥0 (’1)n Cn xn+1 . By a fundamental property of Catalan numbers,

y 2 = ’y + x. Hence y = (x + x2 ) ’1 . Substitute t ’ n for k and apply equation

(42) to y = F (x), so F ’1 (x) = x + x2 :

t

x

t 2 t’n n

= (t ’ n)[x ]

(43) t[x ](x + x ) .

y

The right-hand side of (43) is just

(t ’ n)χCn (t)

’t

y

(t ’ n)[xn ] = .

x n!

LECTURE 5. FINITE FIELDS 71