ρ ’1

(3) (7 , 6) (2) (8) 3 (7,6) (2) (8)

Q P

We have thus obtained a poset P whose elements are labelled by the cycles of

a permutation w ∈ Sn , such that ρ(P, w) = Q. For each unlabelled Q, there are

exactly n! pairs (P, w) (where the poset P is labelled by the cycles of w ∈ Sn )

for which ρ(P, w) ∼ Q. Since by Proposition 5.17 there are Cn nonisomorphic

=

n-element semiorders, we get

n

n!Cn = c(n, k)r(Ak ).

k=1

Note. Theorem 5.19 can also be proved using Burnside™s lemma (also called

the Cauchy-Frobenius lemma) from group theory.

To test one™s understanding of the proof of Theorem 5.19, consider why it

doesn™t work for all posets. In other words, let f (n) denote the number of posets on

n

f (n) x

[n] and g(n) the number of nonisomorphic n-element posets. Set F (x) = n!

and G(x) = g(n)xn . Why doesn™t the above argument show that G(x) = F (1 ’

78 R. STANLEY, HYPERPLANE ARRANGEMENTS

e’x )? Let Q = 2 + 2 (the unique obstruction to being an interval order, by

Proposition 5.15(a)). The autonomous classes have one element each. Consider the

two labelings • : Q ’ [4] and the corresponding ρ’1 :

2 4 2 4

ρ ’1

1 3 1 3

4 2 4 2

ρ ’1

3 1 3 1

We obtain the same labelled posets in both cases, so the proof of Theorem 5.19

fails. The key property of interval orders that the proof of Theorem 5.19 uses

implicitly is the following.

Lemma 5.6. If σ : P ’ P is an automorphism of the interval order P and

σ(x) = σ(y), then x and y are autonomous.

Proof. Assume not. Then there exists an element s ∈ P satisfying s > x, s > y (or

dually). Since σ(x) = y, there must exist t ∈ P satisfying t > y, t > x. But then

{x, s, y, t} form an induced 2 + 2, so by Proposition 5.15(a) P is not an interval

order.

Specializing m = 1 and a1 = 1 in Theorem 5.19 yields the following corollary,

due ¬rst (in an equivalent form) to Chandon, Lemaire and Pouget [8].

Corollary 5.12. Let f (n) denote the number of semiorders on [n] (or n-element

labelled semiorders). Then

xn

= C(1 ’ e’x ),

f (n)

n!

n≥0

where √

1’ 1 ’ 4x

C n xn =

C(x) = .

2x

n≥0

5.6. Intervals with generic lengths

A particularly interesting class of interval orders are those corresponding to intervals

with speci¬ed generic lengths · = ( 1 , . . . , n ). Intuitively, this means that the

intersection poset P (I· ) is as “large as possible.” One way to make this precise

is to say that · is generic if P (I· ) ∼ P (I· ), where · = ( 1 , . . . , n ) and the

=

i ™s are linearly independent over Q. Thus if · is generic, then the intersection

poset L(I· ) does not depend on ·, but rather only on n. In particular, r(I· ) does

not depend on · (always assuming · is generic). Hence by Proposition 5.16, the

number #P· of labelled interval orders corresponding to intervals I1 , . . . , In with

(Ii ) = i depends only on n. This fact is not at all obvious combinatorially, since

the interval orders themselves do depend on ·. For instance, it is easy to see that

· = (1, 1.0001, 1.001, 1.01, 1.1) is generic and that no corresponding interval order

LECTURE 5. FINITE FIELDS 79

can be isomorphic to 4 + 1. On the other hand, · = (1, 10, 100, 1000, 10000) is also

generic, but this time there is a corresponding interval order isomorphic to 4 + 1.

(See Exercise 17.)

The preceding discussion raises the question of computing #Pn when · is

generic. We write Gn for the corresponding interval order xi ’ xj = i , i = j,

since the intersection poset depends only on n. The following result is a nice appli-

cation of arrangements to “pure” enumeration; no proof is known except the one

sketched here.

Theorem 5.20. Let

xn x2 x3 x4 x5

= 1 + x + 3 + 19 + 195 + 2831 + · · · .

z= r(Gn )

n! 2! 3! 4! 5!

n≥0

De¬ne a power series

x2 x3 x4

y = 1 + x + 5 + 46 + 631 + · · ·

2! 3! 4

by 1 = y(2 ’ exy ). Equivalently,

’1

1 1 + 2x

y =1+ log .

1+x 1+x

Then z is the unique power series satisfying z /z = y 2 , z(0) = 1.

Note. The condition z /z = y 2 can be rewritten as z = exp y 2 dx.

Sketch of proof. Putting t = ’1 in Theorem 2.4 gives

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

(46) r(Gn ) =

B⊆Gn

B central

Given a central subarrangement B ⊆ Gn , de¬ne a digraph (directed graph) GB on

[n] by letting i ’ j be a (directed) edge if the hyperplane xi ’ xj = i belongs to B.

One then shows that as an undirected graph GB is bipartite, i.e., the vertices can be

partitioned into two subsets U and V such that all edges connect a vertex in U to a

vertex in V . The pair (U, V ) is called a vertex bipartition of GB . Moreover, if B is

a block of GB (as de¬ned preceding Proposition 4.11), say with vertex bipartition

(UB , VB ), then either all edges of B are directed from UB to VB , or all edges are

directed from VB to UB . It can also be seen that all such directed bipartite graphs

can arise in this way. It follows that equation (46) can be rewritten

r(Gn ) = (’1)n (’1)e(G)+c(G) 2b(G) ,

(47)

G

where G ranges over all (undirected) bipartite graphs on [n], e(G) denotes the

number of edges of G, and b(G) denotes the number of blocks of G.

Equation (47) reduces the problem of determining r(G) to a (rather di¬cult)

problem in enumeration, whose solution may be found in [14, §6].

5.7. Other examples

There are two additional arrangements related to the braid arrangement that in-

volve nice enumerative combinatorics. We merely repeat the de¬nitions here from

Lecture 1 and assemble some of their basic properties in Exercises 19“28.

80 R. STANLEY, HYPERPLANE ARRANGEMENTS

The Linial arrangement in K n is given by the hyperplanes xi ’ xj = 1, 1 ¤ i <

j ¤ n. It consists of “half” of the semiorder arrangement I1n . Despite its similarity

to I1n , it is considerably more di¬cult to obtain its characteristic polynomial and

other enumerative invariants. Finally the threshold arrangement in K n is given by

the hyperplanes xi + xj = 0, 1 ¤ i < j ¤ n. It is a subarrangement of the Coxeter

arrangements A(Bn ) (=A(Cn )) and A(Dn ).

LECTURE 5. FINITE FIELDS 81

Exercises

(1) [2] Verify equation (37), viz.,