A Bijective Answer to a Question of Simion

Richard Ehrenborg Department of Mathematics

University of Kentucky Lexington, KY 40506-0027

USA

richard.ehrenborg@uky.edu

Gábor Hetyei

Department of Mathematics and Statistics

UNC-Charlotte Charlotte, NC 28223-0001

USA

ghetyei@uncc.edu

Margaret Readdy Department of Mathematics

University of Kentucky Lexington, KY 40506-0027

USA

margaret.readdy@uky.edu

Abstract

We present a bijection between balanced Delannoy paths of length 2n and the faces of the n-dimensional Simion type B associahedron. This polytope is also known as the Bott-Taubes polytope and the cyclohedron. This bijection takes a path with k up steps (and k down steps) to a (k − 1)-dimensional face of the Simion type B associahedron. We give two presentations of this bijection, one recursive and one non-recursive.

1 Introduction

Simion constructed a type B associahedron Q_{n}^{B} whose facets correspond to centrally symmetric triangulations of a regular (2n + 2)-gon; see [10]. The vertices correspond to B-diagonals, that is, pairs of diagonals that are centrally symmetric. This polytope is also known as the Bott-Taubes polytope [4] and the cyclohedron [12]. We follow Simion’s convention and view this polytope Q_{n}^{B} as a simplicial polytope.

Simion observed that the number of (k−1)-dimensional faces of the type B associahedron is given by

f_{k−1}(Q_{n}^{B}) = \binom{n}{k} · \binom{n + k}{k}.  (1)

Simion asked if there is a combinatorial proof of this identity. A combinatorial interpretation for the right-hand side of equation (1) is the number of lattices paths between (0, 0) and (2n, 0) taking k up steps (1, 1), k down steps (1, −1), and n − k horizontal steps (2, 0). Such paths are known as balanced Delannoy paths. We provide a bijection between the faces of the type B associahedron and balanced Delannoy paths.

Our approach is based upon the paper [7], where the Simion type B associahedron Q_{n}^{B} is shown to be a pulling triangulation of the Legendre polytope. This polytope, also known as the full type A root polytope, is the convex hull of the set {e_{i} − e_{j} : 1 ≤ i, j ≤ n + 1, i ≠ j}. Hence it is natural to encode the vertices of the polytope Q_{n}^{B} with the pairs (i, j) where i, j ∈ {1, 2, …, n + 1} and i ≠ j. We view these pairs as directed edges on the vertex set {1, 2, …, n + 1}. We call these directed edges arrows to be consistent with [7] and not to overuse the term edge. Thus a face of the type B associahedron Q_{n}^{B} corresponds to a digraph on the vertex set {1, 2, …, n + 1}.

In the paper [7] a condition is given on pairs of arrows when their associated B-diagonals cross. Reformulating this condition yields a description of those digraphs that correspond to faces of Q_{n}^{B}; see Proposition 2. We call these digraphs facial.

After preliminaries, in Section 3 we give a bijection between paths that never go below the x-axis, known as Schröder paths, and facial digraphs with the extra condition that all the arrows are directed backwards. Next, we extend this bijection to all digraphs and facial digraphs. This presentation of the bijection is recursive. In Section 4 we reformulate this presentation to obtain a non-recursive description of the bijection. Lastly, we end with concluding remarks.

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

Figure 1: A set of B-diagonals corresponding to a 7-dimensional face of Q_{10}^{B}.

2 Preliminaries

2.1 The Simion type B associahedron

Following Simion [10], for a centrally symmetric convex (2n + 2)-gon label its vertices in the clockwise order with 1, 2, …, n, n + 1, \overline{1}, \overline{2}, …, \overline{n}, \overline{n + 1}. Let Γ_{n}^{B} denote the simplicial complex whose n · (n + 1) vertices arise from the B-diagonals of the (2n + 2)-gon, that is, (i) diagonals joining antipodal pairs of points, and (ii) antipodal pairs of noncrossing diagonals. In the first case, the diagonals are pairs of the form \{i, \overline{i}\} satisfying 1 ≤ i ≤ n+1. In the second case, the B-diagonals are either of the form \{\{i, j\}, \{\overline{i}, \overline{j}\}\} with 1 ≤ i < i+1 < j ≤ n + 1 or of the form \{\{i, \overline{j}\}, \{\overline{i}, j\}\} with 1 ≤ j < i ≤ n + 1. Throughout the paper we identify \overline{i} with i + n + 1. The simplicial complex Γ_{n}^{B} is then the family of sets of pairwise noncrossing B-diagonals.

Simion [10, Theorem 1] showed that the simplicial complex Γ_{n}^{B} is the boundary complex of an n-dimensional convex polytope Q_{n}^{B}, now known as the Simion type B associahedron. See Proposition 1 and Corollary 1 in [10] for Simion’s computation of the f- and h-vectors of this polytope.

We define an arrow to be pair (i, j) where 1 ≤ i, j ≤ n + 1 and i ≠ j. We call i the tail of the arrow (i, j) and j the head of the arrow. An arrow (i, j) is a forward arrow if i < j and a backward arrow if i > j. Two undirected arcs {a, b} and {c, d} cross if a < c < b < d or c < a < d < b where we assume a < b and c < d. Furthermore, the arc {a, b} nests the arc {c, d} if a < c < d < b where we again assume a < b and c < d. These two concepts naturally lift to arrows.

Define a bijection between B-diagonals and arrows as follows.

Definition 1. For a B-diagonal {{u, v}, {u + n + 1, v + n + 1}} where 1 ≤ u ≤ n + 1, u < v ≤ u + n + 1 and the addition v + n + 1 is modulo 2n + 2, let the associated arrow be (w, u) where w ≡ v − 1 mod n + 1 and 1 ≤ w ≤ n + 1. The case of two antipodal points is covered when v = u + n + 1. The resulting arrow is (u − 1, u) when 2 ≤ u ≤ n + 1 and the arrow is (n + 1, 1) when u = 1.

From the proof of Proposition 5.5 in [7], we have the following result.

Proposition 2. A non-empty digraph on the node set {1, 2, …, n + 1} represents a proper face of the Simion type B associahedron Q_{n}^{B} exactly when the following conditions are satisfied:

(1) There are no crossings between arrows.

(2) Forward arrows nest.

(3) A backward arrow cannot nest a forward arrow.

(4) No head of an arrow is the tail of another arrow.

We call such a set of arrows a facial digraph. An example of a facial digraph is shown in Figure 2.

Let P be a polytope with a vertex v. We can pull the vertex v, that is, we consider the convex hull of the polytope P and a new point w, where vw^{⟶} is a small vector in general position pointing outwards from the polytope. Given a polytope P and an ordering of its vertices v_{1}, v_{2}, …, v_{m}, we can pull all the vertices in this given order. Namely, pick a real number 0 < ϵ < 1. When pulling the ith vertex, pull it a distance of ϵ^{i}. The resulting polytope Q is simplicial, that is, the boundary of Q is a triangulation of the boundary of the polytope P. Furthermore, the combinatorics of Q only depends on the original polytope P and the pulling order of the vertices. The idea of pulling triangulation is due to Hudson [9, Lemma 1.4]. See Athanasiadis [2, End of Section 2], Hetyei [8, Section 2.3] and Stanley [11, Lemma 1.1], for modern treatments, as well as the book by de Loera, Rambau, and Santos [6] for other types of triangulations.

We identify the arrow (i, j) with the point e_{j} − e_{i} in (n + 1)-dimensional Euclidean space. The convex hull of these n · (n + 1) points forms a convex polytope known as the Legendre polytope [8]. This polytope is also known as the full root polytope of type A; see [1, 5]. Hetyei proved that any pulling triangulation of the Legendre polytope yields a simplicial polytope whose f-vector is given by (1); see [8]. In the paper [7] the authors show that there is a pulling triangulation of Legendre polytope such that the resulting polytope is the Simion type B associahedron. Proposition 2 arises from understanding this pulling triangulation.

1 2 3 4 5 6 7 8 9 10 11

Figure 2: The facial digraph corresponding to the set of B-diagonals in Figure 1.

3 A bijection between the faces of Γ_{n}^{B} and Delannoy paths

In this section we establish a bijection between the faces of Γ_{n}^{B} and balanced Delannoy paths of length 2n in such a way that (k − 1)-dimensional faces correspond to Delannoy paths with k up steps, thus answering Simion’s question. The study of Delannoy paths has a long history. See [3] for a comprehensive survey.

Definition 3. A balanced Delannoy path of length 2n is a lattice path starting at (0, 0), ending at (2n, 0) and using only steps of the following three types: up steps (1, 1), down steps (1, −1) and horizontal steps (2, 0). A Schröder path is a balanced Delannoy path that never goes below the horizontal axis.

More generally, a Delannoy path is a path taking the steps (1, 1), (1, −1) and (2, 0) with no condition where the path ends. In this paper we only work with balanced Delannoy paths.

Let U, D and H denote the up, down and horizontal steps, respectively. Let the length of the letters U and D each to be 1, whereas the length of the letter H be 2. Note that the length of a word is the sum of the lengths of its letters. For example, the word DUUHH has length 7. A Delannoy path is uniquely encoded by a word in these three letters. We call the associated word a Delannoy word. A balanced Delannoy path of length 2n corresponds to a word in which the number k of occurrences of U is the same as the number of occurrences of D, and the number of occurrences of H is n − k. We call such a word balanced. Hence the number of Delannoy paths of length 2n with k up steps is given by the multinomial coefficient \binom{n+k}{k,k,n−k} = \binom{n+k}{k}\binom{n}{k}, which is the same as the number of (k −1)-dimensional faces in the Simion type B associahedron Q_{n}^{B}; see equation (1). A Schröder word is a balanced Delannoy word such that the associated path never goes below the horizontal axis. Let α · β denote the concatenation of the two words α and β.

Let ℙ be the set of positive integers ordered by the natural order. We will consider facial digraphs A on a finite subset V of the positive integers. Recall that the definition of a facial digraph is the conditions appearing in Proposition 2. We view a digraph A as a pair consisting of a node set V = V (A) and an arrow set E = E(A). For a facial digraph A on a non-empty finite set of nodes V and W ⊆ V let A_{W} denote the induced subgraph on W.

Let A be a facial digraph of backward arrows on a non-empty finite set of nodes V ⊆ ℙ and let v be the minimal element of V. We define the Schröder word SP(A) of the facial digraph A by the following recursive definition.

(i) If the set V only consists of one node, that is, V = {v}, let SP(A) be the empty word ϵ.

(ii) If the minimal node v is an isolated node of A, let SP(A) be the concatenation H · SP(A_{V −{v}}).

(iii) Lastly, when the node v is not isolated then since v is the least element, there is necessarily a backward arrow (x, v) going into v. Let w be the smallest node such that (w, v) is an arrow of A, that is, w = min({x ∈ V : (x, v) ∈ A}). Define SP(A) by

SP(A) = U · SP(A_{V ∩(v,w]}) · D · SP(A_{V −(v,w]}).

Lemma 4. Let A be a facial digraph on a set of nodes of size n + 1 consisting of exactly k backward arrows. The Schröder word SP(A) then has length 2n and has exactly k copies of the letters U and k copies of the letters D.

Proof. Both statements follow by induction on n. The first statement follows from the fact that the two sets of nodes V ∩ (v, w] and V − (v, w] are complements of each other. The second statement follows by observing that the noncrossing property ensures that each arrow in A is either the arrow (w, v), an arrow in A_{V ∩(v,w]}, or an arrow in A_{V −(v,w]}.

Proposition 5. The map SP is a bijection between the set of all facial digraphs consisting only of backward arrows on the set of n + 1 nodes and all Schröder words of length 2n.

Proof. Given a Schröder word α of length 2n and a node set V = {v_{1} < v_{2} < ⋯ < v_{n+1}}, the inverse map is computed recursively as follows. If α is the empty word ϵ then the inverse image is the isolated node v_{1}. If the word α begins with H, that is, α = H · β where β has length 2n − 2, compute the inverse image of β on the nodes {v_{2}, v_{3}, …, v_{n+1}} and add the node v_{1} as an isolated node. Otherwise factor α uniquely as U · β · D · γ, where β and γ are Schröder words of lengths 2p and 2n − 2p − 2, respectively. Compute the inverse image of β on the nodes {v_{2}, v_{3}, …, v_{p+2}}. Similarly, compute the inverse image of γ on the nodes {v_{1}, v_{p+3}, v_{p+4}, …, v_{n+1}}. Take the union of these two digraphs and add the backward arrow (v_{p+2}, v_{1}).

We now extend the bijection SP to all facial digraphs. In order to do so we introduce a twisting operation tw on each digraph A that has a forward arrow from the least element v ∈ V to the largest element w ∈ V. The twisted digraph tw(A) is a digraph on the node set V − {v} with arrow set

E(tw(A)) = E(A_{V −{v}}) ∪ {(w, z) : (v, z) ∈ A, z ≠ w}.

In other words, we remove the least node v and replace each forward arrow (v, z) starting at v with a backward arrow (w, z). Note that there is no backward arrow (z, v) in A as v is the tail of the forward arrow (v, w).

Lemma 6. Let V be a node set whose smallest (respectively, largest) node is v (respectively, w). The twisting map is a bijection from the set of facial digraphs on the set V containing the forward arrow (v, w) to the set of facial digraphs on the set V − {v}.

Proof. We claim that the twisted digraph tw(A) is a facial digraph. Note that the restriction A_{V −{v}} is a facial digraph. If there are no forward arrows in A of the form (v, z) where z < w, the equality tw(A) = A_{V −{v}} holds and the claim is true. Hence assume that there are forward arrows of the form (v, z). We need to show that the digraph remains facial after adding the backward arrow (w, z). We verify conditions (1) through (4) of Proposition 2 in order. If the arrow (w, z) crosses an arrow (x, y) then the arrow (v, z) already crossed this arrow in A, verifying condition (1). Since we did not introduce any new forward arrows, condition (2) holds vacuously. Assume that the backward arrow (w, z) nests a forward arrow (x, y). Then the forward arrows (v, z) and (x, y) did not nest in A, verifying (3). Condition (4) holds directly, proving the claim.

The twisting map is one-to-one. The inverse has the node set V (tw^{−1}(B)) = V (B) ∪ {v} and the arrow set is given by

E(tw^{−1}(B)) = {(v, w)} ∪ E(B_{V ∩(v,w)}) ∪ {(v, z) : (w, z) ∈ B},

where V ∩ (v, w) denotes the intersection of the set V with the open interval (v, w). Note that in case the node w was a ‘tail node’, the inverse map switches it back to being a ‘head node’.

We now extend the bijection SP to a map DP which applies to all facial digraphs. Let A be facial digraph on the node set V. Furthermore, let v and w be the minimal, respectively, the maximal node of the node set V, that is, v = min(V) and w = max(V).

(i) If the facial digraph A has no forward arrows, let DP(A) = SP(A).

(ii) If the facial digraph A has a forward arrow, let (x, y) be the forward arrow which nests the other forward arrows. Since v ≤ x < y ≤ w, observe that the digraphs A_{V ∩[v,x]} and A_{V ∩[y,w]} have no forward arrows. Define DP(A) to be the concatenation

DP(A) = SP(A_{V ∩[v,x]}) · D · DP(tw(A_{V ∩[x,y]})) · U · SP(A_{V ∩[y,w]}).

As an extension of Lemma 4 we have the following lemma.

Lemma 7. Let A be a facial digraph on a set V of n+1 nodes and assume that A consists of k arrows. Then the balanced Delannoy word DP(A) has length 2n and has exactly k copies of the letters U and D, respectively.

Proof. We only have to prove the lemma for the second case defining DP. Assume that V ∩ [v, x] and V ∩ [y, w] have cardinalities a and b, respectively. Then the middle part V ∩ [x, y] has size n − a − b + 3. Thus tw(A_{V ∩[x,y]}) has n − a − b + 2 nodes. Hence the total

1 2 3 4 5 6 7 8 9 10 11

Figure 3: The modified set of arrows obtained from the set in Figure 2.

length is 2·(a−1)+2·(n−a−b+1)+2·(b−1)+2 = 2n. For the second case of the lemma, assume that the restricted digraphs A_{V ∩[v,x]} and A_{V ∩[y,w]} have c and d arrows, respectively. Since there is no arrow nesting the forward arrow (x, y), the middle digraph A_{V ∩[x,y]} has k − c − d arrows. Thus the twisted digraph has one less arrow, namely k − c − d − 1. Hence the total number of U letters is c + (k − c − d − 1) + d + 1 = k, proving the second claim.

We now extend Proposition 5 to all facial digraphs.

Theorem 8. The map DP is a bijection between the set of all facial digraphs on a set of n + 1 nodes and the set of all balanced Delannoy words of length 2n.

Proof. The inverse of the map DP is computed as follows. Let α be a balanced Delannoy word of length 2n and V be a node set {v_{1} < v_{2} < ⋯ < v_{n+1}}. If the Delannoy word α is a Schröder word, apply the inverse map of Proposition 5. Otherwise, we can factor the Delannoy word α uniquely as β·D·γ·U ·δ, where γ is a balanced Delannoy word, and β and δ are Schröder words. Note that the factor β · D is uniquely determined by the fact it is the shortest initial segment in which the number of D letters exceeds the number of U letters, in other words, the encoded path ends with the first down step going below the horizontal axis. By a symmetric argument, U · δ is the shortest final segment with one more U than the number of D’s. Assume that β, γ and δ have lengths 2p, 2q and 2n − 2p − 2q − 2, respectively. Apply the inverse map from the proof of Proposition 5 to the words β and δ to obtain digraphs on {v_{1}, v_{2}, …, v_{p−1}}, respectively {v_{p+q+2}, v_{p+q+3}, …, v_{n+1}}.

By recursion, apply the inverse of DP to γ to obtain a facial digraph on the node set {v_{p+2}, v_{p+3}, …, v_{p+q+2}}. Then apply the inverse of the twisting map to the digraph thus obtained. Finally, take the union of these three digraphs.

4 A non-recursive description of the bijection

We now give non-recursive description of the bijection DP. First we encode a facial digraph with a multiset of indexed letters.

Definition 9. Given a facial digraph A on the node set V, define the associated multiset M(A) with elements from the set of indexed letters {D_{x}, U_{x}, H_{x} : x ∈ ℙ} by the following three steps:

1. For each x < max(V) which is a maximum element in a weakly connected component we add the letter H_{x} to the multiset M(A).

(0,0) (4,0) (16,0) (20,0)

Figure 4: The lattice path associated to the digraph in Figure 2.

2. For each tail x of a forward arrow, consider the set Head(x) = {y > x : (x, y) ∈ A}, that is, the set of heads of forward arrows with tail x. Add a copy of the letter D_{x} to M(A), also add a copy of the letter U_{w} for w = max(Head(x)). Remove the forward arrow (x, w). For each remaining y ∈ Head(x) that is less than w, replace the forward arrow (x, y) with the backward arrow (w, y). The resulting set of arrows has only backward arrows.

3. For each head y of a backward arrow, consider the set Tail(y) = {x > y : (x, y) ∈ A}, that is, the set of tails of backward arrows with head y. Add a copy of U_{y} to M(A). Also add a copy of D_{x} for x ∈ Tail(y) and add a copy of U_{x} for all but the maximum element of Tail(y).

Example 10. For the facial set of arrows A shown in Figure 2, in the first step we add the letters H_{2} and H_{7} to M(A). In the second step we add the letters D_{3}, U_{9}, D_{4}, and U_{7} to M(A), and we remove the forward arrows (3, 9) and (4, 7). We also replace (3, 8) with (9, 8) and (4, 5) with (7, 5). We obtain the set of backward arrows shown in Figure 3. Note that this set of arrows does not need to be facial anymore: in our example, 9 is the head of (10, 9) and (11, 9) and it is also the tail of (9, 8). Finally, in step three we add the letters U_{1}, D_{3}, U_{5}, D_{6}, U_{6}, D_{7}, U_{8}, D_{9}, U_{9}, D_{10}, U_{10}, and D_{11} to M(A). We end up with the multiset

M(A) = {U_{1}, H_{2}, D_{3}, D_{3}, D_{4}, U_{5}, D_{6}, U_{6}, D_{7}, U_{7}, H_{7}, U_{8}, D_{9}, U_{9}, U_{9}, D_{10}, U_{10}, D_{11}}.

Define a linear order on the indexed letters by the inequalities D_{x} < U_{x} < H_{x} < D_{x+1} for all positive integers x. We obtain the lattice path as follows.

Proposition 11. The balanced Delannoy word DP(A) is obtained from the multiset M(A) by reading the indexed letters in order and then omitting the subscripts.

For the set of arrows shown in Figure 2, we obtain the word

UHDDDUDUDUHUDUUDUD.

The lattice path encoded by this word is shown in Figure 4.

Recall that a weakly connected component of a digraph is a connected component in the graph obtained by disregarding the direction of the arrows. In our facial digraphs, the weakly connected components are trees.

A quick outline of a proof of Proposition 11 is as follows. First prove the statement for facial digraphs without forward arrows. In this case, each nonmaximal element x of Tail(y) contributes two consecutive letters D_{x}U_{y}. Next, observe that a digraph and its twisted digraph have the same weakly connected components. Furthermore, the arrows that moved under the twisted operation still have the same set of heads. Hence, after recording the horizontal steps in step (1) we may perform all twisting operations simultaneously in step (2). We leave the remaining details to the reader.

5 Concluding remarks

The faces of the type B associahedron Q_{n}^{B} have a natural order by inclusion. What is the image of this order under our bijection? Is there a different ordering of the balanced Delannoy paths that would yield a more natural order preserving bijection?

6 Acknowledgments

We would like to thank the referee for helping substantially improve the presentation. The first and third author thank the Institute for Advanced Study in Princeton, New Jersey, for a research visit in Summer 2018. This work was partially supported by grants from the Simons Foundation (#429370 to Richard Ehrenborg, #245153 and #514648 to Gábor Hetyei, #206001 and #422467 to Margaret Readdy).

References

[1] F. Ardila, M. Beck, S. Hoşten, J. Pfeifle, and K. Seashore, Root polytopes and growth series of root lattices, SIAM J. Discrete Math. 25 (2011), 360–378.

[2] C. Athanasiadis, h^{∗}-vectors, Eulerian polynomials and stable polytopes of graphs, Electron. J. Combin. 11 (2) (2004), Paper R6.

[3] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Statist. Plan. Inference 135 (2005), 40–54.

[4] R. Bott and C. Taubes, On the self-linking of knots. Topology and physics, J. Math. Phys. 35 (1994), 5247–5287.

[5] S. Cho, Polytopes of roots of type A_{n}, Bull. Austral. Math. Soc. 59 (1999), 391–402.

[6] J. A. de Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, Algorithms Comput. Math. vol. 25, Springer-Verlag, 2010.

[7] R. Ehrenborg, G. Hetyei, and M. Readdy, Simion’s type B associahedron is a pulling triangulation of the Legendre polytope, Discrete Comput. Geom. 60 (2018), 98–114.

[8] G. Hetyei, Delannoy orthants of Legendre polytopes, Discrete Comput. Geom. 42 (2009), 705–721.

[9] J. F. P. Hudson, Piecewise Linear Topology, W. A. Benjamin, Inc., 1969.

[10] R. Simion, A type-B associahedron, Adv. in Appl. Math. 30 (2003), 2–25.

[11] R. P. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333–342.

[12] J. Stasheff, From operads to “physically” inspired theories, Contemp. Math. 202 (1997), 53–81.

2010 Mathematics Subject Classification: Primary 52B05; Secondary 05A15, 05E45, 52B12. Keywords: Delannoy number, type B associahedron, Bott-Taubes polytope, Schröder path, f-vector.

(Concerned with sequences \underline{A006318}, \underline{A008288}, \underline{A008459}, and \underline{A063007}.)

Received June 26 2018; revised versions received October 15 2018; December 13 2018. Published in Journal of Integer Sequences, December 18 2018.

Return to Journal of Integer Sequences home page.