Parking Functions and Noncrossing Partitions

Richard P. Stanley^{∗} Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139

                rstan@math.mit.edu

Submitted: August 12, 1996; Accepted: November 12, 1996

Dedicated to Herb Wilf on the occasion of his sixty-fifth birthday

Abstract

A parking function is a sequence (a_{1}, …, a_{n}) of positive integers such that if b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} is the increasing rearrangement of a_{1}, …, a_{n}, then b_{i} ≤ i. A noncrossing partition of the set [n] = {1, 2, …, n} is a partition π of the set

[n] with the property that if a < b < c < d and some block B of π contains both a and c, while some block B′ of π contains both b and d, then B = B′. We establish some connections between parking functions and noncrossing partitions. A generating function for the flag f-vector of the lattice NC_{n+1} of noncrossing partitions of [n + 1] is shown to coincide (up to the involution ω on symmetric function) with Haiman’s parking function symmetric function. We construct an edge labeling of NC_{n+1} whose chain labels are the set of all parking functions of length n. This leads to a local action of the symmetric group 𝔖_{n} on NC_{n+1}.

MR primary subject number: 06A07 MR secondary subject numbers: 05A15, 05E05, 05E10, 05E25

the electronic journal of combinatorics 4, no. 2, (1997), #R20 2

1. Introduction. A parking function is a sequence (a_{1}, …, a_{n}) of positive integers such that if b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} is the increasing rearrangement of a_{1}, …, a_{n}, then b_{i} ≤ i.^{1} Parking functions were introduced by Konheim and Weiss [14] in connection with a hashing problem (though the term “hashing” was not used). See this reference for the reason (formulated in a way which now would be considered politically incorrect) for the terminology “parking function.” Parking functions were subsequently related to labelled trees and to hyperplane arrangements. For further information on these connections see [31] and the references given there. In this paper we will develop a connection between parking functions and another topic, viz., noncrossing partitions.

∗Partially supported by NSF grant DMS-9500714.

1Minor variations of this definition appear in the literature, but they are equivalent to the definition given here. For instance, in [31] parking functions are obtained from the definition given here by subtracting one from each coordinate.

A noncrossing partition of the set [n] = {1, 2, …, n} is a partition π of the set [n] (as defined e.g. in [29, p. 33]) with the property that if a < b < c < d and some block B of π contains both a and c, while some block B′ of π contains both b and d, then B = B′. The study of noncrossing partitions goes back at least to H. W. Becker [1], where they are called “planar rhyme schemes.” The systematic study of noncrossing partitions began with Kreweras [15] and Poupard [22]. For some further work on noncrossing partitions, see [5][21][25][28] and the references given there.

A fundamental property of the set of noncrossing partitions of [n] is that it can be given a natural partial ordering. Namely, we define π ≤ σ if every block of π is contained in a block of σ. In other words, π is a refinement of σ. Thus the poset NC_{n} of all noncrossing partitions of [n] is an induced subposet of the lattice Π_{n} of all partitions of [n] [29, Example 3.10.4]. In fact, NC_{n} is a lattice with a number of remarkable properties. We will develop additional properties of the lattice NC_{n} which connect it directly with parking functions.

2. The parking function symmetric function. Let P be a finite graded poset of rank n with ˆ0 and ˆ1 and with rank function ρ. (See [29, Ch. 3] for poset terminology and notation used here.) Let S be a subset of [n − 1] = {1, 2, …, n − 1}, and define α_{P} (S) to be the number of chains ˆ0 = t_{0} < t_{1} < ⋯ < t_{s} = ˆ1 of P such that S = {ρ(t_{1}), ρ(t_{2}), …, ρ(t_{s−1})}. The function α_{P} is called the flag f-vector of P. For S ⊆ [n − 1] further define

β_{P} (S) = ∑_{T ⊆S}(−1)^{|S−T |}α_{P} (T).

The function β_{P} is called the flag h-vector of P. Knowing α_{P} is the same as knowing β_{P} since

α_{P} (S) = ∑_{T ⊆S} β_{P} (T).

For further information on flag f-vectors and h-vectors (using a different terminology), see [29, Ch. 3.12].

There is a kind of generating function for the flag h-vector which is often useful in understanding the combinatorics of P. Regarding n as fixed, let S ⊆ [n − 1] and define a formal power series Q_{S} = Q_{S}(x) = Q_{S}(x_{1}, x_{2}, …) in the (commuting) indeterminates x_{1}, x_{2}, … by

Q_{S} = ∑_{{i_{1}≤i_{2}≤···≤in \atop i_{j} <i_{j+1} if j∈S}} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}}.

Q_{S} is known as Gessel’s quasisymmetric function [10] (see also [16, §5.4][18][24, Ch. 9.4]). The functions Q_{S}, where S ranges over all subsets of [n − 1], are linearly independent over any field. For our ranked poset P we then define

F_{P} = ∑_{S⊆[n−1]} β_{P} (S)Q_{S}.

This definition (in a different but equivalent form) was first suggested by R. Ehrenborg [6, Def. 4.1] and is further investigated in [30]. One of the results of [30] (Thm. 1.4) is the following proposition (which is equivalent to a simple generalization of [29, Exercise 3.65]).

2.1 Proposition. Let P be as above. If every interval [u, v] of P is ranksymmetric (i.e., [u, v] has as many elements of rank i as of corank i), then F_{P} is a symmetric function of x_{1}, x_{2}, . . ..

We now consider the case P = NC_{n+1}. (We take NC_{n+1} rather than NC_{n} because NC_{n+1} has rank n.) It is well-known that every interval in NC_{n+1} is self-dual and hence rank-symmetric. (This follows from the fact that NC_{n+1} is itself self-dual [15, §3][27, Thm. 1.1] and that every interval of NC_{n+1} is a product of NC_{i}’s [21, §1.3].) Hence F_{NC_{n+1}} is a symmetric function, and we can ask whether it is already known. In fact, F_{NC_{n+1}} has previously appeared in connection with parking functions, as stated below in Theorem 2.3. First we provide some background information related to parking functions.

Let P_{n} denote the set of all parking functions of length n. The symmetric group 𝔖_{n} acts on P_{n} by permuting coordinates. Let PF_{n} = PF_{n}(x) denote the Frobenius characteristic of the character of this action [17, Ch. 1.7]. Thus if

PF_{n} = ∑_{λ⊢n} τ_{λ,n}s_{λ}

is the expansion of PF_{n} in terms of Schur functions, then τ_{λ,n} is the multiplicity of the irreducible character of 𝔖_{n} indexed by λ in the action of 𝔖_{n} on P_{n}. The symmetric function PF_{n} was first considered in the context of parking functions by Haiman [13, §§2.6 and 4.1]. Following Haiman, we will give a formula for PF_{n} from which its expansion in terms of various symmetric function bases is immediate. The key observation (due to Pollack [8, p. 13] and repeated in [13, p. 28]) is the following (which we state in a slightly different form than Pollack). Let ℤ_{n+1} denote the set {1, 2, …, n+1}, with addition modulo n+1. Then every coset of the subgroup H of ℤ_{n+1}^{n} generated by (1, 1, …, 1) contains exactly one parking function. From this it follows easily that

PF_{n} = \frac{1}{n + 1}[t^{n}]H(t)^{n+1},  (1)

where [t^{n}]G(t) denotes the coefficient of t^{n} in the power series G(t), and where

H(t) = 1 + h_{1}t + h_{2}t^{2} + ⋯ = \frac{1}{(1 − x_{1}t)(1 − x_{2}t) ⋯},

the generating function for the complete symmetric functions h_{i}. (Throughout this paper we adhere to symmetric function terminology and notation as in Macdonald [17].)

The following proposition summarizes some of the properties of PF_{n} which follow easily from equation (1).

2.2 Proposition. (a) We have the following expansions.

PF_{n} = ∑_{λ⊢n}(n + 1)^{ℓ(λ)−1}z_{λ}^{−1}p_{λ}  (2)
= ∑_{λ⊢n} \frac{1}{n + 1}s_{λ}(1^{n+1})s_{λ}  (3)

= ∑_{λ⊢n} \frac{1}{n + 1} [∏_{i} \binom{λ_{i} + n}{n}] m_{λ}  (4)

= ∑_{λ⊢n} \frac{n(n − 1) ⋯ (n − ℓ(λ) + 2)}{m_{1}(λ)! ⋯ m_{n}(λ)!}h_{λ}.  (5)

ωPF_{n} = ∑_{λ⊢n} \frac{1}{n + 1} [∏_{i} \binom{n + 1}{λ_{i}}] m_{λ}.  (6)

Here s_{λ}(1^{n+1}) denotes s_{λ} with n+1 variables set equal to 1 and the others to 0, and is evaluated explicitly e.g. in [17, Example 4, p. 45]. Moreover, ℓ(λ) is the number of parts of λ; z_{λ} is as in [17, p. 24]; m_{i}(λ) denotes the number of parts of λ equal to i; and ω is the standard involution [17, pp. 21–22] on symmetric functions.

(b) We also have that

∑_{n≥0} PF_{n} t^{n+1} = (tE(−t))^{⟨−1⟩} ,  (7)

where E(t) = ∑_{n≥0} e_{n}t^{n}, e_{n} denotes the nth elementary symmetric function, and ^{⟨−1⟩} denotes compositional inverse.

Proof. (a) Let C(x, y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1}, the well-known “Cauchy product.” Then H(t)^{n+1} is obtained by setting n + 1 of the y_{i}’s equal to t and the others equal to 0. From this all the expansions in (a) follow from (1) and well-known expansions for C(x, y) and ω_{x}C(x, y) (where ω_{x} denotes ω acting on the x variables only). To give just one example (needed in the first proof of Theorem 2.3), we have

ω_{x}C(x, y) = ∑_{λ} m_{λ}(x)e_{λ}(y).

Hence

ωPF_{n} = ∑_{λ⊢n} \frac{1}{n + 1}e_{λ}(1^{n+1})m_{λ}.

Equation (6) now follows from the simple fact that e_{k}(1^{n+1}) = \binom{n+1}{k}. We should point out that (2) appears (in a dual form) in [11, (9)], (3) appears in [13, (28)], and (5) appears (again in dual form) in [13, (82)][17, Example 24(a), p. 35]. A q-analogue of PF_{n} and of much of our Proposition 2.2 appears in [9].

(b) This is an immediate consequence of (1), the fact that

\frac{1}{H(t)} = E(−t),  (8)

and the Lagrange inversion formula, as in [13, §4.1]. See also [17, Examples 2.24–2.25, pp. 35–36]. □

Let P be a Cohen-Macaulay poset with ˆ0 and ˆ1 such that every interval is rank-symmetric. Thus F_{P} is a symmetric function. In [30, Conj. 2.3] it was conjectured that F_{P} is Schur positive, i.e., a nonnegative linear combination of Schur functions. Equation (3) confirms this conjecture in the case P = NC_{n+1}. However, it turns out that the conjecture is in fact false. A counterexample is provided by the following poset P. The elements of P consist of all integer vectors (a_{1}, a_{2}, b_{1}, b_{2}, b_{3}, b_{4}) such that 0 ≤ a_{1} ≤ 5, 0 ≤ a_{2} ≤ 1, 0 ≤ b_{1} ≤ 3, 0 ≤ b_{2}, b_{3}, b_{4} ≤ 1, and a_{1} + a_{2} = b_{1} + b_{2} + b_{3} + b_{4}, ordered componentwise. It can be shown that P is lexicographically shellable and hence Cohen-Macaulay, and it is easy to see that P is locally rank-symmetric (even locally self-dual). Moreover,

F_{P} = s_{6} + 7s_{51} + 6s_{42} + 2s_{33} + 18s_{411} + 10s_{321} − s_{222} + 20s_{3111} + 5s_{2211} + 8s_{21111}.

The symmetric functions PF_{n} also have an unexpected connection with the multiplication of conjugacy classes in the symmetric group (the work of Farahat-Higman [7]). For further details see [11][17, Ch. I, Example 7.25, pp. 132–134]. This connection was exploited by Goulden and Jackson [11] to compute some connection coefficients for the symmetric group.

The expansion (5) of PF_{n} in terms of the h_{λ}’s has a simple interpretation in terms of parking functions. Suppose that a = (a_{1}, …, a_{n}) ∈ P_{n}. Let r_{1}, …, r_{k} be the positive multiplicities of the elements of the multiset {a_{1}, …, a_{n}} (so r_{1} + ⋯ + r_{k} = n). Then the action of 𝔖_{n} on the orbit 𝔖_{n}a has characteristic h_{r_{1}} ⋯ h_{r_{k}}. For instance, a set of orbit representatives in the case n = 3 is (1, 1, 1), (2, 1, 1), (3, 1, 1), (2, 2, 1), and (3, 2, 1). Hence PF_{3} = h_{3} +h_{2}h_{1} +h_{2}h_{1} + h_{2}h_{1} + h_{1}^{3} = h_{3} + 3h_{21} + h_{111}. In general it follows that the coefficient q_{λ} of h_{λ} in PF_{n} is equal to the number of orbits of parking functions of length n such that the terms of their elements have multiplicities λ_{1}, λ_{2}, … (in some order). Equation (5) then gives an explicit formula for this number. The total number of parking functions whose terms have multiplicities λ_{1}, λ_{2}, … is q_{λ} times the size of the orbit, i.e., q_{λ}\binom{n}{λ_{1},λ_{2},...}.

We are now ready to discuss the connection between PF_{n} and noncrossing partitions. The basic result is the following.

2.3 Theorem. For any n ≥ 0 we have

F_{NC_{n+1}} = ωPF_{n}.

Proof. Let λ = (λ_{1}, …, λ_{ℓ}) be a partition of n with λ_{ℓ} > 0. It is immediate from the definition of F_{P} in Section 1 (see [30, Prop. 1.1]) that if F_{P} is symmetric and F_{P} = ∑_{λ} c_{λ}m_{λ}, then

c_{λ} = α_{P} (λ_{1}, λ_{1} + λ_{2}, …, λ_{1} + λ_{2} + ⋯ + λ_{ℓ−1}).  (9)

The proof now follows by comparing equation (6) with the evaluation of α_{NC_{n+1}}(S) due to Edelman [4, Thm. 3.2]. □

It follows from the above discussion that PF_{n} encodes in a simple way the flag f-vector and flag h-vector of NC_{n+1}, viz., (1) the coefficient of Q_{S} in the expansion of PF_{n} in terms of Gessel’s quasisymmetric function is equal to β_{NC_{n+1}}(S), and (2) if the elements of S ⊆ [n − 1] are j_{1} < ⋯ < j_{r} and if λ is the partition whose parts are the numbers j_{1}, j_{2} − j_{1}, j_{3} − j_{2}, …, n − j_{r}, then the coefficient of m_{λ} in the expansion of PF_{n} in terms of monomial symmetric functions is equal to α_{NC_{n+1}}(S). There is a further statistic on NC_{n+1} closely related to PF_{n}, namely, the number of noncrossing partitions of [n + 1] of type λ, i.e., with block sizes λ_{1}, λ_{2}, . . ..

2.4 Proposition. Let λ be a partition of n. The coefficient of h_{λ} in the expansion of PF_{n} in terms of complete symmetric functions is equal to the number u_{λ} of noncrossing partitions of type λ.

First proof. Compare equation (5) with the explicit value of the number of noncrossing partitions of type λ found by Kreweras [15, Thm. 4]. □

Second proof. Our second proof is based on the following noncrossing analogue of the exponential formula due to Speicher [28, p. 616]. (For a more general result, see [21].) Given a function f : ℕ → R (where R is a commutative ring with identity) with f(0) = 1, define a function g : ℕ → R by g(0) = 1 and

g(n) = ∑_{π={B_{1},...,B_{k}}∈NC_{n}} f(#B_{1}) ⋯ f(#B_{k}).  (10)

Let F (t) = ∑_{n≥0} f(n)t^{n}. Then

∑_{n≥0} g(n)t^{n+1} = (\frac{t}{F (t)})^{⟨−1⟩} .  (11)

In equation (10) take f(n) = h_{n}, the complete symmetric function. Then g(n) becomes ∑_{λ⊢n} u_{λ}h_{λ}. But Proposition 2.2(b), together with equations (11) and (8), shows that g(n) = PF_{n}, and the proof follows. □

Note the curious fact that Theorem 2.3 refers to NC_{n+1}, while Proposition 2.4 refers to NC_{n}. Proposition 2.4, together with the definition of PF_{n}, show that the number of noncrossing partitions of type λ ⊢ n is equal to the number of 𝔖_{n}-orbits of parking functions of length n and part multiplicities λ. It is easy to give a bijective proof of this fact (shown to me by R. Simion), which we omit.

3. An edge labeling of the noncrossing partition lattice. If P is a locally finite poset, then an edge of P is a pair (u, v) ∈ P ×P such that v covers u (i.e., u < v and no element t satisfies u < t < v). An edge labeling of P is a map Λ : E(P) → ℤ, where E(P) is the set of edges of P. Edge labelings of posets have many applications; in particular, if P has what is known as an ELlabeling, then P is lexicographically shellable and hence Cohen-Macaulay [2][3]. An EL-labeling of NC_{n+1} was defined by Björner [2, Example 2.9] and further exploited by Edelman and Simion [5]. Here we define a new labeling, which up to an unimportant reindexing is EL and is intimately related to parking functions.

Let (π, σ) be an edge of NC_{n+1}. Thus σ is obtained from π by merging together two blocks B and B′. Suppose that min B < min B′, where min S denotes the minimum element of a finite set S of integers. Define

Λ(π, σ) = max{i ∈ B : i < B′},  (12)

where i < B′ denotes that i is less than every element of B′. For instance, if B = {2, 4, 5, 15, 17} and B′ = {7, 10, 12, 13}, then Λ(π, σ) = 5. Note that Λ(π, σ) always exists since min B < B′.

The labeling Λ of the edges of NC_{n+1} extends in a natural (and well-known) way to a labeling of the maximal chains. Namely, if 𝔪 : ˆ0 = π_{0} < π_{1} < ⋯ < π_{n} = ˆ1 is a maximal chain of NC_{n+1}, then set

Λ(𝔪) = (Λ(π_{0}, π_{1}), Λ(π_{1}, π_{2}), …, Λ(π_{n−1}, π_{n})).

3.1 Theorem. The labels Λ(𝔪) of the maximal chains of NC_{n+1} consist of the parking functions of length n, each occuring once.

Proof. If Λ(π_{j}, π_{j+1}) = i, then the block of π_{j+1} containing i also contains an element k > i. Hence the number of j for which Λ(π_{j}, π_{j+1}) = i cannot exceed n + 1 − i, from which it follows that Λ(𝔪) is a parking function.

Suppose that 𝔪 and 𝔪′ are maximal chains of NC_{n+1} for which Λ(𝔪) = Λ(𝔪′). We will prove by induction on n that 𝔪 = 𝔪′. The assertion is clear for n = 0. Assume true for n − 1. Let the elements of 𝔪 be ˆ0 = π_{0} < π_{1} < ⋯ < π_{n} = ˆ1. Suppose that Λ(𝔪) = (a_{1}, …, a_{n}). Let r = max{a_{i} : 1 ≤ i ≤ n}, and let s = max{i : a_{i} = r}. We claim that one of the blocks of π_{s−1} is just the singleton set {r + 1}. If r and r + 1 are in the same block of π_{s−1}, then we can’t have Λ(π_{s−1}, π_{s}) = r, contradicting a_{s} = r. Hence r and r + 1 are in different blocks of π_{s−1}. If the block B of π_{s−1} containing r + 1 contained some element t < r, then by the noncrossing property and the fact that a_{s} = r we have that B is merged with the block B_{1} of π_{s−1} containing r to get π_{s}. But min B ≤ t < r ∈ B_{1}, contradicting a_{s} = r. Hence every element of B is greater than r. If B contained some element t > r + 1, then (since r + 1 = min B) we would have a_{k} = r + 1 for some k < r, contradicting maximality of r. This proves the claim.

We next claim that π_{s} is obtained from π_{s−1} by merging the block B_{1} containing r with the block {r + 1}. Otherwise (since a_{s} = r) π_{s} is obtained by merging B_{1} with some block B_{2} all of whose elements are greater than r + 1. For some t > s we must obtain π_{t} from π_{t−1} by merging the block B_{3} containing r + 1 with the block B_{4} containing r. Now B_{3} can’t contain an element less than r + 1 by the noncrossing property of π_{s−1} (since B_{4} contains both r and an element greater than r + 1). It follows that Λ(π_{t−1}, π_{t}) = r, contradicting the maximality of s and proving the claim.

It is now clear by induction that the chain 𝔪 can be uniquely recovered from the parking function Λ(𝔪) = (a_{1}, …, a_{n}). Namely, let a′ be the sequence obtained from Λ(𝔪) by removing a_{s}. Then a′ is a parking function of length n − 1. By induction there is a unique maximal chain 𝔪^{∗} : ˆ0 = π_{0}^{∗} < π_{1}^{∗} < ⋯ < π_{n−1}^{∗} = ˆ1 of NC_{n} such that Λ(𝔪^{∗}) = a′. By the discussion above we can then obtain 𝔪 uniquely from 𝔪^{∗} by (1) replacing each element i > r of the ambient set [n] with i + 1, (2) adjoining a singleton block {r + 1} to each π_{i}^{∗} for i ≤ s − 1, (3) inserting between π_{s−1}^{∗} and π_{s}^{∗} a new element obtained from π_{s−1}^{∗} by merging the block containing r with the singleton block {r + 1}, and (4) for i > s adjoining the element r + 1 to the block of π_{i}^{∗} containing r. Hence we have shown that if Λ(𝔪) = Λ(𝔪′), then 𝔪 = 𝔪′. But it is known [15, Cor. 5.2][4, Cor. 3.3] that NC_{n+1} has (n + 1)^{n−1} maximal chains, which is just the number of parking functions of length n [14, Lemma 1 and §6][8]. Thus every parking function of length n occurs exactly once among the sequences Λ(𝔪), and the proof is complete. □

The above proof of the injectivity of the map Λ from maximal chains to parking functions is reminiscent of the proof [20, p. 5] that the Prüfer code of a labelled tree determines the tree. Our proof “cheated” by using the fact that the number of maximal chains is the number of parking functions. We only gave a direct proof of the injectivity of Λ. However, our proof actually suffices to show also surjectivity since the argument of the above paragraph is valid for any parking function, the key point being that removing an occurrence of the largest element of a parking function preserves the property of being a parking function.

If we define a new labeling Λ^{∗} of NC_{n+1} by

Λ^{∗}(π, σ) = |π| − Λ(π, σ),

where |π| is the number of blocks of π, then it is easy to check (using the fact that every interval of NC_{n+1} is a product of NC_{i}’s) that every interval [π, τ] has a unique maximal chain 𝔪 : π = π_{0} < π_{1} < ⋯ < π_{j} = τ such that

Λ^{∗}(π_{0}, π_{1}) ≤ Λ^{∗}(π_{1}, π_{2}) ≤ ⋯ ≤ Λ^{∗}(π_{k−1}, π_{k}).

In other words, Λ^{∗} is an R-labeling in the sense of [29, Def. 3.13.1]. Moreover, this maximal chain 𝔪 has the lexicographically least label Λ^{∗}(𝔪) of any maximal chain of the interval [π, τ]. Thus Λ^{∗} is in fact an EL-labeling, as defined in [2, Def. 2.2] (though there it is called just an “L-labeling.”). For the significance of the EL-labeling property, see the first paragraph of this section. Here we will just be concerned with the weaker R-labeling property.

Define the descent set D(a) of a parking function a = (a_{1}, …, a_{n}) by

D(a) = {i : a_{i} > a_{i+1}}.

From the fact that Λ^{∗} is an R-labeling and [29, Thm. 3.13.2], we obtain the following proposition.

3.2 Proposition. (a) Let S ⊆ [n − 1]. The number of parking functions a of length n satisfying D(a) = S is equal to β_{NC_{n+1}}([n − 1] − S).

(b) Let S ⊆ [n−1]. The number of parking functions a of length n satisfying D(a) ⊇ S is equal to α_{NC_{n+1}}([n − 1] − S). This number is given explicitly by [4, Thm. 3.2] or by equations (4) and (9).

The labeling Λ is closely related to a bijection between the maximal chains of NC_{n+1} and labelled trees, different from the earlier bijection of Edelman [4, Cor. 3.3]. Let 𝔪 : ˆ0 = π_{0} < π_{1} < ⋯ < π_{n} = ˆ1 be a maximal chain of NC_{n+1}. Define a graph Γ_{𝔪} on the vertex set [n+1] as follows. There will be an edge e_{i} for each 1 ≤ i ≤ n. Suppose that π_{i} is obtained from π_{i−1} by merging blocks B and B′ with min B < min B′. Then the vertices of e_{i} are defined to be Λ(π_{i−1}, π_{i}) and min B′. It is easy to see that Γ_{𝔪} is a tree. Root Γ_{𝔪} at the vertex 1 and erase the vertex labels. If v_{i} is the vertex of e_{i} farthest from the root, then move the label i of the edge e_{i} from e_{i} to the vertex v_{i}. Label the root with 0 and unroot the tree. We obtain a labelled tree T_{𝔪} on n+1 vertices, and one can easily check that the map 𝔪 ↦ T_{𝔪} is a bijection between maximal chains of NC_{n+1} and labelled trees on n + 1 vertices.

4. A local action of the symmetric group. Suppose that P is a graded poset of rank n with ˆ0 and ˆ1 such that F_{P} is a symmetric function. If F_{P} is Schur positive, then it is the Frobenius characteristic of a representation of 𝔖_{n} whose dimension is the number of maximal chains of P. Thus we can ask whether there is some “nice” representation of 𝔖_{n} on the vector space V_{P} (over a field of characteristic zero) whose basis is the set of maximal chains of P. This question was discussed in [30, §5]. A “nice” representation should somehow reflect the poset structure. With this motivation, an action of 𝔖_{n} on V_{P} is defined to be local [30, §5] if for every adjacent transposition σ_{i} = (i, i+1) and every maximal chain

𝔪 : ˆ0 = t_{0} < t_{1} < ⋯ < t_{n} = ˆ1,  (13)

we have that σ_{i}(𝔪) is a linear combination of maximal chains of the form t_{0} < t_{1} < ⋯ < t_{i−1} < t′_{i} < t_{i+1} < ⋯ < t_{n}, i.e., of maximal chains which agree with 𝔪 except possibly at t_{i}.

Now let P = NC_{n+1}. Every interval [π, τ] of NC_{n+1} of length two contains either two or three elements in its middle level. In the latter case, there are three blocks B_{1}, B_{2}, B_{3} of π such that τ is obtained from π by merging B_{1}, B_{2}, B_{3} into a single block. Moreover, any two of these blocks can be merged to form a noncrossing partition. Let π_{ij} be the noncrossing partition obtained by merging B_{i} and B_{j}, so that the middle elements of the interval [π, τ] are π_{12}, π_{13}, π_{23}. Exactly one of these partitions π_{ij} will have the property that Λ(π, π_{ij}) = Λ(π_{ij}, τ), where Λ is defined by (12). Let us call this partition π_{ij} the special element of the interval [π, τ]. Now define linear transformations σ′_{i} : V_{NC_{n+1}} → V_{NC_{n+1}}, 1 ≤ i ≤ n − 1 as follows. Let 𝔪 be a maximal chain of NC_{n+1} with elements ˆ0 = π_{0} < π_{1} < ⋯ < π_{n} = ˆ1.

Case 1. The interval [π_{i−1}, π_{i+1}] contains exactly two middle elements π_{i} and π′_{i}. Then set σ′_{i}(𝔪) = 𝔪′, where 𝔪′ is given by π_{0} < π_{1} < ⋯ < π_{i−1} < π′_{i} < π_{i+1} < ⋯ < π_{n}.

Case 2. The interval [π_{i−1}, π_{i+1}] contains exactly three middle elements, of which π_{i} is special. Then set σ′_{i}(𝔪) = 𝔪.

Case 3. The interval [π_{i−1}, π_{i+1}] contains exactly three middle elements π_{i}, π′_{i}, and π′′_{i}, of which π′′_{i} is special. Then set σ′_{i}(𝔪) = 𝔪′, where 𝔪′ is given by π_{0} < π_{1} < ⋯ < π_{i−1} < π′_{i} < π_{i+1} < ⋯ < π_{n}.

4.1 Proposition. The action of each σ′_{i} on V_{NC_{n+1}} defined above yields a local action of 𝔖_{n} on V_{NC_{n+1}}. Equivalently, there is a homomorphism φ : 𝔖_{n} → GL(V_{NC_{n+1}}) satisfying φ(σ_{i}) = σ′_{i}. The Frobenius characteristic of this action is given by PF_{n}.

Proof. Each maximal chain 𝔪 corresponds to a parking function Λ(𝔪) via Theorem 3.1. Thus the natural action of 𝔖_{n} on P_{n} defined in Section 2 may be “transferred” to an action ψ of 𝔖_{n} on the set of maximal chains of NC_{n+1}. It is easy to check that ψ and φ agree on the σ_{i}’s, and the proof follows. □

The action φ does not quite have the property mentioned at the beginning of this section that its characteristic is F_{NC_{n+1}}. By Theorem 2.3, the characteristic is actually ωF_{NC_{n+1}}. However, we only have to multiply φ by the sign character (equivalently, define a new action φ′ by φ′(σ_{i}) = −φ(σ_{i})) to get the desired property.

It is rather surprising that the simple “local” definition we have given of φ defines an action of 𝔖_{n}. Perhaps it would be interesting to look for some more examples. (We need to exclude trivial examples such as w(𝔪) = 𝔪 for all w ∈ 𝔖_{n} and all maximal chains 𝔪.) A few other examples appear in the next section and in [30, §5]. A further example (the posets of shuffles of C. Greene [12]) is discussed in [26] together with the rudiments of a systematic theory of such actions, but much work needs to be done for a satisfactory understanding of local 𝔖_{n}-actions.

5. Generalizations. In this section we will briefly discuss two generalizations of what appears above. All proofs are entirely analogous and will be omitted. Fix an integer k ∈ ℙ. A k-divisible noncrossing partition is a noncrossing partition π for which every block size is divisible by k. Thus π is a noncrossing partition of a set [kn] for some n ≥ 0. Let NC_{n}^{(k)} be the poset of all k-divisible noncrossing partitions of [kn]. (NC_{n}^{(k)} is actually a join-semilattice of NC_{kn}. It has ˆ1 but not a ˆ0 when k > 1.) The combinatorial properties of the poset NC_{n}^{(k)} were first considered by Edelman [4, §4]. If a pair (π, σ) is an edge of NC_{n}^{(k)} (i.e., σ covers π in NC_{n}^{(k)}), then (π, σ) is an edge of NC_{n}. Hence the edge-labeling Λ of NC_{n} restricts to an edge-labeling of NC_{n}^{(k)}.

Define a k-parking function of length n to be a sequence (a_{1}, …, a_{n}) of positive integers such that if b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} is the increasing rearrangement of a_{1}, …, a_{n}, then b_{i} ≤ ki. Let P_{n}^{(k)} denote the set of all k-parking functions of length n. The argument of Pollack mentioned in Section 2 that #P_{n} = (n + 1)^{n−1} easily extends to P_{n}^{(k)}. Namely, let ℤ_{k(n+1)} denote the set {1, 2, …, k(n+ 1)} with addition modulo k(n + 1). Then every coset of the subgroup H of ℤ_{k(n+1)}^{n} generated by (1, 1, …, 1) contains exactly k k-parking functions. Hence

#P_{n}^{(k)} = k(k(n + 1))^{n−1}. The symmetric group 𝔖_{n} acts on P_{n}^{(k)} by permuting coordinates, and we can consider its Frobenius characteristic PF_{n}^{(k)} just as we did for P_{n}. The above generalization of Pollack’s argument shows that

PF_{n}^{(k)} = \frac{1}{n + 1}[t^{n}]H(t)^{k(n+1)}.

Proposition 2.2 generalizes straightforwardly to the case of PF_{n}^{(k)}. In particular, Proposition 2.2(b) takes the form

∑_{n≥0} PF_{n}^{(k)} t^{n+1} = (tE(−t)^{k})^{⟨−1⟩} .

Theorem 3.1 generalizes as follows.

5.1 Theorem. The labels Λ(𝔪) of the maximal chains of NC_{n+1}^{(k)} consist of the k-parking functions of length n, each occuring once.

Proposition 3.2 requires some modification when extended to k-parking functions because the posets NC_{n+1}^{(k)} do not have a ˆ0 when k > 1. For these posets we regard the minimal elements as having rank 0, and we define α_{NC{(k) \atop n+1}}(S)

and β_{NC{(k) \atop n+1}}(S) for S ⊆ \{0, 1, …, n − 1\}. Thus for instance α_{NC{(k) \atop n+1}}(∅) = β_{NC{(k) \atop n+1}}(∅) = 1, and α_{NC{(k) \atop n+1}}(0) is the number of minimal elements of NC_{n+1}^{(k)}.

Write [0, n − 1] = {0, 1, …, n − 1}.

5.2 Proposition. (a) Let S ⊆ [n − 1]. The number of k-parking functions a of length n satisfying D(a) = S is equal to

β_{NC{(k) \atop n+1}}([n − 1] − S) + β_{NC{(k) \atop n+1}}([0, n − 1] − S).

(b) Let S ⊆ [n − 1]. The number of k-parking functions a of length n satisfying D(a) ⊇ S is equal to α_{NC{(k) \atop n+1}}([0, n − 1] − S). This number is given

explicitly by [4, Thm. 4.2].

Note, however, that there does not seem to be a nice generalization of Theorem 2.3. The quasisymmetric function F_{NC{(k) \atop n+1}} is not a symmetric function when k > 1, and we know of no simple connection between the flag f-vector of NC_{n+1}^{(k)} and the symmetric function PF_{n}^{(k)}, nor between the number of kdivisible noncrossing partitions of a given type and PF_{n}^{(k)}.

Proposition 4.1 extends straightforwardly to NC_{n+1}^{(k)}. The natural action of 𝔖_{n} on P_{n}^{(k)} is transferred via Theorem 5.1 to an action on V_{NC{(k) \atop n+1}}. This action is a permutation representation on the maximal chains, and is readily seen to be local. Its characteristic is PF_{n}^{(k)}.

There is a different generalization of noncrossing partitions due to Reiner [23] (a special case had earlier appeared in a different guise in [19], as explained in [23]) that we have not looked at very closely. Reiner regards ordinary noncrossing partitions as corresponding to the root system A_{n} and constructs analogues for the root systems B_{n} and D_{n}. Actually, for every subset S ⊆ [n] he constructs a lattice NC_{n}^{BD}(S) interpolating between the B_{n} analogue (the case S = ∅) and the D_{n} analogue (the case S = [n]). The lattices NC_{n}^{BD}(S) do not always have self-dual intervals [23, Remark on p. 13], but at least every interval is rank-symmetric. Thus by Proposition 2.1, this implies that NC_{n}^{BD}(S) is a symmetric function. This symmetric function only depends on the cardinality s of S, so we write F_{n}^{BD}(s) for F_{NC_{n}^{BD}(S)}. We also write F_{n}^{B} for F_{n}^{BD}(0).

Let [n]^{n} denote the set of all sequences (a_{1}, …, a_{n}) of positive integers with a_{i} ≤ n. We call such a sequence a B_{n}-parking function, for the following reason. Let PF_{n}^{B} be the Frobenius characteristic of the action of 𝔖_{n} on [n]^{n} obtained by permuting coordinates. It follows from [23, Prop. 7] that

F_{n}^{B} = ωPF_{n}^{B}.

Thus in analogy with Theorem 2.3 it makes sense to think of the elements of [n]^{n} as B_{n}-parking functions. Reiner’s result [23, Prop. 7] makes it easy to give an analogue of Proposition 2.2. Let us simply mention the formula

PF_{n}^{B} = [t^{n}]H(t)^{n},

from which the analogues of all parts of Proposition 2.2 follow easily. In particular, the analogue of Proposition 2.2(b) takes the form

∑_{n≥1} PF_{n}^{B} \frac{t^{n}}{n} = log \frac{(tE(−t))^{⟨−1⟩}}{t} .  (14)

Comparing Proposition 2.2 with equation (14) yields the curious result that

exp ∑_{n≥1} PF_{n}^{B} \frac{t^{n}}{n} = ∑_{n≥0} PF_{n} t^{n}.

What is missing from the analogy between A_{n} and B_{n} noncrossing partitions is the analogue of Theorem 3.1, i.e., a labeling of NC_{n+1}^{B} such that the labels of the maximal chains are the B_{n}-parking functions. We have not looked at this question and recommend it as an interesting open problem.

For the general case of NC_{n}^{BD}(S), it follows from [23, Thm. 11] that

F_{n}^{BD}(s) = F_{n}^{B} − s · PF′_{n},

where PF′_{n} is the Frobenius characteristic of the action of 𝔖_{n} on all sequences (a_{1}, …, a_{n}) of positive integers whose increasing rearrangement b_{1} ≤ ⋯ ≤ b_{n} satisfies b_{1} = 1 and b_{i} ≤ i − 1 for 2 ≤ i ≤ n. We have not considered further properties of the symmetric function F_{n}^{BD}(s).

References

[1] H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952), 39.

[2] A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159–183.

[3] A. Björner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), 323–341.

[4] P. H. Edelman, Chain enumeration and non-crossing partitions, Discrete Math. 31 (1980), 171–180.

[5] P. H. Edelman and R. Simion, Chains in the lattice of noncrossing partitions, Discrete Math. 126 (1994), 107–119.

[6] R. Ehrenborg, On posets and Hopf algebras, Advances in Math. 119 (1996), 1–25.

[7] H. K. Farahat and G. Higman, The centres of symmetric group rings, Proc. Royal Soc. (A) 250 (1959), 212–221.

[8] D. Foata and J. Riordan, Mappings of acyclic and parking functions, aequationes math. 10 (1974), 10–22.

[9] A. M. Garsia and M. Haiman, A remarkable q, t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combinatorics 5 (1996), 191–244.

[10] I. Gessel, Multipartite P -partitions and inner products of skew Schur functions, Contemporary Math. 34 (1984), 289–301.

[11] I. P. Goulden and D. M. Jackson, Symmetric functions and Macdonald’s result for top connexion coefficients in the symmetric group, J. Algebra 166 (1994), 364–378.

[12] C. Greene, Posets of shuffles, J. Combinatorial Theory (A) 46 (1988), 191–206.

[13] M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Alg. Combinatorics 3 (1994), 17–76.

[14] A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966), 1266–1274.

[15] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), 333–350.

[16] D. Krob and J.-Y. Thibon, Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q = 0, Institut Blaise Pascal, Laboratoire Informatique Théorique et Programmation, preprint LITP 96/12, March, 1996.

[17] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second ed., Oxford University Press, Oxford, 1995.

[18] C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra 177 (1995), 967–982.

[19] C. Montenegro, The fixed point non-crossing partition lattices, preprint, 1993.

[20] J. W. Moon, Counting Labelled Trees, Canadian Mathematical Monographs, No. 1, Canadian Mathematical Congress, 1970.

[21] A. Nica and R. Speicher, A “Fourier transform” for multiplicative functions on non-crossing partitions, J. Algebraic Combinatorics, to appear.

[22] Y. Poupard, Étude et denombrement paralleles des partitions non croisées d’un cycle et des decoupage d’un polygone convexe, Discrete Math. 2 (1972), 279–288.

[23] V. Reiner, Non-crossing partitions for classical reflection groups, preprint dated March 1996. Available at the URL ftp://s6.math.umn.edu/pub/papers/reiner/ or by anonymous ftp.

[24] C. Reutenauer, Free Lie Algebras, Oxford University Press, Oxford, 1993.

[25] R. Simion, Combinatorial statistics on non-crossing partitions, J. Combinatorial Theory (A) 66 (1994), 270–301.

[26] R. Simion and R. Stanley, Flag-symmetry of the poset of shuffles and a local action of the symmetric group, in preparation.

[27] R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), 193–206.

[28] R. Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994), 611–628.

[29] R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge, 1996 or 1997.

[30] R. Stanley, Flag-symmetric and locally rank-symmetric partially ordered sets, Electronic J. Combinatorics 3, R6 (1996), 22 pp.

[31] R. Stanley, Hyperplane arrangements, parking functions and tree inversions, in Festschrift in Honor of Gian-Carlo Rota, Birkhäuser, Boston/Basel/Berlin, to appear.