p

and p choices for ±1 , so it follows from Theorem 5.15 that χSn (t) = t(t ’ n)n’1 .

We obtain the following corollary immediately from Theorem 2.5.

Corollary 5.11. We have r(Sn ) = (n + 1)n’1 and b(Sn ) = (n ’ 1)n’1 .

Note. Since r(Sn ) and b(Sn ) have such simple formulas, it is natural to ask

for a direct bijective proof of Corollary 5.11. A number of such proofs are known;

a sketch that r(Sn ) = (n + 1)n’1 is given in Exercise 3.

66 R. STANLEY, HYPERPLANE ARRANGEMENTS

Note. It can be shown that the cone cSn is not supersolvable for n ≥ 3 (Ex-

ercise 4) but is free in the sense of Theorem 4.14.

5.3. Exponential sequences of arrangements

The braid arrangement (in fact, any Coxeter arrangement) is highly symmetrical;

indeed, the group of linear transformations that preserves the arrangement acts

transitively on the regions. Thus all regions “look the same.” The Shi arrangement

lacks this symmetry, but it still possesses a kind of “combinatorial symmetry” that

allows us to express the characteristic polynomials χSn (t), for all n ≥ 1, in terms

of the number r(Sn ) of regions.

De¬nition 5.14. A sequence A = (A1 , A2 , . . . ) of arrangements is called an expo-

nential sequence of arrangements (ESA) if it satis¬es the following three conditions.

(1) An is in K n for some ¬eld K (independent of n).

(2) Every H ∈ An is parallel to some hyperplane H in the braid arrangement

Bn (over K).

(3) Let S be a k-element subset of [n], and de¬ne

AS = {H ∈ An : H is parallel to xi ’ xj = 0 for some i, j ∈ S}.

n

Then L(AS ) ∼ L(Ak ).

=

n

Examples of ESA™s are given by An = Bn or An = Sn . In fact, in these cases

we have AS ∼ Ak — K n’k .

n=

The combinatorial properties of ESA™s are related to the exponential formula

in the theory of exponential generating functions [19, §5.1], which we now review.

Informally, we are dealing with “structures” that can be put on a vertex set V such

that each structure is a disjoint union of its “connected components.” We obtain a

structure on V by partitioning V and placing a connected structure on each block

(independently). Examples of such structures are graphs, forests, and posets, but

not trees or groups. Let h(n) be the total number of structures on an n-set V (with

h(0) = 1), and let f (n) be the number that are connected. The exponential formula

states that

xn xn

(39) h(n) = exp f (n) .

n! n!

n≥0 n≥1

More precisely, let f : P ’ R, where R is a commutative ring. (For our purposes,

R = Z will do.) De¬ne a new function h : N ’ R by h(0) = 1 and

f (#B1 )f (#B2 ) · · · f (#Bk ).

(40) h(n) =

π={B1 ,...,Bk }∈Πn

Then equation (39) holds. A straightforward proof can be given by considering the

expansion

xn xn

exp f (n) = exp f (n)

n! n!

n≥1 n≥1

«

kn

x

f (n)k k .

=

n! k!

n≥1 k≥0

We omit the details (Exercise 5).

LECTURE 5. FINITE FIELDS 67

For any arrangement A in K n , de¬ne r(A) = (’1)n χA (’1). Of course if K = R

this coincides with the de¬nition of r(A) as the number of regions of A. We come

to the main result concering ESA™s.

Theorem 5.17. Let A = (A1 , A2 , . . . ) be an ESA. Then

« ’t

xn xn

= (’1)n r(An ) .

χAn (t)

n! n!

n≥0 n≥0

Example 5.13. For A = (B1 , B2 , . . . ) Theorem 5.17 asserts that

« ’t

n n

x x

= (’1)n n! ,

t(t ’ 1) · · · (t ’ n + 1)

n! n!

n≥0 n≥0

as immediately follows from the binomial theorem. On the other hand, if A =

(S1 , S2 , . . . ), then we obtain the much less obvious identity

« ’t

n n

x x

= (’1)n (n + 1)n’1 .

t(t ’ n)n’1

n! n!

n≥0 n≥0

Proof of Theorem 5.17. By Whitney™s theorem (Theorem 2.4) we have for

any arrangement A in K n that

(’1)#Btn’rank(B) .

χA (t) =

B⊆A

B central

Let A = (A1 , A2 , . . . ), and let B ⊆ An for some n. De¬ne π(B) ∈ Πn to have blocks

that are the vertex sets of the connected components of the graph G on [n] with

edges

E(G) = {ij : ∃ xi ’ xj = c in B}.

(41)

De¬ne

(’1)#B tn’rk(B) .

χAn (t) =

˜

B⊆A

B central

π(B)=[n]

Then

(’1)#B tn’rk(B)

χAn (t) =

π={B1 ,...,Bk }∈Πn B⊆A

B central

π(B)=π

χA#B1 (t)χA#B2 (t) · · · χA#Bk (t).

= ˜ ˜ ˜

π={B1 ,...,Bk }∈Πn

Thus by the exponential formula (39),

xn xn

χAn (t) = exp χAn (t)

˜ .

n! n!

n≥0 n≥1

68 R. STANLEY, HYPERPLANE ARRANGEMENTS

But π(B) = [n] if and only if rk(B) = n ’ 1, so χAn (t) = cn t for some cn ∈ Z. We

˜

therefore get

xn xn

χAn (t) = exp t cn

n! n!