is equal to the number of regions of I1n intersecting the region x1 < x2 < · · · < xn

of Bn . Since Cn = I1n ∪ Bn , there follows from Proposition 5.14 the following result

of Wine and Freunde [24].

Proposition 5.17. The number u(n) of nonisomorphic n-element semiorders is

given by

1

u(n) = r(Cn ) = Cn .

n!

Figure 9 shows the nonisomorphic 3-element semiorders corresponding to the

regions of Cn intersecting the region x1 < x2 < · · · < xn of Bn .

We now come to the problem of determining r(I1n ), the number of semiorders

on [n].

LECTURE 5. FINITE FIELDS 75

x3 = x2 x3 = x2 + 1

3

3

2 2

1

1

x 2 = x1 +1

32

3

1

2

1

123

x2 = x1

Figure 9. The nonisomorphic 3-element semiorders as regions of C1n

Theorem 5.19. Fix distinct real numbers a1 , a2 , . . . , am > 0. Let An be the ar-

rangement in Rn with hyperplanes

xi ’ xj = a1 , . . . , am , i = j,

An :

and let A— = An ∪ Bn . De¬ne

n

xn

F (x) = r(An )

n!

n≥1

n

x

r(A— )

G(x) = .

n

n!

n≥1

Then F (x) = G(1 ’ e’x ).

Proof. Let c(n, k) denote the number of permutations w of n objects with k cycles

(in the disjoint cycle decomposition of w). The integer c(n, k) is known as a signless

Stirling number of the ¬rst kind and for ¬xed k has the exponential generating

76 R. STANLEY, HYPERPLANE ARRANGEMENTS

function

xn 1 k

log(1 ’ x)’1

(44) c(n, k) = .

n! k!

n≥0

For futher information, see e.g. [18, pp. 17“20][19, (5.25)].

We have

F (x) = G(1 ’ e’x ) ” G(x) = F (log(1 ’ x)’1 )

1 k

log(1 ’ x)’1

= r(Ak )

k!

k≥1

xn

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

n!

k≥1 n≥0

It follows that we need to show that

n

r(A— )

(45) = c(n, k)r(Ak ).

n

k=1

For simplicity we consider only the case m = 1 and a1 = 1, but the argument is

completely analogous in the general case. When m = 1 and a1 = 1 we have that

r(A— ) = n!Cn and that r(An ) is the number of semiorders on [n]. Thus it su¬ces

n

ρ

to give a map (P, w) ’ Q, where w ∈ Sk and P is a semiorder whose elements

are labelled by the cycles of w, and where Q is an unlabelled n-element semiorder,

such that ρ is n!-to-1, i.e., every Q appears exactly n! times as an image of some

(P, w).

Choose w ∈ Sn with k cycles in c(n, k) ways, and make these cycles the vertices

of a semiorder P in r(Ak ) ways. De¬ne a new poset ρ(P, w) as follows: if the cycle

(c1 , . . . , cj ) is an element of P , then replace it with an antichain with elements

c1 , . . . , cj . Given 1 ¤ c ¤ n, let C(c) be the cycle of w containing c. De¬ne

c < d in ρ(P, w) if C(c) < C(d) in P . We illustrate this de¬nition with n = 8 and

w = (1, 5, 2)(3)(6, 8)(4, 7):

(3) (4,7) 3 4 7

ρ

(1,5,2) (6,8) 1 5 2 6 8

Q = ρ ( P,w )

( P,w )

Given an unlabelled n-element semiorder Q, such as

LECTURE 5. FINITE FIELDS 77

we now show that there are exactly n! pairs (P, w) for which ρ(P, w) ∼ Q. Call a

=

pair of elements x, y ∈ Q autonomous if for all z ∈ Q we have

x < z ” y < z, x > z ” y > z.

Equivalently, the map „ : Q ’ Q transposing x, y and ¬xing all other z ∈ Q is an

automorphism of Q. Clearly the relation of being autonomous is an equivalence

relation. Partition Q into its autonomous equivalence classes. Regard the elements

of Q as being distinguished, and choose a bijection (labeling) • : Q ’ [n] (in n!

ways). Fix a linear ordering (independent of •) of the elements in each equivalence

class. (The linear ordering of the elements in each equivalence class in the diagram

below is left-to-right.)

5 4 1

3 6 2 8

7

In each class, place a left parenthesis before each left-to-right maximum, and

place a right parenthesis before each left parenthesis and at the end. (This is the

bijection Sn ’ Sn , w ’ w, in [18, p. 17].) Merge the elements c1 , c2 , . . . , cj

ˆ

(appearing in that order) between each pair of parentheses into a single element

labelled with the cycle (c1 , c2 , . . . , cj ).