Crossings and Nestings of Matchings and Partitions

William Y.C. Chen^{1,2}, Eva Y.P. Deng^{3}, Rosena R.X. Du^{4} Richard P. Stanley^{5,6}, and Catherine H. Yan^{7,8} 1,4Center for Combinatorics, LPMC Nankai University, Tianjin 300071, P.R. China 3Department of Applied Mathematics Dalian University of Technology, Dalian, Liaoning 116024, P.R.China 5Department of Mathematics Massachusetts Institute of Technology, Cambridge, MA 02139 7Department of Mathematics Texas A&M University, College Station, TX 77843 1chen@nankai.edu.cn, ^{3}dengyp@eyou.com, ^{4}du@nankai.edu.cn, 5rstan@math.mit.edu, ^{7}cyan@math.tamu.edu January 12, 2005

Abstract

We present results on the enumeration of crossings and nestings for matchings and set partitions. Using a bijection between partitions and vacillating tableaux, we show that if we fix the sets of minimal block elements and maximal block elements, the crossing number and the nesting number of partitions have a symmetric joint distribution. It follows that the crossing numbers and the nesting numbers distributed symmetrically over all partitions of [n], as well as over all matchings on [2n]. As a corollary, the number of k-noncrossing partitions is equal to the number of k-nonnesting partitions. The same is also true for matchings. An application is given to the enumeration of matchings with no k-crossing (or with no k-nesting).

Mathematics Subject Classification. Primary 05A18, secondary 05E10, 05A15. Key words and phrases. Crossing, nesting, partition, vacillating tableau.

2partially supported by the 973 Project on Mathematical Mechanization, the National Science Foundation, the Ministry of Education and the Ministry of Science and Technology of China.

6Partially supported by NSF grant #DMS-9988459.

8Partially supported by NSF grant #DMS-0245526 and a Sloan Fellowship.

1 Introduction

A (complete) matching on [2n] = {1, 2, …, 2n} is a partition of [2n] of type (2, 2, …, 2). It can be represented by listing its n blocks, as {(i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{n}, j_{n})} where i_{r} < j_{r} for 1 ≤ r ≤ n. Two blocks (also called arcs) (i_{r}, j_{r}) and (i_{s}, j_{s}) form a crossing if i_{r} < i_{s} < j_{r} < j_{s}; they form a nesting if i_{r} < i_{s} < j_{s} < j_{r}. It is well-known that the number of matchings on [2n] with no crossings (or with no nestings) is given by the n-th Catalan number

C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

See [22, Exercise 6.19] for many combinatorial interpretations of Catalan numbers, where item (o) is for noncrossing matchings, and item (ww) can be viewed as nonnesting matchings, in which the blocks of the matching are the columns of the standard Young tableaux of shape (n, n). Nonnesting matchings are also one of the items of [23].

Let k ≥ 2 be an integer. A k-crossing of a matching M is a set of k arcs (i_{r_{1}}, j_{r_{1}}), (i_{r_{2}}, j_{r_{2}}), …, (i_{r_{k}}, j_{r_{k}}) of M such that i_{r_{1}} < i_{r_{2}} < ⋯ < i_{r_{k}} < j_{r_{1}} < j_{r_{2}} < ⋯ < j_{r_{k}}. A matching without any k-crossing is a k-noncrossing matching. Similarly, a k-nesting is a set of k arcs (i_{r_{1}}, j_{r_{1}}), (i_{r_{2}}, j_{r_{2}}), …, (i_{r_{k}}, j_{r_{k}}) of M such that i_{r_{1}} < i_{r_{2}} < ⋯ < i_{r_{k}} < j_{r_{k}} < ⋯ < j_{r_{2}} < j_{r_{1}}. A matching without any k-nesting is a k-nonnesting matching.

Enumeration on crossings/nestings of matchings has been studied for the cases k = 2 and k = 3. For k = 2, in addition to the above results on Catalan numbers, the distribution of the number of 2-crossings has been studied by Touchard [26], and later more explicitly by Riordan [18], who gave a generating function. M. de Sainte-Catherine [7] proved that 2-crossings and 2-nestings are identically distributed over all matchings of [2n], i.e., the number of matchings with r 2-crossings is equal to the number of matchings with r 2-nestings.

The enumeration of 3-nonnesting matchings was first studied by D. Gouyou-Beauschamps in [9], in which he gave a bijection between involutions with no decreasing sequence of length 6 and pairs of noncrossing Dyck left factors by a recursive construction. His bijection is essentially a correspondence between 3-nonnesting matchings and pairs of noncrossing Dyck paths, where a matching can also be considered as a fixed-point-free involution. We observed that the number of 3-noncrossing matchings also equals the number of pairs of noncrossing Dyck paths, and a one-to-one correspondence between 3-noncrossing matchings and pairs of noncrossing Dyck paths can be built recursively.

In this paper, we extend the above results. Let cr(M) be maximal i such that M has a icrossing, and ne(M) the maximal j such that M has a j-nesting. Denoted by f_{n}(i, j) the number of matchings M on [2n] with cr(M) = i and ne(M) = j. We shall prove that f_{n}(i, j) = f_{n}(j, i). As a corollary, the number of matchings on [2n] with cr(M) = k equals the number of matchings M on [2n] with ne(M) = k.

Our construction applies to a more general structure, viz., partitions of a set. Given a partition P of [n], denoted by P ∈ Π_{n}, we represent P by a graph on the vertex set [n] whose edge set consists of arcs connecting the elements of each block in numerical order. Such an edge set is called the standard representation of the partition P. For example, the standard representation of 1457-26-3 is {(1, 4), (4, 5), (5, 7), (2, 6)}. Here we always write an arc e as a pair (i, j) with i < j, and say that i is the lefthand endpoint of e and j is the righthand endpoint of e.

Let k ≥ 2 and P ∈ Π_{n}. Define a k-crossing of P as a k-subset (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) of the arcs in the standard representation of P such that i_{1} < i_{2} < ⋯ < i_{k} < j_{1} < j_{2} < ⋯ < j_{k}. Let cr(P) be the maximal k such that P has a k-crossing. Similarly, define a k-nesting of P as a k-subset (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) of the set of arcs in the standard representation of P such that i_{1} < i_{2} < ⋯ < i_{k} < j_{k} < ⋯ < j_{2} < j_{1}, and ne(P) the maximal j such that P has a j-nesting. Note that when restricted to complete matchings, these definitions agree with the ones given before.

Let g_{n}(i, j) be the number of partitions P of [n] with cr(P) = i and ne(P) = j. We shall prove that g_{n}(i, j) = g_{n}(j, i), for all i, j and n. In fact, our result is much stronger. We present a generalization which implies the symmetric distribution of cr(P) and ne(P) over all partitions in Π_{n}, as well over all complete matchings on [2n].

To state the main result, we need some notation. Given P ∈ Π_{n}, define

min(P) = {minimal block elements of P }, max(P) = {maximal block elements of P }.

For example, for P = 135-26-4, min(P) = {1, 2, 4} and max(P) = {4, 5, 6}. The pair (min(P), max(P)) encodes some useful information about the partition P. For example, the number of blocks of P is | min(P)| = | max(P)|; number of singleton blocks is | min(P) ∩ max(P)|; P is a (partial) matching if and only if | min(P)| = | max(P)| and min(P) ∪ max(P) = [n], and P is a complete matching if in addition, min(P) ∩ max(P) = ∅.

Fix S, T ⊆ [n] with |S| = |T |. Let P_{n}(S, T) be the set {P ∈ Π_{n} : min(P) = S, max(P) = T }, and f_{n,S,T} (i, j) be the cardinality of the set {P ∈ P_{n}(S, T) : cr(P) = i, ne(P) = j}.

Theorem 1.

f_{n,S,T} (i, j) = f_{n,S,T} (j, i).  (1)

In other words,

∑_{P ∈P_{n}(S,T)} x^{cr(P)}y^{ne(P)} = ∑_{P ∈P_{n}(S,T)} x^{ne(P)}y^{cr(P)}.  (2)

That is, the statistics cr(P) and ne(P) have a symmetric joint distribution over each set P_{n}(S, T).

Summing over all pairs (S, T) in (1), we get

g_{n}(i, j) = g_{n}(j, i).  (3)

We say that a partition P is k-noncrossing if cr(P) < k. It is k-nonnesting if ne(P) < k. Let NCN_{k,l}(n) be the number of partitions of [n] that are k-noncrossing and l-nonnesting. Summing over 1 ≤ i < k and 1 ≤ j < l in (3), we get the following corollary.

Corollary 2. NCN_{k,l}(n) = NCN_{l,k}(n).

Letting l > n, Corollary 2 becomes the following result.

Corollary 3. NC_{k}(n) = NN_{k}(n), where NC_{k}(n) is the number of k-noncrossing partitions of [n], and NN_{k}(n) is the number of k-nonnesting partitions of [n].

Theorem 1 also applies to complete matchings. A partition P of [2n] is a complete matching if and only if | min(P)| = | max(P)| = n and min(P) ∩ max(P) = ∅. (It follows that min(P) ∪ max(P) = [2n].) Restricting Theorem 1 to disjoint pairs (S, T) of [2n] with |S| = |T | = n, we get the following result on the crossing and nesting number of complete matchings.

Corollary 4. Let M be a matching on [2n].

1. The statistics cr(M) and ne(M) have a symmetric joint distribution over P_{2n}(S, T), where |S| = |T | = n, and S, T are disjoint.

2. f_{n}(i, j) = f_{n}(j, i) where f_{n}(i, j) is the number of matchings on [2n] with cr(M) = i and ne(M) = j.

3. The number of matchings on [2n] that are k-noncrossing and l-nonnesting is equal to the number of matchings on [2n] that are l-noncrossing and k-nonnesting.

4. The number of k-noncrossing matchings on [2n] is equal to the number of k-nonnesting matchings on [2n].

The paper is arranged as follows. In Section 2 we introduce the concept of vacillating tableau of general shape, and give a bijective proof for the number of vacillating tableaux of shape λ and length 2n. In Section 3 we apply the bijection of Section 2 to vacillating tableaux of empty shape, and characterize crossings and nestings of a partition by the corresponding vacillating tableau. The involution on the set of vacillating tableaux defined by taking the conjugate to each shape leads to an involution on partitions which exchanges the statistics cr(P) and ne(P) while preserves min(P) and max(P), thus proving Theorem 1. Then we modify the bijection between partitions and vacillating tableaux by taking isolated points into consideration, and give an analogous result on the enhanced crossing number and nesting number. This is the content of Section 4. Finally in Section 5 we restrict our bijection to the set of complete matchings and oscillating tableaux, and study the enumeration of k-noncrossing matchings. In particular, we construct bijections from k-noncrossing matchings for k = 2 or 3 to Dyck paths and pairs of noncrossing Dyck paths, respectively, and present the generating function for the number of k-noncrossing matchings.

2 A Bijection between Partitions and Vacillating Tableaux

Let Y be Young’s lattice, that is, the set of all partitions of all integers n ∈ ℕ ordered componentwise, i.e., (μ_{1}, μ_{2}, …) ≤ (λ_{1}, λ_{2}, …,) if μ_{i} ≤ λ_{i} for all i. We write λ ⊢ k or |λ| = k if ∑ λ_{i} = k. A vacillating tableau is a walk on the Hasse diagram of Young’s lattice subject to certain conditions. The main tool in our proof of Theorem 1 is a bijection between the set of partitions and the set of vacillating tableaux of empty shape ∅.

Definition 1. A vacillating tableau V_{λ}^{2n} of shape λ and length 2n is a sequence λ^{0}, λ^{1}, …, λ^{2n} of partitions of n such that (i) λ^{0} = ∅, and λ^{2n} = λ, (ii) λ^{2i+1} is obtained from λ^{2i} by doing nothing (i.e., λ^{2i+1} = λ^{2i}) or deleting a square, and (iii) λ^{2i} is obtained from λ^{2i−1} by doing nothing or adding a square.

In other words, a vacillating tableau of shape λ is a walk on the Hasse diagram of Young’s lattice from ∅ to λ where each step consists of either (i) doing nothing twice, (ii) do nothing then adding a square, (iii) removing a square then doing nothing, or (iv) removing a square and then adding a square. Note that if the length is larger than 0, λ^{1} = ∅. If the vacillating tableau is of empty shape, then λ^{2n−1} = ∅ as well.

Example 1. Abbreviate λ = (λ_{1}, λ_{2}, …) by λ_{1}λ_{2} · · ·. There are 5 vacillating tableaux of shape ∅ and length 6. They are

\begin{matrix}λ^{0} & λ^{1} & λ^{2} & λ^{3} & λ^{4} & λ^{5} & λ^{6} \\ ∅ & ∅ & ∅ & ∅ & ∅ & ∅ & ∅ \\ ∅ & ∅ & ∅ & ∅ & 1 & ∅ & ∅ \\ ∅ & ∅ & 1 & ∅ & 1 & ∅ & ∅ \\ ∅ & ∅ & 1 & ∅ & ∅ & ∅ & ∅ \\ ∅ & ∅ & 1 & 1 & 1 & ∅ & ∅ \end{matrix}  (4)

Example 2. An example of a vacillating tableau of shape 11 and length 10 is given by

∅, ∅, 1, 1, 1, 1, 2, 2, 21, 11, 11.

Theorem 5. (i) Let g_{λ}(n) be the number of vacillating tableaux of shape λ ⊢ k and length 2n. By a standard Young tableau (SYT) of shape λ, we mean an array T of shape λ whose entries are distinct positive integers that increase in every row and column. The content of T is the set of positive integers that appear in it. (We don’t require that content(λ) = [k], where λ ⊢ k.) We then have

g_{λ}(n) = B(n, k)f^{λ},

where f^{λ} is the number of SYT’s of shape λ and content [k], and B(n, k) is the number of partitions of [n] with k blocks distinguished.

(ii) The exponential generating function of B(n, k) is given by

∑_{n≥0} B(n, k)\frac{x^{n}}{n!} = \frac{1}{k!}(e^{x} − 1)^{k} exp(e^{x} − 1).  (5)

To prove Theorem 5, we construct a bijection between the set V_{λ}^{2n} of vacillating tableaux of shape λ and length 2n, and pairs (P, T), where P is a partition of [n], and T is an SYT of shape λ such that content(T) ⊆ max(P). In the next section we apply this bijection to vacillating tableaux of empty shape, and related it to the enumeration of crossing and nesting numbers of a partition. In the following we shall assume familiarity with the RSK algorithm, and use row-insertion P ⟵ k as the basic operation of the RSK algorithm. For the notation, as well as some basic properties of the RSK algorithm, see e.g. [22, Chapter 7]. In general we shall apply the RSK algorithm to a sequence w of distinct integers, denoted by w ⟼^{RSK} (A(w), B(w)), where A(w) is the (row)-insertion tableau and B(w) the recording tableau. The shape of the SYT’s A(w) and B(w) is also called the shape of the sequence w.

The Bijection ψ from Vacillating Tableaux to Pairs (P, T). Given a vacillating tableau V = (∅ = λ^{0}, λ^{1}, …, λ^{2n} = λ), we will recursively define a sequence (P_{0}, T_{0}), (P_{1}, T_{1}),…, (P_{2n}, T_{2n}) where P_{i} is a set of pairs of integers in [n], and T_{i} is an SYT of shape λ^{i}. Let P_{0} be the empty set, and let T_{0} be the empty SYT (on the empty alphabet).

1. If λ^{i} = λ^{i−1}, then (P_{i}, T_{i}) = (P_{i−1}, T_{i−1}).

2. If λ^{i} ⊃ λ^{i−1}, then i = 2k for some integer k ∈ [n]. In this case let P_{i} = P_{i−1} and T_{i} is obtained from T_{i−1} by adding the entry k in the square λ^{i} \ λ^{i−1}.

3. If λ^{i} ⊂ λ^{i−1}, then i = 2k − 1 for some integer k ∈ [n]. In this case let T_{i} be the unique SYT (on a suitable alphabet) of shape λ^{i} such that T_{i−1} is obtained from T_{i} by row-inserting some number j. In this case let P_{i} be obtained from P_{i−1} by adding the pair (j, k).

Finally, let ψ(V) = (P, T_{2n}), where P is the partition on [n] whose standard representation is P_{2n}.

In the above construction if an integer i appears in T_{2n}, then P_{2n} can not contain any pair (i, j) with i < j. It follows that i is the maximal element in the block containing it. Hence the content of T_{2n} is a subset of max(P).

Example 3. As an example of the map ψ, let the vacillating tableau be

∅, ∅, 1, 1, 2, 2, 2, 2, 21, 21, 211, 21, 21, 11, 21.

Then the pairs (B_{i}, T_{i}) (where B_{i} is the pair added to P_{i−1} to obtain P_{i}) are given by

i 0 1 2 3 4 5 6 7 8 9 10 11  12 13  14
T_{i} ∅ ∅ 1 1 12 12 12 12 12 12 12 14  14 1  17
4 4 4 5  5 5  5

5

B_{i}  (2, 6)  (4, 7)

Hence

T = {1 7 \atop 5} , P = 1-26-3-47-5.

The map ψ is bijective since the above construction can be reversed. Given a pair (P, T), where P is a partition of [n], and T is an SYT whose content consists of maximal elements of some blocks of P, let E(P) be the standard representation of P, and T_{2n} = T. We work our way backwards from T_{2n}, reconstructing the preceding tableaux and hence the sequence of shapes. If we have the SYT T_{2k} for some k ≤ n, we can get the tableaux T_{2k−1}, T_{2k−2} by the following rules.

1. T_{2k−1} = T_{2k} if the integer k does not appear in T_{2k}. Otherwise T_{2k−1} is obtained from T_{2k} by deleting the square containing k.

2. T_{2k−2} = T_{2k−1} if E(P) does not have an edge of the form (i, k). Otherwise there is a unique i < k such that (i, k) ∈ E(P). In that case let T_{2k−2} be obtained from T_{2k−1} by row-inserting i, or equivalently, T_{2k−2} = (T_{2k−1} ⟵ i).

Proof of Theorem 5. Part (i) follows from the bijection ψ, where a block of P is distinguished if its maximal element belongs to content(T). For part (ii), simply note that to get a structure counted by B(n, k), we can partition [n] into two subsets, S and T, and then partition S into k blocks and put a mark on each block, and partition T arbitrarily. The generating function of B(n, k) then follows from the well-known generating functions for S(n, k), the Stirling number of the second kind, and for the Bell number B(n),

∑_{n≥k} S(n, k)\frac{x^{n}}{n!} = \frac{1}{k!}(e^{x} − 1)^{k},  ∑_{n≥0} B(n)\frac{x^{n}}{n!} = exp(e^{x} − 1).  □

Remark. (1). Restricting to vacillating tableaux of empty shape, the map ψ provides a bijection between the set V_{∅}^{2n} of vacillating tableaux of empty shape and length 2n and the set of partitions of [n]. In particular, g_{∅}(n), the cardinality of V_{∅}^{2n}, is equal to the nth Bell number B(n).

(2). Note that there is a symmetry between the four types of movements in the definition of vacillating tableaux. Thus any walk from ∅ to ∅ in m + n steps can be viewed as a walk from ∅ to some shape λ in n steps, then followed by the reverse of a walk from ∅ to λ in m steps. It follows that

∑_{λ} g_{λ}(n)g_{λ}(m) = g_{∅}(m + n) = B(m + n).  (6)

Remark. The partition algebra 𝔓_{n} is a certain semisimple algebra, say over ℂ, whose dimension is the Bell number B(n) (the number of partitions of [n]). (The algebra 𝔓_{n} depends on a parameter x which is irrelevant here.) See [13] for a survey of this topic. Vacillating tableaux are related to irreducible representations of 𝔓_{n} in the same way that SYT of content [n] are related to irreducible representations of the symmetric group 𝔖_{n}. In particular, the irreducible representations I_{λ} of 𝔓_{n} are indexed by partitions λ for which there exists a vacillating tableau of shape λ and length 2n, and dim I_{n} is the number of such vacillating tableaux. This result is equivalent to [13, Thm. 2.24(b)], but that paper does not explicitly define the notion of vacillating tableau.

3 Crossings and Nestings of Partitions

In this section we restrict the map ψ to vacillating tableaux of empty shape, for which ψ provides a bijection between the set of vacillating tableaux of empty shape and length 2n and the set of partitions of [n]. To make the bijection clear, we restate the inverse map from the set of partitions to vacillating tableaux.

The Map ϕ from Partitions to Vacillating Tableaux. Given a partition P ∈ Π_{n} with the standard representation, we construct the sequence of SYT’s, hence the vacillating tableau ϕ(P) as follows: Start from the empty SYT by letting T_{2n} = ∅, read the number j ∈ [n] one by one from n to 1, and define T_{2j−1}, T_{2j−2} for each j. There are four cases.

1. If j is the righthand endpoint of an arc (i, j), but not a lefthand endpoint, first do nothing, then insert i (by the RSK algorithm) into the tableau.

2. If j is the lefthand endpoint of an arc (j, k), but not a righthand endpoint, first remove j, then do nothing.

3. If j is an isolated point, do nothing twice.

4. If j is the righthand endpoint of an arc (i, j), and the lefthand endpoint of another arc (j, k), then delete j first, and then insert i. The vacillating tableau ϕ(P) is the sequences of shapes of the above SYT’s.

Example 4. Let P be the partition 1457-26-3 of [7].

[figure: 1; 2; 3; 4; 5; 6; 7]

Figure 1: The standard representation of the partition 1457-26-3.

Starting from ∅ on the right, go from 7 to 1, the seven steps are (1) do nothing, then insert 5,

(2) do nothing, then insert 2, (3) delete 5 and insert 4, (4) delete 4 and insert 1, (5) do nothing twice, (6) remove 2 then do nothing, (7) remove 1 then do nothing. Hence the corresponding SYT’s, constructed from right to left, are

\begin{aligned}∅ & ∅ & 1 & 1 & 1 & 1 & 1 & 2 & 24 & 2 & 2 & 5 & 5 & ∅ & ∅ \\ & & & & 2 & 2 & 2 & & & & 5 \end{aligned}

The vacillating tableau is

∅, ∅, 1, 1, 11, 11, 11, 1, 2, 1, 11, 1, 1, ∅, ∅.

The relation between cr(P), ne(P) and the vacillating tableau is given in the next theorem.

Theorem 6. Let P ∈ Π_{n} and ϕ(P) = (∅ = λ^{0}, λ^{1}, …, λ^{2n} = ∅). Then cr(P) is the most number of rows in any λ^{i}, and ne(P) is the most number of columns in any λ^{i}.

Proof. We prove Theorem 6 in four steps. First, we interpret a k-crossing/k-nesting of P in terms of entries of SYT’s T_{i} in ϕ(P). Then, we associate to each SYT T_{i} a sequence σ_{i} whose terms are entries of T_{i}. We prove that T_{i} is the insertion tableau of σ_{i} under the RSK algorithm, and apply Schensted’s theorem to conclude the proof.

Step 1. Let T (P) = (T_{0}, T_{1}, …, T_{2n}) be the sequence of SYT’s associated to the vacillating tableau ϕ(P). By the construction of ψ and ϕ, a pair (i, j) is an arc in the standard representation of P if and only if i is an entry in the SYT’s T_{2i}, T_{2i+1}, …, T_{2j−2}. We say that the the integer i is added to T (P) at step i and leaves at step j.

First we prove that the arcs (i_{1}, j_{1}), …, (i_{k}, j_{k}) form a k-crossing of P if and only if there exists a tableau T_{i} in T (P) such that the integers i_{1}, i_{2}, …, i_{k} ∈ content(T_{i}), and i_{1}, i_{2}, …, i_{k} leave T (P) in increasing order according to their numerical values. Given a k-crossing ((i_{1}, j_{1}), …, (i_{k}, j_{k})) of P, where i_{r} < j_{r} for 1 ≤ r ≤ k and i_{1} < i_{2} < ⋯ < i_{k} < j_{1} < j_{2} < ⋯ < j_{k}, the integer i_{r} is added to T (P) at step i_{r} and leaves at step j_{r}. Hence all i_{r} are in T_{2j_{1}−2}, and they leave T (P) in increasing order. The converse is also true: if there are k integers i_{1} < i_{2} < ⋯ < i_{k} all appearing in the same tableau at some steps, and then leave in increasing order, say at steps j_{1} < j_{2} < ⋯ < j_{k}, then i_{k} < j_{1} and the pairs ((i_{1}, j_{1}), …, (i_{k}, j_{k})) ∈ P form a k-crossing. By a similar argument arcs (i_{1}, j_{1}), …, (i_{k}, j_{k}) form a k-nesting of P if and only if there exists a tableaux T_{i} in T (P) such that the integers i_{1}, i_{2}, …, i_{k} ∈ content(T_{i}), and i_{1}, i_{2}, …, i_{k} leave T (P) in decreasing order.

Step 2. For each T_{i} ∈ T (P), we define a permutation σ_{i} of content(T_{i}) (backward) recursively as follows. Let σ_{2n} be the empty sequence. (1) If T_{i} = T_{i−1}, then σ_{i−1} = σ_{i}. (2) If T_{i−1} is obtained from T_{i} by row-inserting some number j, then σ_{i−1} = σ_{i}j, the juxtaposition of σ_{i} and j. (3) If T_{i} is obtained from T_{i−1} by adding the entry i, then σ_{i−1} is obtained from σ_{i} by deleting the number i. Note that in the last case, i must be the largest entry in σ_{i}.

Clearly σ_{i} is a permutation of the entries in content(T_{i}). If σ_{i} = w_{1}w_{2} ⋯ w_{r}, then the entries of content(T_{i}) leave T (P) in the order w_{r}, …, w_{2}, w_{1}.

Step 3. Claim: If σ_{i} ⟼^{RSK} (A_{i}, B_{i}), then A_{i} = T_{i}.

We prove the claim by backward induction. The case i = 2n is trivial as both A_{2n} and T_{2n} are the empty SYT. Assume the claim is true for some i, 1 ≤ i ≤ 2n. We prove that the claim holds for i − 1.

If T_{i−1} = T_{i}, the claim holds by the inductive hypothesis. If T_{i−1} is obtained from T_{i} by inserting the number j, then the claim holds by the definition of the RSK algorithm. It is only left to consider the case that T_{i−1} is obtained from T_{i} by removing the entry i.

Let us write σ_{i} as u_{1}u_{2} ⋯ u_{s}iv_{1} ⋯ v_{t}, and σ_{i−1} as u_{1}u_{2} ⋯ u_{s}v_{1} ⋯ v_{t}, where i > u_{1}, …, u_{s}, v_{1}, …, v_{t}. We need to show that the insertion tableau of σ_{i−1} is the same as the insertion tableau of σ_{i} deleting the entry i, i.e., A_{i−1} = A_{i} \{i}. Proof by induction on t. If t = 0 then it is true by the RSK algorithm that A_{i} is obtained from A_{i−1} by adding i at the end of the first row. Assume it is true for t − 1, i.e., A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}) = A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}) \ {i}. Note that in A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}), if i is in position (x, y), then there is no element in positions (x, y + 1) or (x + 1, y). Now we insert the entry v_{t} by the RSK algorithm. Consider the insertion path I = I(A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}) ⟵ v_{t}). If i does not appear on this path, then we would have the exact same insertion path when inserting v_{t} into A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}). This insertion path results in the same change to A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}) and A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}), which does not touch the position (x, y) of i. So A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}v_{t}) = A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}v_{t}) \ {i}. On the other hand, if i appears in the insertion path I, i.e., (x, y) ∈ I, then since i is the largest element, it must be bumped into the (x + 1)-th row, and become the last entry in the (x + 1)-th row without bumping any number further. Then the insertion path of v_{t} into A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}) is I minus the last position {(x + 1, ∗)}, and again we have A(u_{1} ⋯ u_{s}v_{1} ⋯ v_{t−1}v_{t}) = A(u_{1} ⋯ u_{s}iv_{1} ⋯ v_{t−1}v_{t}) \ {i}. This finishes the proof of the claim.

Step 4. We shall need the following theorem of Schensted [19][22, Thms. 7.23.13, 7.23.17], which gives the basic connection between the RSK algorithm and the increasing and decreasing subsequences.

Schensted’s Theorem Let σ be a sequence of integers whose terms are distinct. Assume σ ⟼^{RSK} (A, B), where A and B are SYT’s of the shape λ. Then the length of the longest increasing subsequence of σ is λ_{1} (the number of columns of λ), and the length of the longest decreasing subsequence is λ′_{1} (the number of rows of λ).

Now we are ready to prove Theorem 6. By Steps 1 and 2, a partition P has a k-crossing if and only if there exists i such that σ_{i} has a decreasing subsequence of length k. The claim in Step 3 implies that the shape of the sequence σ_{i} is exactly the diagram of the i-th partition λ^{i} in the vacillating tableau ϕ(P). By Schensted’s Theorem, σ_{i} has a decreasing subsequence of length k if and only if the partition λ^{i} in ϕ(P) has at least k rows. This proves the statement for cr(P) in Theorem 6. The statement for ne(P) is proved similarly. □

The symmetric joint distribution of statistics cr(P) and ne(P) over P_{n}(S, T) follows immediately from Theorem 6. Proof of Theorem 1.

From Theorem 6, a partition P ∈ Π_{n} has cr(P) = k and ne(P) = j if and only if for the partitions {λ^{i}}_{i=0}^{2n} of the vacillating tableau ϕ(P), the maximal number of rows of the diagram of any λ^{i} is k, and the maximal number of columns of the diagram of any λ^{i} is j. Let τ be the involution defined on the set V_{∅}^{2n} by taking the conjugate to each partition λ^{i}. Since τ preserves min(P) and max(P), it induces an involution on P_{n}(S, T) which exchanges the statistics cr(P) and ne(P). This proves Theorem 1. □

Let λ = (λ_{1}, λ_{2}, …) be the shape of a sequence w of distinct integers. Schensted’s Theorem provides a combinatorial interpretation of the terms λ_{1} and λ′_{1}: they are the length of the longest increasing and decreasing subsequences of w. In [12] Greene extended Schensted’s Theorem by giving an interpretation of the rest of the diagram of λ = (λ_{1}, λ_{2}, …).

Assume w is a sequence of length n. For each k ≤ n, let d_{k}(w) denote the length of the longest subsequence of w which has no increasing subsequences of length k + 1. It can be shown easily that any such sequence is obtained by taking the union of k decreasing subsequences. Similarly, define a_{k}(w) to be the length of the longest subsequence consisting of k ascending subsequences.

Theorem 7 (Greene). For each k ≤ n,

a_{k}(w) = λ_{1} + λ_{2} + ⋯ + λ_{k},
d_{k}(w) = λ′_{1} + λ′_{2} + ⋯ + λ′_{k},

where λ′ = (λ′_{1}, λ′_{2}, …) is the conjugate of λ.

We may consider the analogue of Greene’s Theorem for set partitions. Let P ∈ Π_{n} with the standard representation {(i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{t}, j_{t})}, where i_{r} < j_{r} for 1 ≤ r ≤ t. Let e_{r} = (i_{r}, j_{r}). We define the crossing graph Cr(P) of P as follows. The vertex set of Cr(P) is {e_{1}, e_{2}, …, e_{t}}. Two arcs e_{r} and e_{s} are adjacent if and only if the edges e_{r} and e_{s} are crossing, that is, i_{r} < i_{s} < j_{r} < j_{s}. Clearly a k-crossing of P corresponds to a k-clique of Cr(P). Let cr_{t}(P) be the maximal number of vertices in a union of t cliques of Cr(P). In other words, cr_{t}(P) is the maximal number of arcs in a union of t crossings of P. Similarly, let Ne(P) be the graph defined on the vertex set {e_{1}, …, e_{t}} where two arcs e_{r} and e_{s} are adjacent if and only if i_{r} < i_{s} < j_{s} < j_{r}. Let ne_{t}(P) be the maximal number of vertices in a union of t cliques of Ne(P). In other words, ne_{t}(P) is the maximal number of arcs in a union of t nestings of P.

Proposition 8. Let P = ((i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{t}, j_{t})) be the standard representation of a partition of [n], where i_{r} < j_{r} for all 1 ≤ r ≤ t and j_{1} < j_{2} < ⋯ < j_{t}. Let α(P) be the sequence i_{1}i_{2} ⋯ i_{t}. Then there is a one-to-one correspondence between the set of nestings of P and the set of decreasing subsequences of α(P).

Proof. Let ϕ(P) be the vacillating tableau corresponding to P, and T (P) the sequence of SYT’s constructed in the bijection. Then α(P) records the order in which the entries of T_{i}’s leave T (P). Let σ = i_{t} ⋯ i_{2}i_{1} be the reverse of α(P), and {σ_{i} : 1 ≤ i ≤ 2n} the permutation of content(T_{i}) defined in Step 2 of the proof of Theorem 6. Then the σ_{i}’s are subsequences of σ.

From Steps 1 and 2 of the proof of Theorem 6, nestings of P are represented by the increasing subsequences of σ_{i}, 1 ≤ i ≤ 2n, and hence by the increasing subsequences of σ. Conversely, let i_{r_{1}} < i_{r_{2}} < ⋯ < i_{r_{t}} be an increasing subsequence of σ. Being a subsequence of σ means that its terms leave T (P) in reverse order, so i_{r_{t}} leaves first in step j_{r_{t}}. Thus all the entries i_{r_{1}}, …, i_{r_{t}} appear in the SYT’s T_{i} with 2i_{r_{t}} ≤ i ≤ 2j_{r_{t}} − 2. Therefore i_{r_{1}}i_{r_{2}} ⋯ i_{r_{t}} is also an increasing subsequence of σ_{i}, for 2i_{r_{t}} ≤ i ≤ 2j_{r_{t}} − 2. □

Combining Proposition 8 and Greene’s Theorem, we have the following corollary describing ne_{t}(P).

Corollary 9. Let P and α(P) be as in Proposition 8. Then

ne_{t}(M) = λ′_{1} + λ′_{2} + ⋯ + λ′_{t},

where λ is the shape of α(P), and λ′ is the conjugate of λ.

The situation for cr_{t}(P) is more complicated. We don’t have a result similar to Proposition 8. Any crossing of P uniquely corresponds to an increasing subsequence of α(P). But the converse is not true. An increasing subsequence i_{r_{1}}i_{r_{2}} ⋯ i_{r_{t}} corresponds to a t-crossing of P only if we have the additional condition i_{r_{t}} < j_{r_{1}}. It would be interesting to get a result for cr_{t}(P) analogous to Corollary 9.

To conclude this section we discuss the enumeration of noncrossing partitions. The following theorem is a direct corollary of the bijection between vacillating tableaux and partitions.

Theorem 10. Let ϵ_{i} denote the ith unit coordinate vector in ℝ^{k−1}. The number of k-noncrossing partitions of [n] equals the number of closed lattice walks in the region

V_{k} = {(a_{1}, a_{2}, …, a_{k−1}) : a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{k−1} ≥ 0, a_{i}inℤ}

from the origin to itself of length 2n with steps ±ϵ_{i} or (0, 0, …, 0), with the property that the walk goes backwards (i.e., with step −ϵ_{i}) or stands still (i.e., with step (0, 0, …, 0)) after an even number of steps, and goes forwards (i.e., with step +ϵ_{i}) or stands still after an odd number of steps.

Recall that a partition P ∈ Π_{n} is k-noncrossing if cr(P) < k, and is k-nonnesting if ne(P) < k. A partition P has no k-crossings and no j-nestings if and only if for all the partitions λ^{i} of ϕ(P), the diagram fits into a (k − 1) × (j − 1) rectangle. Taking the conjugate of each partition, we get bijective proofs of Corollaries 2 and 3.

Theorem 1 asserts the symmetric distribution of cr(P) and ne(P) over P_{n}(S, T), for all S, T ⊆ [n] with |S| = |T |. Not every P_{n}(S, T) is nonempty. A set P_{n}(S, T) is nonempty if and only if for all i ∈ [n], |S ∩ [i]| ≥ |T ∩ [i]|. Another way to describe the nonempty P_{n}(S, T) is to use lattice paths. Associate to each pair (S, T) a lattice path L(S, T) with steps (1, 1), (1, −1) and (1, 0): start from (0, 0), read the integers i from 1 to n one by one, and move two steps for each i.

1. If i ∈ S ∩ T, move (1, 0) twice.
2. If i ∈ S \ T, move (1, 0) then (1, 1).
3. If i ∈ T \ S, move (1, −1) then (1, 0).
4. If i ∉ S ∪ T, move (1, −1) then (1, 1).

This defines a lattice path L(S, T) from (0, 0) to (2n, 0), Conversely, the path uniquely determines (S, T). Then P_{n}(S, T) is nonempty if and only if the lattice path L(S, T) is a Motzkin path, i.e., never goes below the x-axis.

There are existing notions of noncrossing partitions and nonnesting partitions, e.g., [22, Ex.6.19]. A noncrossing partition of [n] is a partition of [n] in which no two blocks “cross” each other, i.e., if a < b < c < d and a, b belong to a block B and c, d to another block B′, then B = B′. A nonnesting partition of [n] is a partition of [n] such that if a, e appear in a block B and b, d appear in a different block B′ where a < b < d < e, then there is a c ∈ B satisfying b < c < d.

It is easy to see that P is a noncrossing partition if and only if the standard representation of P has no 2-crossing, and P is a nonnesting partition if and only if the standard representation of P has no 2-nesting. Hence the vacillating tableau correspondence, in the case of 1-row/column tableaux, gives bijections between noncrossing partitions of [n], nonnesting partitions of [n], (both are counted by Catalan numbers) and sequences 0 = a_{0}, a_{1}, ..., a_{2n} = 0 of nonnegative integers such that a_{2i+1} = a_{2i} or a_{2i} − 1, and a_{2i} = a_{2i−1} or a_{2i−1} + 1. These sequences a_{0}, ..., a_{2n} give a new combinatorial interpretation of Catalan numbers.

Replacing a term a_{i+1} = a_{i} + 1 with a step (1, 1), a term a_{i+1} = a_{i} − 1 with a step (1, −1), and a term a_{i+1} = a_{i} with a step (1, 0), we get a Motzkin path, so we also have a bijection between noncrossing/nonnesting partitions and certain Motzkin paths. The Motzkin paths are exactly the ones defined as L(S, T), where S = min(P) and T = max(P). Conversely, given a Motzkin path of the form L(S, T), we can recover uniquely a noncrossing partition and a nonnesting partition. Write the path as {(i, a_{i}) : 0 ≤ i ≤ 2n}. Let A = [n] \ T and B = [n] \ S. Clearly |A| = |B|. Assume A = {i_{1}, i_{2}, …, i_{t}}_{<}, and B = {j_{1}, j_{2}, …, j_{t}}_{<} where elements are listed in increasing order. Then to get the standard representation of the noncrossing partition, pair each j_{r} with max{i_{s} ∈ A : i_{s} < j_{r}, a_{2i_{s}} = a_{2j_{r}−2}}. To get the standard representation of the nonnesting partition, pair each j_{r} with i_{r}, for 1 ≤ r ≤ t.

Remark. In our definition, a k-crossing is defined as a set of k mutually crossing arcs in the standard representation of the partition. There exist some other definitions. For example, in [14] Klazar defined 3-noncrossing partition as a partition P which does not have 3 mutually crossing blocks. It can be seen that P is 3-noncrossing in Klazar’s sense if and only if there do not exist 6 elements a_{1} < b_{1} < c_{1} < a_{2} < b_{2} < c_{2} in [n] such that a_{1}, a_{2} ∈ A, b_{1}, b_{2} ∈ B, c_{1}, c_{2} ∈ C, and A, B, C are three distinct blocks of P.

Klazar’s definition of 3-noncrossing partitions is different from ours. For example, let P be the partition 15-246-37 of [7], with standard representation as follows:

[figure: 1; 2; 3; 4; 5; 6; 7]

According to Klazar’s definition, P has a 3-crossing, since we have 1 < 2 < 3 < 5 < 6 < 7 and {1, 5}, {2, 6} and {3, 7} belong to three different blocks, respectively. On the other hand, P has no 3-crossing on our sense.

For general k, these three notions of k-noncrossing partitions, i.e., (1) no k-crossing in the standard representation of P, (2) no k mutually crossing arcs in distinct blocks of P, and (3) no k mutually crossing blocks, are all different, with the first being the weakest, and the third the strongest.

4 A Variant: Partitions and Hesitating Tableaux

We may also consider the enhanced crossing/nesting of a partition, by taking isolated points into consideration. For a partition P of [n], let the enhanced representation of P be the union of the standard representation of P and the loops {(i, i) : i is an isolated point of P }. An enhanced kcrossing of P is a set of k edges (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) of the enhanced representation of P such that i_{1} < i_{2} < ⋯ < i_{k} ≤ j_{1} < j_{2} < ⋯ < j_{k}. In particular, two arcs of the form (i, j) and (j, l) with i < j < l are viewed as crossing. Similarly, an enhanced k-nesting of P is a set of k edges (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) of the enhanced representation of P such that i_{1} < i_{2} < ⋯ < i_{k} ≤ j_{k} < ⋯ < j_{2} < j_{1}. In particular, an edge (i, k) and an isolated point j with i < j < k form an enhanced 2-nesting.

Let \overline{cr}(P) be the size of the largest enhanced crossing, and \overline{ne}(P) the size of the largest enhanced nesting. Using a variant form of vacillating tableau, we obtain again a symmetric joint distribution of the statistics \overline{cr}(P) and \overline{ne}(P).

The variant tableau is a hesitating tableau of shape ∅ and length 2n, which is a path on the Hasse diagram of Young’s lattice from ∅ to ∅ where each step consists of either (i) doing nothing then adding a square, (ii) removing a square then doing nothing, or (iii) adding a square and then removing a square.

Example 5. There are 5 hesitating tableaux of shape ∅ and length 6. They are

\begin{matrix}∅ & 1 & ∅ & 1 & ∅ & 1 & ∅ \\ ∅ & 1 & ∅ & ∅ & 1 & ∅ & ∅ \\ ∅ & ∅ & 1 & 11 & 1 & ∅ & ∅ \\ ∅ & ∅ & 1 & ∅ & ∅ & 1 & ∅ \\ ∅ & ∅ & 1 & 21 & 1 & ∅ & ∅ \end{matrix}  (7)

To see the equivalence with vacillating tableaux, let U be the operator that takes a shape to the sum of all shapes that cover it in Young’s lattice (i.e., by adding a square), and similarly D takes a shape to the sum of all shapes that it covers in Young’s lattice (i.e., by deleting a square). Then, as is well-known, DU − UD = I (the identity operator). See, e.g. [20][22, Exer. 7.24]. It follows that

(U + I)(D + I) = DU + ID + UI.  (8)

Iterating the left-hand side generates vacillating tableaux, and iterating the right-hand side gives the hesitating tableaux defined above.

A bijective map between partitions of [n] and hesitating tableaux of empty shape has been given by M. Korn [15], based on growth diagrams. Here by modifying the map ϕ defined in Section 3 we get a more direct bijection ϕ̄ between partitions and hesitating tableaux of empty shape, which leads to the symmetric joint distribution of \overline{cr}(P) and \overline{ne}(P). The construction and proofs are very similar to the ones given in Sections 2 and 3, and hence are omitted here. We will only state the definition of the map ϕ̄ from partitions to hesitating tableaux, to be compared with the map ϕ in Section 3.

The Bijection ϕ̄ from Partitions to Hesitating Tableaux. Given a partition P ∈ Π_{n} with the enhanced representation, we construct the sequence of SYT’s, and hence the hesitating tableau ϕ̄(P), as follows: Start from the empty SYT by letting T_{2n} = ∅, read the numbers j ∈ [n] one by one from n to 1, and define two SYT’s T_{2j−1}, T_{2j−2} for each j. When j is a lefthand endpoint only, or a righthand endpoint only, the construction is identical to that of the map ϕ. Otherwise,

1. If j is an isolated point, first insert j, then delete j.

2. If j is the righthand endpoint of an arc (i, j), and the lefthand endpoint of another arc (j, k), then insert i first, and then delete j.

Example 6. For the partition 1457-26-3 of [7] in Figure 2, the corresponding SYT’s are

\begin{aligned}∅ & ∅ & 1 & 1 & 1 & 13 & 1 & 14 & 24 & 24 & 2 & 5 & 5 & ∅ & ∅ \\ & & & & 2 & 2 & 2 & 2 & & 5 & 5 \end{aligned}

The hesitating tableau ϕ̄(P) is

∅, ∅, 1, 1, 11, 21, 11, 21, 2, 21, 11, 1, 1, ∅, ∅.

The conjugation of shapes does not preserve min(P) or max(P). Instead, it preserves min(P)\ max(P), and max(P) \ min(P). Let S, T be disjoint subsets of [n] with the same cardinality, P̄_{n}(S, T) = {P ∈ Π_{n} : min(P)\max(P) = S, max(P)\min(P) = T }, and f̄_{n,S,T} (i, j) = #{P ∈ P̄_{n}(S, T) : \overline{cr}(P) = i, \overline{ne}(P) = j\}.

Figure 2: The enhanced representation of the partition 1457-26-3.

Theorem 11. We have

f̄_{n,S,T} (i, j) = f̄_{n,S,T} (j, i).

As a consequence, Corollaries 2 and 3 remain valid if we define k-noncrossing (or k-nonnesting) by c̄r(P) < k (or n̄e(P) < k).

Remark. As done for vacillating tableaux, one can extend the definition of hesitating tableaux by considering moves from ∅ to λ, and denote by f_{λ}(n) the number of such hesitating tableaux of length 2n. Identity (8) implies that f_{λ}(n) = g_{λ}(n), the number of vacillating tableaux from ∅ to λ. It follows that f_{∅}(n) = B(n), and

∑_{λ} f_{λ}(n)f_{λ}(m) = B(m + n),

where B(n) is the nth Bell number. For further discussion of the number f_{λ}(n), see [23, Problem 33] (version of 17 August 2004).

5 Enumeration of k-Noncrossing Matchings

Restricting Theorem 1 to disjoint subsets (S, T) of [2n] with |S| = |T | = n, we get the symmetric joint distribution of the crossing number and nesting number for matchings, as stated in Corollary 4 in Section 1.

In a complete matching, an integer is either a left endpoint or a right endpoint in the standard representation. In applying the map ϕ to complete matchings on [2n], if we remove all steps which do nothing, we obtain a sequence ∅ = λ^{0}, λ^{1}, …, λ^{2n} = ∅ of partitions such that for all 1 ≤ i ≤ 2n, the diagram of λ^{i} is obtained from that of λ^{i−1} by either adding one square or removing one square. Such a sequence is called an oscillating tableau (or up-down tableau) of empty shape and length 2n. Thus we get a bijection between complete matchings on [2n] and oscillating tableaux of empty shape and length 2n. This bijection was originally constructed by the fourth author, and then extended by Sundaram [24] to arbitrary shapes to give a combinatorial proof of the Cauchy identity for the symplectic group Sp(2n). The explicit description of the bijection has appeared in [24] and was included in [22, Exercise 7.24]. Oscillating tableaux first appeared (though not with that name) in [4].

Remark. The Brauer algebra 𝔅_{n} is a certain semisimple algebra, say over ℂ, whose dimension is the number 1 · 3 ⋯ (2n − 1) of matchings on [2n]. (The algebra 𝔅_{n} depends on a parameter x which is irrelevant here.) Oscillating tableaux are related to irreducible representations of 𝔅_{n} in the same way that SYT of content [n] are related to irreducible representations of the symmetric group 𝔖_{n} and that vacillating tableaux of length 2n are related to irreducible representations of the partition algebra 𝔓_{n}. In particular, the irreducible representations J_{λ} of 𝔅_{n} are indexed by partitions λ for which there exists a oscillating tableau of shape λ and length n, and dim J_{n} is the number of such oscillating tableaux. See e.g. [3, Appendix B6] for further information.

Next we use the bijection between complete matchings and oscillating tableaux to study the enumeration of k-noncrossing matchings. All the results in the following hold for k-nonnesting matchings as well.

For complete matchings, Theorem 10 becomes the following.

Corollary 12. The number of k-noncrossing matchings of [2n] is equal to the number of closed lattice walks of length 2n in the set

V_{k} = {(a_{1}, a_{2}, …, a_{k−1}) : a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{k−1} ≥ 0, a_{i} ∈ ℤ}

from the origin to itself with unit steps in any coordinate direction or its negative.

Restricted to the cases k = 2, 3, Corollary 12 leads to some nice combinatorial correspondences. Recall that a Dyck path of length 2n is a lattice path in the plane from the origin (0, 0) to (2n, 0) with steps (1, 1) and (1, −1), that never passes below the x-axis. A pair (P, Q) of Dyck paths is noncrossing if they have the same origin and the same destination, and P never goes below Q.

Corollary 13. 1. The set of 2-noncrossing matchings is in one-to-one correspondence with the set of Dyck paths.

2. The set of 3-noncrossing matchings is in one-to-one correspondence with the set of pairs of noncrossing Dyck paths.

Proof. By Corollary 12, 2-noncrossing matchings are in one-to-one correspondence with closed lattice paths {v⃗_{i} = (x_{i})}_{i=0}^{2n} with x_{0} = x_{2n} = 0, x_{i} ≥ 0 and x_{i+1} − x_{i} = ±1. Given such a 1dimensional lattice path, define a lattice path in the plane by letting P = {(i, x_{i}) | i = 0, 1, …, 2n}. Then P is a Dyck path, and this gives the desired correspondence.

For k = 3, 3-noncrossing matchings are in one-to-one correspondence with 2-dimensional lattice paths {v⃗_{i} = (x_{i}, y_{i})}_{i=0}^{2n} with (x_{0}, y_{0}) = (x_{2n}, y_{2n}) = (0, 0), x_{i} ≥ y_{i} ≥ 0 and (x_{i+1}, y_{i+1}) − (x_{i}, y_{i}) = (±1, 0) or (0, ±1). Given such a lattice path, define two lattice paths in the plane by setting P = {(i, x_{i} + y_{i}) | i = 0, 1, …, 2n} and Q = {(i, x_{i} − y_{i}) | i = 0, 1, …, 2n}. Then (P, Q) is a pair of noncrossing Dyck paths. It is easy to see that this is a bijection. □

Example 7. We illustrate the bijections between 3-noncrossing matchings, oscillating tableaux, and pairs of noncrossing Dyck paths. The oscillating tableau is

∅, 1, 2, 21, 31, 21, 11, 21, 2, 1, ∅.

The sequence of SYT’s as defined in the bijection is

∅, 1, 12, {1 2 \atop 3} , {1 2 4 \atop 3} , {1 2 \atop 3} , {1 \atop 3} , {1 7 \atop 3} , 37, 3, ∅.

The corresponding matching and the pair of noncrossing Dyck paths are given in Figure 3.

[figure: 1; 8; 2; 6; 3; 10; 4; 5; 7; 9]

Figure 3: The matching and the pair of noncrossing Dyck paths.

Let f_{k}(n) be the number of k-noncrossing matchings of [2n]. By Corollary 12 it is also the number of lattice paths of length 2n in the region V_{k} from the origin to itself with step set {±ϵ_{1}, ±ϵ_{2}, …, ±ϵ_{k−1}}. Set

F_{k}(x) = ∑_{n} f_{k}(n)\frac{x^{2n}}{(2n)!}.

It turns out that a determinantal expression for F_{k}(x) has been given by Grabiner and Magyar [10]. It is simply the case λ = η = (n, n − 1, ..., 1) of equation (38) in [10], giving

F_{k}(x) = det [I_{i−j}(2x) − I_{i+j}(2x)]_{i,j=1}^{k−1} ,  (9)

where

I_{m}(2x) = ∑_{j≥0} \frac{x^{m+2j}}{j!(m + j)!},

the hyperbolic Bessel function of the first kind of order m [27]. One can easily check that when k = 2, the generating function of 2-noncrossing matchings equals

F_{2}(x) = I_{0}(2x) − I_{2}(2x) = ∑_{j≥0} C_{j} \frac{x^{2j}}{(2j)!},

where C_{j} is the j-th Catalan number. When k = 3, we have

f_{3}(n) = \frac{3!(2n + 2)!}{n!(n + 1)!(n + 2)!(n + 3)!}
= C_{n}C_{n+2} − C_{n+1}^{2}.

This result agrees with the formula on the number of pairs of noncrossing Dyck paths due to Gouyou-Beauchamps in [9].

Remark. We would like to point out the similarity between the determinant formula (9) and some other analogous formulas considered in literature, for instance, by Gessel [11, Eq. 22], and by Baik and Rains [1, Eqs. (2.22)–(2.33)]. It should be possible to work out the complete asymptotic distribution of cr(M), the size of the largest crossing of a complete matching on [2n] from the determinant formula of F_{k}(x). This would be analogous to the famous result on the longest increasing subsequence of a random permutation due to Baik, et al. [2].

Similarly one can try to enumerate complete matchings of [2n] with no (k + 1)-crossing and no (j + 1)-nesting. By the oscillating tableau bijection this is just the number of walks of length 2n from ˆ0 to ˆ0 in the Hasse diagram of the poset L(k, j), where ˆ0 denotes the unique bottom element (the empty partition) of L(k, j), the lattice of integer partitions whose shape fits in a k×j rectangle, ordered by inclusion. Let g_{k,j}(n) be this number, and G_{k,j}(x) = ∑_{n} g_{k,j}(n)x^{2n} be the generating function.

For j = 1, the number g_{k,1}(n) counts lattice paths from (0, 0) to (2n, 0) with steps (1, 1) or (1, −1) that stay between the lines y = 0 and y = k. The evaluation of g_{k,1}(n) was first considered by Takacs in [25] by a probabilistic argument. An explicit formula was given by Mohanty [16] by applying the reflection principle repeatedly, viz.,

g_{k,1}(n) = ∑_{i} [\binom{2n}{n − i(k + 2)} − \binom{2n}{n + i(k + 2) + k + 1}] .

The generating function G_{k,1}(x) has been given by Feller, who in [8] considered generating functions for the duration of the game in the classical ruin problem, that is, restricted random walks with absorbing barriers at 0 and a, and initial position z. Let

U_{z}(x) = ∑_{n=0}^{∞} u_{z,n}x^{n},

where u_{z,n} is the probability that the process ends with the n-th step at the barrier 0. Equation (4.11) in Chapter 14 of [8] gives

U_{z}(x) = (\frac{q}{p})^{z} \frac{λ_{1}^{a−z}(x) − λ_{2}^{a−z}(x)}{λ_{1}^{a}(x) − λ_{2}^{a}(x)},

where

λ_{1}(x) = \frac{1 + \sqrt{1 − 4pqx^{2}}}{2px} , λ_{2}(x) = \frac{1 − \sqrt{1 − 4pqx^{2}}}{2px} .

Then G_{k,1}(x) is just U_{1}(2x)/x with a = k + 2, z = 1, and p = q = 1/2.

In general, by the transfer matrix method [21, §4.7]

G_{k,j}(x) = \frac{det(I − xA_{k,j}(0))}{det(I − xA_{k,j})}  (10)

is a rational function, where A_{k,j} is the adjacency matrix of the Hasse diagram of L(k, j), and A_{k,j}(0) is obtained from A_{k,j} by deleting the row and the column corresponding to ˆ0. A_{k,j}(0) is also the adjacency matrix of the Hasse diagram of L(k, j) with its bottom element (the empty partition) removed. Note that det(I − xA_{k,j}) is a polynomial in x^{2} since L(k, j) is bipartite [5, Thm. 3.11]. Let det(I − xA_{k,j}) = p_{k,j}(x^{2}). The following is a table of p_{k,j}(x) for the values of 1 ≤ k ≤ j ≤ 4. (We only need to list those with k ≤ j since p_{k,j}(x) = p_{j,k}(x).)

(k, j) p_{k,j}(x) = det(I − \sqrt{x}A_{k,j})
(1, 1) 1 − x
(1, 2) 1 − 2x
(1, 3) 1 − 3x + x^{2}
(1, 4) (1 − x)(1 − 3x)
(2, 2) (1 − x)(1 − 5x)
(2, 3) (1 − x)(1 − 3x)(1 + 8x − 4x^{2}))
(2, 4) (1 − 14x + 49x^{2} − 49x^{3})(1 − 6x + 5x^{2} − x^{3})
(3, 3) (1 − x)(119x + 83x^{2} − x^{3})(1 − 5x + 6x^{2} − x^{3})
(3, 4) (1 − 2x)(1 − 8x + 8x^{2})(1 − 4x + 2x^{2})(1 − 16x + 60x^{2} − 32x^{3} + 4x^{4})
·(1 − 24x + 136x^{2} − 160x^{3} + 16x^{4})
(4, 4) (1 − x)(1 − 18x + 81x^{2} − 81x^{3})(1 − 27x + 99x^{2} − 9x^{3})(1 − 9x + 18x^{2} − 9x^{3})
·(1 − 27x + 195x^{2} − 361x^{3})(1 − 6x + 9x^{2} − x^{3})(1 − 9x + 6x^{2} − x^{3})

The polynomial p_{k,j}(x) seems to have a lot of factors. It would be interesting to understand why det(I − xA_{k,j}) has so many factors. It would also be interesting to decide when A_{k,j} is invertible, or even to determine the rank of A_{k,j}. We have observed the following.

• For k + j ≤ 12 and 1 ≤ k ≤ j, A_{k,j} is invertible exactly for (k, j) =(1, 1), (1, 3), (1, 5), (1, 7), (1, 9), (1, 11), (3, 3), (3, 7), (3, 9), (5, 5) and (5, 7).

• A_{1,j} is invertible if and only if j is odd. This is true because L(1, j) is a path of length j, whose determinant satisfies the recurrence det(A_{1,j}) = − det(A_{1,j−2}). The statement follows from the initial conditions det(A_{1,1}) = −1 and det(A_{1,2}) = 0.

• det(A_{2,j}) = 0 for all j. It can be seen as follows. For i = 0, 1, let L_{i} be the set {(m, m) ∈ L(2, j) : m ≡ i (mod 2)}. Any partition (x, y) of L(2, j) adjacent to some vertices in L_{0} or L_{1} must satisfy x = y + 1. On the other hand, there are exactly two vertices in L(2, j) that are adjacent to (y + 1, y), namely, (y, y) and (y + 1, y + 1), one in L_{0} and one in L_{1}. This implies that in A_{2,j}, the sum of the rows indexed by partitions in L_{0} is equal to the sum of rows indexed by partitions in L_{1}. Hence det(A_{2,j}) = 0.

Based on the above observation, we conjecture that the condition that A_{k,j} is invertible is that k and j are odd, with the case (3, 5) being an exception.

References

[1] J. Baik and E. Rains, Algebraic aspects of increasing subsequences, Duke Math. J. 109 (2001), No. 1, 1–65.

[2] J. Baik, P. Deift and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), No. 4, 1119–1178.

[3] H. Barcelo and A. Ram, Combinatorial representation theory, in New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97), MSRI Publ. 38, Cambridge University Press, Cambridge, 1999, pp. 23–90.

[4] A. Berele, A Schensted-type correspondence for the symplectic group, J. Combinatorial Theory (A) 43 (1986), 320–328.

[5] D. M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs, 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995.

[6] H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations. Amer. J. Math. 87 (1965), 684–694.

[7] M. de Sainte-Catherine, Couplages et Pfaffiens en combinatoire, physique et informatique, Ph.D. Thesis, University of Bordeaux I, 1983.

[8] W. Feller, An Introduction to Probability Theory and Its Applications, 3rd edition, John Wiley & Sons, Inc., New York, 1968.

[9] D. Gouyou-Beauschamps, Standard Young tableaux of height 4 and 5, Europ. J. Combin. 10 (1989), 69–82.

[10] D. Grabiner and P. Magyar, Random walks in Weyl chambers and the decomposition of tensor powers, J. Alg. Combinatorics 2 (1993), 239–260.

[11] I. Gessel, Symmetric functions and P-recursiveness, J. Combinatorial Theory (A) 53 (1990), 257–285.

[12] C. Greene, An extension of Schensted’s theorem, Adv. Math. 14 (1974), 254–265.

[13] T. Halverson and A. Ram, Partition algebras, preprint; math.RT/0401314.

[14] M. Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combinatorial Theory (A) 102 (2003), 63–87.

[15] M. Korn, Personal communication.

[16] S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, New York, 1979.

[17] R. C. Mullin and R. C. Stanton, A map-theoretic approach to Davenport-Schinzel sequences, Pacific J. Math. 40 (1972), 167–172.

[18] J. Riordan, The distribution of crossings chords joining pairs of 2n points on a circle, Math. Computation 29 (1975), 215-222.

[19] C. E. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191.

[20] R. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), 919–961.

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

[22] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[23] R. Stanley, Supplementary Exercises for Chapter 7 of Enumerative Combinatorics, available

    at http://www-math.mit.edu/∼rstan/ec.

[24] S. Sundaram, The Cauchy identity for Sp(2n), J. Combinatorial Theory (A) 53 (1990), 209– 238.

[25] L. Takacs, Ballot problems, Z. Wahrsch. Verw. Gebiete 1 (1962), 154–158.

[26] J. Touchard, Sur un problème de configuration et sur les fractions continues, Canad. J. Math. 14 (1952), 2-25.

[27] E. T. Whittaker and G. N. Watson, A Course of Modern Analysis, Cambridge University Press, Cambridge, 1927.