Séminaire Lotharingien de Combinatoire 62 (2009), Article B62a

d-REGULAR SET PARTITIONS AND ROOK PLACEMENTS

ANISSE KASRAOUI

Université de Lyon; Université Claude Bernard Lyon 1

Institut Camille Jordan CNRS UMR 5208 43, boulevard du 11 novembre 1918 F-69622, Villeurbanne Cedex

                               anisse@math.univ-lyon1.fr

Abstract. We use a classical correspondence between set partitions and rook placements on the triangular board to give a quick picture understanding of the “reduction identity”

|P^{(d)}(n, k)| = |P^{(d−j)}(n − j, k − j)|,

where P^{(d)}(n, k) is the collection of all set partitions of [n] := {1, 2, …, n} into k blocks such that for any two distinct elements x, y in the same block, we have |y − x| ≥ d. We also generalize an identity of Klazar on d-regular noncrossing partitions. Namely, we show that the number of d-regular ℓ-noncrossing partitions of [n] is equal to the number of (d − 1)-regular enhanced ℓ-noncrossing partitions of [n − 1].

1. Introduction

A partition of [n]:={1, 2, …, n} is a collection of disjoint and nonempty subsets of [n], called blocks, whose union is [n]. We will denote by P(n, k) the set of partitions of [n] into k blocks and by P_{n} the set of all partitions of [n]. It is well-known that |P_{n}| = B_{n} and |P(n, k)| = S(n, k) where, as usual, |. | denotes cardinality, B_{n} is the n-th Bell number, and S(n, k) is the (n, k)-th Stirling number of the second kind [4].

Given a positive integer d, a partition of [n] is said to be d-regular, if for any two distinct elements x, y in the same block, we have |y − x| ≥ d. We will denote by P_{n}^{(d)} the set of d-regular partitions of [n] and by P^{(d)}(n, k) the set of d-regular partitions of [n] into k blocks. Note that P_{n} = P_{n}^{(1)} and P(n, k) = P^{(1)}(n, k). It seems that d-regular partitions were first considered by Prodinger [11] who called them d-Fibonacci partitions. A natural question that arises is: how many d-regular partitions of [n] are there? Prodinger [11] solved this question by showing that the number of d-regular partitions of [n] equals the number of partitions of [n − d + 1], that is

|P_{n}^{(d)}| = |P_{n−d+1}| = B_{n−d+1}.  (1.1)

Later, Yang [14] obtained a refinement of Prodinger’s result by showing (see the proof of [14, Theorem 2]) that the number of d-regular partitions in P(n, k) is equal to the number of partitions in P(n − d + 1, k − d + 1), i.e.,

|P^{(d)}(n, k)| = |P(n − d + 1, k − d + 1)| = S(n − d + 1, k − d + 1).  (1.2)

Note that Prodinger’s “algebraic proof” [11] of (1.1) can be extended to prove (1.2), and that Chu and Wei [3] have recently rediscovered (1.2) with a generating function proof. Zeng [15] also provided a recursive proof of (1.2). At this point, it is legitimate to ask of a bijection between P_{n}^{(d)} and P_{n−d+1}. In the case d = 2, Prodinger [11] has given such a bijection that he attributed to F. J. Urbanek. He also said that Urbanek’s bijection can be extended to arbitrary d, but he adds that “this is more complicated to describe and therefore is omitted.” Yang [14] also gave another bijection in the case d = 2. The unique explicit bijective explanation of (1.2) that we have found in the literature is due to Chen et al. [1] by means of a simple reduction algorithm which transforms d-regular partitions of [n] into k blocks to (d − 1)-regular partitions of [n − 1] into k − 1 blocks.

The main purpose of this short note is to give a quick “picture understanding” of (1.2). More precisely, we will show in Section 2 that the model of rook placements on the triangular board for set partitions provides an elegant and quick explanation of (1.2). It must be noted that, although it appears that our picture proof is equivalent to the reduction algorithm of Chen et al. [1], the “picture approach” has its own merit. In particular, we hope that this approach lets the reader never forget why these identities hold. We will also generalize an identity of Klazar on the enumeration of noncrossing d-regular partitions in Section 3. Finally, we will conclude the paper by studying the “behavior of nestings under reduction.”

2. Picture proof of (1.2)

The n-th triangular board Δ_{n} is the board consisting of n−1 columns with n−1 cells in the first (leftmost) column, n − 2 in the second, …, and 1 in the rightmost column. For convenience, we also join pending edges at the right and at the top of Δ_{n}. See Figure 1 for an illustration of Δ_{9} (the rooks should be ignored at this point). A rook placement is a way of placing non-attacking rooks on such a board, i.e., putting no two rooks in the same row or column. Let RR(n, k) be the set of all rook placements of n − k rooks on the triangular shape Δ_{n}. Figure 1 gives an example of an element of RR(9, 4), where a rook is indicated by an R.

R R R R R

Figure 1. A rook placement

It is well-known that |RR(n, k)| = S(n, k). We will show this with a classical bijection (see e.g. [13, p.75]). Define

Δ : P(n, k) ↦ RR(n, k)

d-REGULAR SET PARTITIONS AND ROOK PLACEMENTS 3

as follows. First, label the rows (including the pending edge) of Δ_{n} from bottom to top in decreasing order by n, n − 1, …, 1 and columns (including the pending edge) from left to right in increasing order by 1, 2, …, n. Then, if π ∈ P(n, k), we construct Δ(π) by placing a rook in the cell on the column labeled by i and the row labeled by j if and only if (i, j) is an arc of π, that is i < j, i and j belong to the same block B of π, and there are no element in B between i and j. An illustration is given in Figure 2.

R R R R R_{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11}^{11}^{10}^{9}^{8}^{7}^{6}^{5}^{4}^{3}^{2}^{1}

Figure 2. The rook placement Δ(1 9/2 6 10/3/4 8/5/7 11).

It is easy to show that the map Δ is well defined and bijective. Moreover, this map “transforms” the d-regularity into a nice property of rook placements. Let RR^{(d)}(n, k) be the set of rook placements in RR(n, k) such that there are no rooks in the (d − 1) highest cells of each column. Note that RR(n, k) = RR^{(1)}(n, k). Then it is immediate to check the following result.

Proposition 2.1. The map Δ establishes a bijection between P^{(d)}(n, k) and RR^{(d)}(n, k). In particular, we have |RR^{(d)}(n, k)| = |P^{(d)}(n, k)|.

As an illustration, a partition π of [9] is 3-regular if and only if its corresponding placement Δ(π) contains no rook in the colored zone of Δ_{9} drawn in the following picture.

For instance, the partition π_{1} = 1 9/2 6 10/3/4 8/5/7 11 belongs to P^{(4)}(11, 6), and the corresponding rook placement Δ(π_{1}) (drawn in Figure 2) belongs to RR^{(4)}(11, 6). Similarly, the partition π_{2} = 1 7 9/2 4 6 8/3/5 belongs to P^{(2)}(9, 4) and the corresponding rook placement Δ(π) (drawn in Figure 1) belongs to RR^{(2)}(9, 4).

It is now immediate to recover (1.2). Indeed, invoking Proposition 2.1, it suffices to show that |RR^{(d)}(n, k)| = |RR(n − d + 1, k − d + 1)|, which is obvious. For d ≥ 2 and 1 ≤ j ≤ d − 1, let

Ψ_{j} : RR^{(d)}(n, k) ↦ RR^{(d−j)}(n − j, k − j)

the map which associates to a placement ρ ∈ RR(n, k) the rook placement Ψ_{j}(ρ) obtained from ρ by deleting the j highest cells on each column of ρ. An illustration is given in Figure 3.

R ^{R} ^{R} ^{R} ^{R}  \overline{}Ψ_{2}  ^{R R R R R}

Figure 3. The mapping Ψ_{2}.

It is immediate to check that the map Ψ_{j} is well defined and establishes a bijection between RR^{(d)}(n, k) and RR^{(d−j)}(n − j, k − j), and thus |RR^{(d)}(n, k)| = |RR^{(d−j)}(n − j, k − j)|, i.e., by Proposition 2.1,

|P^{(d)}(n, k)| = |P^{(d−j)}(n − j, k − j)|,  (2.1)

which yields (in fact is equivalent) to (1.2) (set j = d − 1).

In the paper [1], Chen et al. have introduced a “reduction algorithm” (described in the next section), Φ, which transforms bijectively d-regular partitions in P(n, k) to (d − 1)- regular partitions in P(n−1, k−1). It is worth noting that the map Ψ_{1} is in fact equivalent to the reduction algorithm Φ, since it can be factorized as

Ψ_{1} = Δ ∘ Φ ∘ Δ^{−1}.  (2.2)

However, as explained in the introduction, the “picture approach” leads to a quick and obvious explanation of (1.2) and (1.1).

3. Reduction of ℓ-noncrossing d-regular partitions

A partition of [n] is said to be noncrossing (or abab-free) if whenever four elements 1 ≤ a < b < c < d ≤ n are such that a, c are in the same block and b, d are in the same block, then the two blocks coincide. The terminology corresponds to the fact that a noncrossing partition admits a linear representation in which the arcs intersect only at elements of [n]. Recall that the linear representation, sometimes called standard representation, of a partition of [n] is the graph obtained by arranging the integers 1, 2, …, n on a line in increasing order from left to right and then joining two integers i and j by an arc drawn above the line if and only if i and j belong to the same block B and there are no elements in B between i and j (see Figure 4).

In the paper [7], Klazar has investigated noncrossing d-regular partitions, more precisely their behavior “under reduction.” Denote by N C^{(d)}(n, k) the set of noncrossing partitions

1 2 3 4 5 6 7 8  1 2 3 4 5 6 7 8

Figure 4. Two partitions in linear representation. Left: 1 6 7/2 3 5 8/4 is crossing, Right: 1/2 5 6/3 4/7 8 is noncrossing.

in P^{(d)}(n, k), and set N C(n, k) := N C^{(1)}(n, k), so that N C(n, k) is the collection of noncrossing partitions of [n] into k blocks. It is well known that the number of noncrossing partitions of [n] is given by the n-th Catalan number C_{n} := \frac{1}{n+1} \binom{2n}{n} and that

|N C(n, k)| = N(n, k),

where N(n, k) is the (n, k)-th Narayana number

N(n, k) = \frac{1}{k}\binom{n}{k − 1}\binom{n − 1}{k − 1}.

A set partition is said to be poor if each part has at most two elements. Let N C_{≤2}^{(d)}(n, k) be the set of all poor partitions in N C^{(d)}(n, k). Then Klazar proved, first with a generating function proof [7], later bijectively [8], that

|N C^{(d)}(n, k)| = |N C_{≤2}^{(d−1)}(n − 1, k − 1)|.  (3.1)

An interesting aspect of (3.1) is that the enumeration of N C^{(d)}(n, k) reduces to the enumeration of N C_{≤2}^{(d−1)}(n − 1, k − 1), the latter being easier than the first. It is worth noting that Klazar [7, Theorem 2.6] uses it to write |N C^{(d)}(n, k)| as a sum of binomial coefficients. Note that the specialization d = 2 of (3.1) was first obtained by Simion and Ullman [12]. By using terminology introduced recently by Chen et al. [2], we now establish a generalization of (3.1).

Let π be a partition of [n]. A sequence (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{r}, j_{r}) of arcs of π is said to be an enhanced r-crossing if i_{1} < i_{2} < ⋯ < i_{r} ≤ j_{1} < j_{2} < ⋯ < j_{r}; if in addition i_{r} < j_{1}, it is an r-crossing. Illustrations are given in Figure 5. Note that an r-crossing is just a particular enhanced r-crossing but the reverse is not true in general.

i_{1} i_{2}  i_{r−1} i_{r} = j_{1} j_{2}  j_{r−1}j_{r} .......  ....... i_{2}  (a)  i_{1} i_{2}  i_{r−1}i_{r} j_{1} j_{2}  j_{r−1}j_{r} .......  ....... i_{2}  (b)

Figure 5. (a)(b): enhanced r-crossing, (b): r-crossing.

A set partition with no r-crossing (respectively, enhanced r-crossing) is called r-non-crossing (respectively, enhanced r-noncrossing). With this terminology, a set partition is noncrossing if and only if it is 2-noncrossing; it is poor and noncrossing if and only if it is enhanced 2-noncrossing. In particular, Klazar’s result can be rewritten as follows: The number of 2-noncrossing partitions in P^{(d)}(n, k) is equal to the number of enhanced 2-noncrossing partitions in P^{(d−1)}(n − 1, k − 1). Therefore, it is the particular case r = 2 of the following result.

Theorem 3.1. Let r, d be two integers ≥ 2. The following quantities are equal: • the number of r-noncrossing partitions in P^{(d)}(n, k),

• the number of enhanced r-noncrossing partitions in P^{(d−1)}(n − 1, k − 1).

The reduction algorithm of Chen et al., Φ, provides a simple bijective proof of Klazar’s result (3.1), and this is the main result of the paper [1]. This proof can be easily generalized to prove Theorem 3.1.

First, recall the original description of the reduction algorithm of Chen et al. [1],

Φ : P^{(d)}(n, k) ↦ P^{(d−1)}(n − 1, k − 1), d ≥ 2.

If π ∈ P^{(d)}(n, k), then construct the linear representation of τ = Φ(π) from the linear representation of π by:

• Replacing each arc (i, j) of the linear representation of π by the arc (i, j − 1).

• Deleting the vertex n. An example is given in Figure 6. Identifying a set partition with its linear representa-

tion, it is not difficult to see that Φ : P^{(d)}(n, k) ↦ P^{(d−1)}(n − 1, k − 1) is well defined and bijective, and that Φ and Ψ_{1} are related by the identity (2.2).

1 2 3 4 5 6 7 8 9 10 11  \overline{}Φ  _{1 2 3 4 5 6 7 8 9 10}

Figure 6. The map Φ sends 1 9/2 6 10/3/4 8/5/7 11 to 1 8/2 5 /3/4 7 10/6 9.

Proof of Theorem 3.1. It suffices to show that the reduction algorithm Φ establishes a bijection between r-noncrossing partitions of P^{(d)}(n, k) and enhanced r-noncrossing partitions of P^{(d−1)}(n − 1, k − 1). Since Φ is a bijection between P^{(d)}(n, k) and P^{(d−1)}(n − 1, k − 1), it suffices to show that a partition π is r-noncrossing if and only if Φ(π) is enhanced r-noncrossing.

Let π be a set partition of [n] and set τ = Φ(π). Suppose τ has an enhanced r-crossing, that is, there exists a sequence (i_{1}, j_{1}), …, (i_{r}, j_{r}) of arcs of τ such that i_{1} < i_{2} < ⋯ < i_{r} ≤ j_{1} < j_{2} < ⋯ < j_{r}. By definition of Φ, the pairs (i_{1}, j_{1}+1), …, (i_{r}, j_{r}+1) are arcs of π, and they thus form an r-crossing of π (since i_{1} < i_{2} < ⋯ < i_{r} < j_{1} +1 < j_{2} +1 < ⋯ < j_{r} +1). We thus have proved that Φ(π) has an enhanced r-crossing implies that π has an rcrossing, or, equivalently, π is r-noncrossing implies that Φ(π) is enhanced r-noncrossing. The converse can be justified in the same manner.

□

4. Concluding remarks

A natural partner of the notion of crossing is, by several aspects (see e.g. [2, 6, 9]), the notion of nesting. It is thus natural to study the “behavior of nestings under reduction.” Let π be a partition of [n]. A sequence (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{r}, j_{r}) of arcs of π is said to be an r-nesting if i_{1} < i_{2} < ⋯ < i_{r} < j_{r} < ⋯ < j_{2} < j_{1}. This means a subgraph as drawn in Figure 7.

i_{1} i_{2}  i_{r−1}i_{r} j_{r} j_{r−1}  j_{2} j_{1} .......  .......

Figure 7. An r-nesting

A set partition with no r-nesting is called r-nonnesting. We will denote by N N^{(d)}(n, k) the set of 2-nonnesting partitions in P^{(d)}(n, k). Set N N (n, k) := N N^{(1)}(n, k), so that N N (n, k) is just the set of 2-nonnesting partitions, also called nonnesting partitions, of [n] into k blocks. It is well known that

|N N (n, k)| = |N C(n, k)| = N(n, k),

where N(n, k) is the (n, k)-th Narayana number.

Theorem 4.1. Let r, d be two integers ≥ 2. Then, for any nonnegative integer j ≤ d − 1, the following quantities are equal:

• the number of r-nonnesting partitions in P^{(d)}(n, k),

• the number of r-nonnesting partitions in P^{(d−j)}(n − j, k − j).

Consequently, setting j = d−1 in Theorem 4.1, we get that the number of r-nonnesting partitions in P^{(d)}(n, k) equals the number of r-nonnesting partitions in P(n − d + 1, k − d + 1). In particular, setting r = 2, we obtain that the cardinality of N N^{(d)}(n, k) is given by

|N N^{(d)}(n, k)| = N(n − d + 1, k − d + 1) = \frac{1}{k − d + 1}\binom{n − d + 1}{k − d}\binom{n − d}{k − d},

and, thus, the number of d-regular 2-nonnesting partitions of [n] is the Catalan number C_{n−d+1}.

Theorem 4.1 can be proved easily by using the reduction algorithm (similarly to the proof of Theorem 3.1), but we will use here the model of rook placement, which leads to a quick picture proof. Indeed, it is easy to see that the correspondence Δ : P(n, k) ↦ RR(n, k) sends any r-nesting of a set partition π to a NE-chain of length r in the rook placement Δ(π), that is, a sequence of r rooks in Δ(π) such that any rook in the sequence is strictly above and to the right of the preceding rook in the sequence (see e.g. [5, 10]). It follows that the number of r-nonnesting partitions in P^{(d)}(n, k) is equal to the number of rook placements in RR^{(d)}(n, k) whose length of longest NE-chain is ≤ r − 1. Applying Ψ_{j} : RR^{(d)}(n, k) ↦ RR^{(d−j)}(n − j, k − j), which obviously preserves the length of longest NE-chain, leads to the desired result. Note that the model of rook placement can be used to prove Theorem 3.1, but the proof would be heavier than the proof given in this paper.

References

[1] W.Y.C. Chen, E.Y.P. Deng and R.R.X. Du, Reduction of m-regular noncrossing partitions, Europ. J. Combin. 26 (2005), 237–243.

[2] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley and C.H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007), 1555–1575.

[3] W. Chu and C. Wei, Set partitions with restrictions, Discrete Math. 308 (2008), 3163–3168.

[4] L. Comtet, Analyse combinatoire, Tome 2, Presses universitaires de France, 1970.

[5] A. Kasraoui, Increasing and decreasing sequences of length two in 01-fillings of moon polyominoes, preprint (2008); arχiv:0812.0799.

[6] A. Kasraoui and J. Zeng, Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. 13 (2006), no. 1, Research Paper 33.

[7] M. Klazar, On abab-free and abba-free set partitions, Europ. J. Combin. 17 (1996), 53–68.

[8] M. Klazar, On trees and noncrossing partitions, Discrete Appl. Math. 82 (1998), 263–269.

[9] M. Klazar, On identities concerning the numbers of crossings and nestings of two edges in matchings, SIAM J. Discrete Math. 20 (2006), 960–976.

[10] C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math. 37 (2006), 404–431.

[11] H. Prodinger, On the number of Fibonacci partitions of a set, Fibonacci Quart. 19 (1981), 463–465.

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

[13] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, 1999.

[14] W. Yang, Bell numbers and k-trees, Discrete Math. 156 (1996), 247–252.

[15] J. Zeng, personal communication (2009).