Exercises on Catalan and Related Numbers excerpted from Enumerative Combinatorics, vol. 2 (published by Cambridge University Press 1999) by Richard P. Stanley version of 23 June 1998 19. [l]-[3+] Show that the Catalan numbers Cn = ^x(2™) count the number of elements of the 66 sets Si, (a) < i < (nnn) given below. We illustrate the elements of each Si for n = 3, hoping that these illustrations will make any undefined terminology clear. (The terms used in (vv)-(yy) are defined in Chapter 7.) Ideally Si and Sj should be proved to have the same cardinality by exhibiting a simple, elegant bijection : Si —>• Sj (so 4290 bijections in all). In some cases the sets S{ and Sj will actually coincide, but their descriptions will differ. (a) triangulations of a convex (n + 2)-gon into n triangles by n — 1 diagonals that do not intersect in their interiors (b) binary parenthesizations of a string of n + 1 letters (xx • x)x x(xx ■ x) (x ■ xx)x x(x ■ xx) xx ■ xx (c) binary trees with n vertices (d) plane binary trees with 2n + 1 vertices (or n + 1 endpoints) (e) plane trees with n + 1 vertices (f) planted (i.e., root has degree one) trivalent plane trees with 2n + 2 vertices 221 (g) plane trees with n + 2 vertices such that the rightmost path of each subtree of the root has even length (h) lattice paths from (0, 0) to (n, n) with steps (0,1) or (1,0), never rising above the line y = x (i) Dyck paths from (0,0) to (2n, 0), i.e., lattice paths with steps (1,1) and (1,-1), never falling below the x-axis (j) Dyck paths (as defined in (i)) from (0, 0) to (2n + 2,0) such that any maximal sequence of consecutive steps (1,-1) ending on the x-axis has odd length (k) Dyck paths (as defined in (i)) from (0, 0) to (2n + 2,0) with no peaks at height two. 222 (1) (unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (1,0) or (0,1), ending at the same point, and only intersecting at the beginning and end (m) (unordered) pairs of lattice paths with n—1 steps each, starting at (0,0), using steps (1,0) or (0,1), ending at the same point, such that one path never arises above the other path (n) n nonintersecting chords joining 2n points on the circumference of a circle (o) ways of connecting 2n points in the plane lying on a horizontal line by n nonintersecting arcs, each arc connecting two of the points and lying above the points (p) ways of drawing in the plane n + 1 points lying on a horizontal line L and n arcs connecting them such that (a) the arcs do not pass below L, ((3) the graph thus formed is a tree, (7) no two arcs intersect in their interiors (i.e., the arcs are noncrossing), and (5) at every vertex, all the arcs exit in the same direction (left or right) (q) ways of drawing in the plane n + 1 points lying on a horizontal line L and n arcs connecting them such that (a) the arcs do not pass below L, ((3) the graph thus 223 formed is a tree, (7) no arc (including its endpoints) lies strictly below another arc, and (S) at every vertex, all the arcs exit in the same direction (left or right) hr\ \ AxA A A ^^r\ J ^A (r) sequences of n l's and n — l's such that every partial sum is nonnegative (with — 1 denoted simply as — below) 111--- 11-1— 11—1- 1-11— 1—1—1 — (s) sequences 1 < a± < ■ ■ ■ < an of integers with a, < i 111 112 113 122 123 (t) sequences a\ < a2 < • • • < an_i of integers satisfying 1 < a; < 2i 12 13 14 23 24 (u) sequences ai, a2,..., an of integers such that a± = 0 and 0 < Oj+i < a, + 1 000 001 010 011 012 (v) sequences a±, a2,..., an_i of integers such that a, < 1 and all partial sums are nonnegative 0,0 0,1 1,-1 1,0 1,1 (w) sequences ai,a2, ■ ■ ■ ,an of integers such that a, > —1, all partial sums are non-negative, and c?i + a2 +----\- an = 0 0,0,0 0,1,-1 1,0,-1 1,-1,0 2,-1,-1 (x) sequences a±, a2, ■ ■ ■, an of integers such that 0 < a, < n — i, and such that if i < j, ai > 0, a,j > 0, and aj+i = aj+2 = • • • = aj_i = 0, then j — i > — ctj 000 010 100 200 110 (y) sequences a\, a2, ■ ■ ■, an of integers such that i < < n and such that if i < j < ai} then a,j < ^ 123 133 223 323 333 (z) sequences a±,a2,... ,an of integers such that 1 < a, < i and such that if a, = j, then ai-r < j — r for 1 < r < j — 1 111 112 113 121 123 224 (aa) equivalence classes B of words in the alphabet [n — 1] such that any three consecutive letters of any word in B are distinct, under the equivalence relation uijv ~ ujiv for any words u, v and any i,j 6 [n — 1] satisfying \i — j\ > 2 {0} {1} {2} {12} {21} (For n = 4 a representative of each class is given by 0, 1, 2, 3, 12, 21, 13, 23, 32, 123, 132, 213, 321, 2132.) (bb) partitions A = (Ai,..., An_i) with Ai < n — 1 (so the diagram of A is contained in an (n — 1) x (n — 1) square), such that if A' = (A'1; A2,...) denotes the conjugate partition to A then A^ > Aj whenever Aj > i (0,0) (1,0) (1,1) (2,1) (2,2) (cc) permutations aia2 • • • a2n of the multiset {l2, 22,..., n2} such that: (i) the first occurrences of 1, 2,..., n appear in increasing order, and (ii) there is no subsequence of the form a(5a(5 112233 112332 122331 123321 122133 (dd) permutations aia2 ■ ■ ■ a2n of the set [2n] such that: (i) 1, 3,..., 2n — 1 appear in increasing order, (ii) 2,4,..., 2n appear in increasing order, and (iii) 2i — 1 appears before 2i, 1 < i < n 123456 123546 132456 132546 135246 (ee) permutations a\a2 - • • an of [n] with longest decreasing subsequence of length at most two (i.e., there does not exist i < j < k, > a,j > a&), called 321-avoiding permutations 123 213 132 312 231 (ff) permutations a\a2 ■ ■ ■ an of [n] for which there does not exist i < j < k and cij < ak < cii (called 312-avoiding permutations) 123 132 213 231 321 (gg) permutations w of [2n] with n cycles of length two, such that the product (1,2,..., 2n)-w has n + 1 cycles (1,2,3,4,5,6)(1,2)(3,4)(5,6) = (1)(2,4, 6) (3) (5) (1,2,3,4,5,6)(1,2)(3,6)(4,5) = (1)(2, 6)(3, 5)(4) (1,2,3,4,5,6)(1,4)(2,3)(5,6) = (1, 3)(2)(4, 6)(5) (1,2,3,4,5,6)(1,6)(2,3)(4,5) = (1, 3, 5)(2)(4)(6) (1,2,3,4,5,6)(1,6)(2,5)(3,4) = (1, 5)(2,4) (3) (6) 225 (hh) pairs (u, v) of permutations of [n] such that u and v have a total of n + 1 cycles, and uv = (1,2,... ,n) (1)(2)(3) • (1,2,3) (1,2,3) •(1)(2)(3) (1,2)(3) • (1,3)(2) (1,3)(2).(1)(2,3) (1)(2,3)-(1,2)(3) (ii) permutations Oia2 ■ ■ ■ an of [n] that can be put in increasing order on a single stack, defined recursively as follows: If 0 is the empty sequence, then let 5(0) = 0. If w = unv is a sequence of distinct integers with largest term n, then S(w) = S(u)S(v)n. A stack-sortable permutation w is one for which S(w) = w. "-1 I- 0,10,2 • • • Q>n For example, 4123 12 123 1234 123 132 213 312 321 (jj) permutations a±02 ■ ■ ■ an of [n] that can be put in increasing order on two parallel queues. Now the picture is 123 132 213 231 312 (kk) fixed-point free involutions w of [2n] such that if i < j < k < I and w(i) = k, then w(j) ^ / (in other words, 3412-avoiding fixed-point free involutions) (12)(34)(56) (14)(23)(56) (12)(36)(45) (16)(23)(45) (16)(25)(34) (11) cycles of length 2n + 1 in &2n+i with descent set {n} 2371456 2571346 3471256 3671245 5671234 (mm) Baxter permutations (as defined in Exercise 55) of [2n] or of [2n + 1] that are reverse alternating (as defined at the end of Section 3.16) and whose inverses are reverse alternating 132546 153426 354612 561324 563412 1325476 1327564 1534276 1735462 1756342 226 (nn) permutations w of [n] such that if w has £ inversions then for all pairs of sequences (aua2,..., ae), (h, b2,..., be) e[n- 1}£ satisfying ^ — ^01 ^02 ' ' ' Sat — ^61 ^62 ' ' ' where Sj is the adjacent transposition + 1), we have that the ^-element multisets {ai, 0,2, ■ ■ ■, ag] and {b\, 62, ■ ■ ■ ,bg} are equal (thus, for example, w = 321 is not counted, since w = S1S2S1 = S2S1S2, and the multisets {1,2,1} and {2,1,2} are not equal) 123 132 213 231 312 (00) permutations w of [n] with the following property: Suppose that w has £ inversions, and let R(w) = {(ai,..., at) G [n - l]e : w = saisa2 ■ ■ ■ sat}, where Sj is as in (nn). Then a,ia,2 ■ ■ ■ = £\. (ai,...,at)eR(w) R(123) = {0}, i2(213) = {(1)}, i2(231) = {(1, 2)} i2(312) = {(2,1)}, #(321) = {(1, 2,1), (2,1, 2)} (pp) noncrossing partitions of [n], i.e., partitions 7r = {Bi,... ,Bk} G nn such that if a < b < c < d and a, c G Bi and b, d G Bj, then i = j 123 12-3 13-2 23-1 1-2-3 (qq) partitions {Bi,..., Bk} of [n] such that if the numbers 1,2,... ,n are arranged in order around a circle, then the convex hulls of the blocks B±,..., Bk are pairwise disjoint (rr) noncrossing Murasaki diagrams with n vertical lines (ss) noncrossing partitions of some set [k] with n+1 blocks, such that any two elements of the same block differ by at least three 1-2-3-4 14-2-3-5 15-2-3-4 25-1-3-4 16-25-3-4 (tt) noncrossing partitions of [2n + 1] into n + 1 blocks, such that no block contains two consecutive integers 137-46-2-5 1357-2-4-6 157-24-3-6 17-246-3-5 17-26-35-4 227 (uu) nonnesting partitions of [n], i.e., partitions 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 G B satisfying b < c < d 123 12-3 13-2 23-1 1-2-3 (The unique partition of [4] that isn't nonnesting is 14—23.) (vv) Young diagrams that fit in the shape (n — 1, n — 2,..., 1) • □ C (ww) standard Young tableaux of shape (n,n) (or equivalently, of shape (71,71 — 1)) 123 124 125 134 135 456 356 346 256 246 or 123 124 125 134 135 45 35 34 25 24 (xx) pairs (P, Q) of standard Young tableaux of the same shape, each with n squares and at most two rows (123,123) ^ g2 g2 ^ 12 13 3 , 2 13 12 2 , 3 (yy) column-strict plane partitions of shape (n— 1, n — 2, in the ith row is equal ton — i or n — i + 1 33 2 33 1 32 2 32 1 13 13 2 , 2 1), such that each entry 22 1 (zz) convex subsets S of the poset Z x Z, up to translation by a diagonal vector (m, m), such that if (i,j) G S then 0 < i — j < n. 0 {(1,0)} {(2,0)} {(1,0), (2,0)} {(2,0), (2,1)} (aaa) linear extensions of the poset 2 x n 123456 123546 132456 132546 135246 228 33 Figure 5: A poset with C4 = 14 order ideals (bbb) order ideals of Int(n — 1), the poset of intervals of the chain n — 1 0, a, b, ab, abc (ccc) order ideals of the poset An obtained from the poset (n — 1) x (n — 1) by adding the relations < if i > j (see Figure 5 for the Hasse diagram of A4) 0 {11} {11,21} {11,21,12} {11,21,12,22} (ddd) nonisomorphic n-element posets with no induced subposet isomorphic to 2 + 2 or 3 + 1 (eee) nonisomorphic (n+ l)-element posets that are a union of two chains and that are not a (nontrivial) ordinal sum, rooted at a minimal element il ® (fff) relations R on [n] that are reflexive (iRi), symmetric (iRj =>• jRi), and such that ifl 2 such that in the sequence laia2 ■ ■ ■ anl, each a, divides the sum of its two neighbors 14321 13521 13231 12531 12341 (jjj) n-element multisets on Z/(n+ 1)Z whose elements sum to 0 000 013 022 112 233 (kkk) n-element subsets 5 of N x N such that if G S then i > j and there is a lattice path from (0, 0) to with steps (0,1), (1,0), and (1,1) that lies entirely inside S {(0,0), (1,0), (2,0)} {(0,0), (1,0), (1,1)} {(0,0), (1,0), (2,1)} {(0,0), (1,1), (2,1)} {(0,0), (1,1), (2, 2)} (111) regions into which the cone xi > x2 > • • • > xn in W1 is divided by the hyperplanes Xi — Xj = 1, for 1 < i < j < n (thd diagram below shows the situation for n = 3, intersected with the hyperplane xi + x2 + x3 = 0) 230 11111111111111 1321512313215 251441522514 32333233323 1 5 2 2 5 1 4 4 1 5 2 3 1 3 2 1 5 1 2 11111111 Figure 6: The frieze pattern corresponding to the sequence (1,3, 2,1,5,1,2, 3) (mmm) positive integer sequences ai, a2, ■ ■ ■, an+2 for which there exists an integer array (necessarily with n + 1 rows) 1 1 1 Q,\ 0,2 C^3 bi b2 b3 b„+2 h a2 'Jn-2 n r2 r3 1 1 1 rn+2 n 1 (54) such that any four neighboring entries in the configuration s t satisfy st = ru + 1 u (an example of such an array for (ai,..., a8) = (1,3, 2,1, 5,1, 2, 3) (necessarily unique) is given by Figure 6): 12213 22131 21312 13122 31221 (nnn) n-tuples (ai,... an) of positive integers such that the tridiagonal matrix 1 0 0 • • 0 0 1 a2 1 0 • • 0 0 0 1 a3 1 • • 0 0 0 0 0 0 • 1 0 0 0 0 • 1 is positive definite with determinant one 131 122 221 213 312 20. (a) [2+] Let m,n be integers satisfying 1 < n < m. Show by a simple bijection that the number of lattice paths from (1,0) to (m,n) with steps (0,1) and (1,0) that intersect the line y = x in at least one point is equal to the number of lattice paths from (0,1) to (m,n) with steps (0,1) and (1,0). 231 (b) [2-] Deduce that the number of lattice paths from (0, 0) to (m, n) with steps (1,0) and (0,1) that intersect the line y = x only at (0, 0) is given by ^ (c) [1+] Show from (b) that the number of lattice paths from (0,0) to (n,n) with steps (1, 0) and (0,1) that never rise above the line y = x is given by the Catalan number Cn = ^-j- (2™). (This gives a direct combinatorial proof of interpretation (h) of Cn in Exercise 19.) 21. (a) [2+] Let Xn be the set of all (2™) lattice paths from (0, 0) to (n, n) with steps (0,1) and (1,0). Define the excedance (also spelled "exceedance") of a path P 6 Xn to be the number of i such that at least one point (i, i') of P lies above the line y = x (i.e., i' > i). Show that the number of paths in Xn with excedance j is independent of j. (b) [1] Deduce that the number of P G Xn that never rise above the line y = x is given by the Catalan number Cn = ^-j- (2™) (a direct proof of interpretation (h) of Cn in Exercise 19). Compare with Example 5.3.11, which also gives a direct combinatorial interpretation of Cn when written in the form ^-j- (2^) (as well as in the form ^ft1))- 22. [2+] Show (bijectively if possible) that the number of lattice paths from (0,0) to (27i, 2ti) with steps (1, 0) and (0,1) that avoid the points (2i — 1, 2i — 1), 1 < i < n, is equal to the Catalan number C2n. 23. [3-] Consider the following chess position. Black is to make 19 consecutive moves, after which White checkmates Black in one move. Black may not move into check, and may not check White (except possibly on his last move). Black and White are cooperating to achieve the aim of checkmate. (In chess problem parlance, this problem is called a serieshelpmate in 19.) How many different solutions are there? 232 24. [?] Explain the significance of the following sequence: un, dos, tres, quatre, cine, sis, set, vuit, nou, deu, ... 25. [2]-[5] Show that the Catalan number Cn = ^x(2™) has the algebraic interpretations given below. (a) number of two-sided ideals of the algebra of all (n — 1) x (n — 1) upper triangular matrices over a field (b) dimension of the space of invariants of SL(2, C) acting on the 2nth tensor power T2n(V) of its "defining" two-dimensional representation V (c) dimension of the irreducible representation of the symplectic group Sp(2(n — 1), C) (or Lie algebrasp(2(n— 1), C)) with highest weight An_i, the (n—l)st fundamental weight (d) dimension of the primitive intersection homology (say with real coefficients) of the toric variety associated with a (rationally embedded) n-dimensional cube (e) the generic number of PGL(2,C) equivalence classes of degree n rational maps with a fixed branch set (f) number of translation conjugacy classes of degree n+ 1 monic polynomials in one complex variable, all of whose critical points are fixed (g) dimension of the algebra (over a field K) with generators e±,..., en_i and relations 2, where (5 is a nonzero element of K (h) number of ©-sign types indexed by (the set of positive roots of the root system An_i) (i) Let the symmetric group &n act on the polynomial ring A = C[x±,..., xn, yi,..., yn] bywf(x1,...,xn,y1,...,yn) = f(xw{1)xw{n), yw{1)yw{n)) for all w G &n. Let / be the ideal generated by all invariants of positive degree, i.e., / = (/ G A : w ■ f = f for all w G 6n, and /(0) = 0). Then (conjecturally) Cn is the dimension of the subspace of A/1 affording the sign representation, i.e., Cn = dim{/ G A/1 :wf= (sgn w)f for all / G Gn}. 26. (a) [3-] Let D be a Young diagram of a partition A, as defined in Section 1.3. Given a square s of D let t be the lowest square in the same column as s, and let u be the rightmost square in the same row as s. Let f(s) be the number of paths from 233 t to u that stay within D, and such that each step is one square to the north or one square to the east. Insert the number f(s) in square s, obtaining an array A. For instance, if A = (5,4, 3, 3) then A is given by 16 7 2 1 1 6 3 1 1 3 2 1 1 1 1 Let M be the largest square subarray (using consecutive rows and columns) of A containing the upper left-hand corner. Regard M as a matrix. For the above example we have " 16 7 2 M= 6 3 1 3 2 1 Show that detM = 1. (b) [2] Find the unique sequence a0,ai, have of real numbers such that for all n > 0 we det di a2 an+l «2n = det a± a2 a2 a3 %+i an+l «2n-l = 1. (When n = 0 the second matrix is empty and by convention has determinant one.) 27. (a) [3-] Let Vn be a real vector space with basis x0, Xi,..., xn and scalar product defined by (xi,Xj) = Cj+j, the (i + j)-th Catalan number. It follows from Exercise 26(b) that this scalar product is positive definite, and therefore V has an orthonormal basis. Is there an orthonormal basis for Vn whose elements are integral linear combinations of the Xj's ? (b) [3-] Same as (a), except now (xt,Xj) = Ci+j+\. (c) [5-] Investigate the same question for the matrices M of Exercise 26(a) (so (xi,Xj) = Mij) when A is self-conjugate (so M is symmetric). 28. (a) [3-] Suppose that real numbers xi, x2, ■ ■ ■, x& are chosen uniformly and inde- pendently from the interval [0,1]. Show that the probability that the sequence Xi,x2, ■ ■ ■, Xd is convex (i.e., Xj < + for 2 < i < d—1) is C^-i/(d— l)!2, where C^-i denotes a Catalan number. 234 (b) [3-] Let Cd denote the set of all points (xi, x2, ■ ■ ■, xd) G Rd such that 0 < Xj < 1 and the sequence Xi,x2,...,Xd is convex. It is easy to see that Cd is a d-dimensional convex polytope, called the convexotope. Show that the vertices of Cd consist of the points (l,^,^,...,),0,0,...,0,|,§,...,l) (55) (with at least one 0 coordinate), together with (1,1,..., 1) (so (d2l) + 1 vertices in all). For instance, the vertices of C3 are (0,0,0), (0,0,1), (0,|,1), (1,0,0), (l,i,0), (1,0,1), (1,1,1). (c) [3] Show that the Ehrhart quasi-polynomial i(Cd,n) of Cd (as defined in Section 4.6) is given by Vd ■= y^i(Cd,n)xn 7J>0 A 1 1 ^ 1 1 \ i-*y^m-iy.^m-ry. ^[i][r-i]!*[ip-i-r]!;M ] where [i] = 1 — xl, = [1][2] • • • [i], and * denotes Hadamard product. For instance, 1 2/i = 2/2 = 2/3 = 2/4 = 2/5 : 1 - x)2 1 + x (1 - x)3 1 + 2x + 3x2 (1 -x)3(l -x2) 1 + 3x + 9x2 + 12x3 + llx4 + 3x5 + x6 (1 -x)2(l -x2)2(l -x3) 1 + 4x + 14x2 + 34x3 + 63x4 + 80x5 + 87x6 + 68x7 + 42x8 + 20x9 + 7x10 (1-x)(l-x2)2(l-x3)2(l-x4) Is there a simpler formula than (56) for i(Cd,n) or y^? 29. [3] Suppose that n + 1 points are chosen uniformly and independently from inside a square. Show that the probability that the points are in convex position (i.e., each point is a vertex of the convex hull of all the points) is (Cn/n\)2. 30. [3-] Let /„ be the number of partial orderings of the set [n] that contain no induced subposets isomorphic to 3 + 1 or 2 + 2. (This exercise is the labelled analogue of Exercise 19(ddd). As mentioned in the solution to this exercise, such posets are called semiorders.) Let C(x) = 1 + x + 2x2 + 5x3 H----be the generating function for Catalan numbers. Show that Y,^ = C{l-e-% (57) n>0 n- the composition of C(x) with the series 1 — e~x = x — \x2 + |x3 — • • •. 235 Figure 7: The Tamari lattice T3 31. (a) [3-] Let V denote the convex hull in Rd+1 of the origin together with all vectors e, — ej, where e, is the ith unit coordinate vector and i < j. Thus V is a d-dimensional convex polytope. Show that the relative volume of V (as defined in Section 4.6) is equal to Cd/d\, where Cd denotes a Catalan number. (b) [3] Let i(V,n) denote the Ehrhart polynomial of V. Find a combinatorial interpretation of the coefficients of the i-Eulerian polynomial (in the terminology of Section 4.3) (1 -x)d+l^i{V,n)xn. n>0 32. (a) [3-] Define a partial order Tn on the set of all binary bracketings (parenthesiza- tions) of a string of length n + 1 as follows. We say that v covers u if u contains a subexpression (xy)z (where x, y, z are bracketed strings) and v is obtained from u by replacing (xy)z with x(yz). For instance, ((a2 • a)a2)(a2 • a2) is covered by ((a-a2)a2)(a2 -a2), (a2(a-a2))(a2 ■ a2), ((a2 • a)a2)(a(a-a2)), and (a2 • a)(a2(a2 • a2)). Figures 7 and 8 show the Hasse diagrams of T3 and T4. (In Figure 8, we have encoded the binary bracketing by a string of four +'s and four —'s, where a + stands for a left parenthesis and a — for the letter a, with the last a omitted.) Let Un be the poset of all integer vectors (a\, a,2, ■ ■ ■, an) such that i < a, < n and such that if i < j < a, then a,j < a,, ordered coordinatewise. Show that Tn and Un are isomorphic posets. (b) [2] Deduce from (a) that Tn is a lattice (called the Tamari lattice). 33. Let C be a convex n-gon. Let S be the set of all sets of diagonals of C that do not intersect in the interior of C. Partially order the element of S by inclusion, and add a 1. Call the resulting poset An. (a) [3-] Show that An is a simplicial Eulerian lattice of rank n — 2, as defined in Section 3.14. (b) [3] Show in fact that An is the lattice of faces of an (n — 3)-dimensional convex polytope Qn. (c) [3-] Find the number Wi = Wi(n) of elements of An of rank i. Equivalently, W, is the number of ways to draw i diagonals of C that do not intersect in their interiors. Note that by Proposition 2.1, Wi(n) is also the number of plane trees with n + i vertices and n — 1 endpoints such that no vertex has exactly one successor. 236 +-+-++-- +-++--+- ++—+-+- +-+++- +++-+— +++--+-- +++—+- ++++— Figure 8: The Tamari lattice T4 (d) [3-] Define n—3 n—3 J2wi(x~ l)n_i-3 = J2 hiXn~3~\ (58) i=0 i=0 as in equation (3.44). The vector (h0,... ,hn_3) is called the h-vector of An (or of the polytope Qn). Find an explicit formula for each h^. There are many possible g-analogues of Catalan numbers. In (a) we give what is perhaps the most natural "combinatorial" g-analogue, while in (b) we give the most natural "explicit formula" g-analogue. In (c) we give an interesting extension of (b), while (d) and (e) are concerned with another special case of (c). (a) [2+] Let p where the sum is over all lattice paths P from (0,0) to (n,n) with steps (1,0) and (0,1), such that P never rises above the line y = x, and where A(P) is the area under the path (and above the x-axis). Note that by Exercise 19(h), we have C„(l) = Cn. (It is interesting to see what statistic corresponds to A(P) for many of the other combinatorial interpretations of Cn given in Exercise 19.) For instance, CQ(q) = Ci(q) = 1, C2(q) = 1 + q, C3(q) = 1 + q + 2q2 + q3, C4(q) = l + q + 2q2 + 3q3 + 3q4 + 3q5 + qe. Show that n cfH-i(?) = Ec'«(«)c'»-«(«)«(*+1)(B"0- i=0 Deduce that if Cn(q) = q(^Cn(l/q), then the generating function F(x) = J2Cn(q)xn n>0 satisfies xF(x)F(qx) - F(x) + 1 = 0. From this we get the continued fraction expansion F(x) =-1-. (59) x 1-- qx 1---^2— q x 1---- 1---- (b) [2+] Define *(*)=(^Ti)Cr)- 238 For instance, c0(q) = Ci(q) = 1, c2(q) = 1 + q2, c3(q) = 1 + q2 + q3 + q4 + qe, c4(q) = 1 + q2 + q3 + 2q4 + q5 + 2qe + q7 + 2q8 + q9 + q10 + q12. Show that Cn(maJH, w where w ranges over all sequences a\a2 ■ ■ ■ a2n of n l's and n — l's such that each partial sum is nonnegative, and where maj(w) = X] h {i: Oi>Oj+i} the major index of w. (c) [3-] Let t be a parameter, and define +it Show that cn(t;q) = J2qm&i{w)+{t-l)des{w), w where w ranges over the same set as in (b), and where des(w) = #{i : at > ai+i}, the number of descents of w. (Hence cn(l; q) = cn(q).) (d) [3-] Show that cn(0;q) = :^^cn(tf)- For instance, c0(0;q) = ci(0;g) = 1, c2(0; q) = 1 + q, c3(0;q) = 1 + q + q2 + q3 + qA, c4(0;q) = l + q + q2 + 2q3 + 2q4 + 2qb + 2q6 + q7 + q8 + q9. (e) [3+] Show that the coefficients of cn(0;q) are unimodal, i.e., if cn(0;q) = ^fyq1, then for some j we have b0 < bi < ■ ■ ■ < bj > bj+i > bj+2 > • • •. (In fact, we can take j= L|degcn(0;g)J = L|— 1)2J -) 35. Let Qn be the poset of direct-sum decompositions of an n-dimensional vector space Vn over the field F9, as defined in Example 5.5.2(b). Let Qn denote Qn with a 0 adjoined, and let /jLn(q) = A*Qn(0, !)■ Hence by (5.74) we have ~ ^ (?) = log „>i q&)(n)l n>o?^(n)! (a) [3-] Show that »n{q) = -(-1)B(9 - 1)(l n>l where Cn(q) is the g-Catalan polynomial defined in Exercise 34(a). 36. (a) [2+] The Narayana numbers N(n, k) are defined by Let Xnk be the set of all sequences w = Wiw2 • • • w2n of n l's and n — l's with all partial sums nonnegative, such that k = #{j : Wj = l,wj+i = -1}. Give a combinatorial proof that N(n, k) = #Xnk. Hence by Exercise 19(r), there follows n J2N(n,k) = Cn. k=l (It is interesting to find for each of the combinatorial interpretations of Cn given by Exercise 19 a corresponding decomposition into subsets counted by Narayana numbers.) (b) [2+] Let F(x,t) = En>i E^i^K^)^- Using the combinatorial interpretation of N(n, k) given in (a), show that xF2 + (xt + x- 1)F + xt = 0, (60) so „. . 1 — x — xt — — x — xt)2 — AxH F(x,t) =----. V ' ; 2x 37. [2+] The Motzkin numbers Mn are defined by 5>»* = -2^- 7J>0 = 1 + x + 2x2 + Ax3 + 9x4 + 21x5 + 51x6 + 127x7 + 323x8 +835x9 + 2188x10 + • • •. Show that Mn = AnCi and Cn = A2nM0, where Cn denotes a Catalan number. 240 38. [3-] Show that the Motzkin number Mn has the following combinatorial interpretations. (See Exercise 46(b) for an additional interpretation.) (a) Number of ways of drawing any number of nonintersecting chords among n points on a circle. (b) Number of walks on N with n steps, with steps —1, 0, or 1, starting and ending at 0. (c) Number of lattice paths from (0,0) to (n,n), with steps (0,2), (2,0), and (1,1), never rising above the line y = x. (d) Number of paths from (0,0) to (n, n) with steps (1,0), (1,1), and (1,-1), never going below the x-axis. Such paths are called Motzkin paths. (e) Number of pairs 1 < a± < ■ ■ ■ < ak < n and 1 < b\ < ■ ■ ■ < bk < n of integer sequences such that a, < bi and every integer in the set [n] appears at least once among the a,'s and 6j's. (f) Number of ballot sequences (as defined in Corollary 2.3(ii)) (ai,..., a2n+2) such that we never have (aj_i, a,, aj+i) = (1, —1,1). (g) Number of plane trees with n/2 edges, allowing "half edges" that have no successors and count as half an edge. (h) Number of plane trees with n + 1 edges in which no vertex, the root excepted, has exactly one successor. (i) Number of plane trees with n edges in which every vertex has at most two successors. (j) Number of binary trees with n — 1 edges such that no two consecutive edges slant to the right. (k) Number of plane trees with n + 1 vertices such that every vertex of odd height (with the root having height 0) has at most one successor. (1) Number of noncrossing partitions 7r = {Bi,..., Bk} of [n] (as defined in Exercise 3.68) such that if Bi = {b} and a < b < c, then a and c appear in different blocks of 7T. (m) Number of noncrossing partitions 7r of [n + 1] such that no block of 7r contains two consecutive integers. 39. [3-] The Schroder numbers rn and sn were defined in Section 2. Show that they have the following combinatorial interpretations. (a) sn-i is the total number of bracketings (parenthesizations) of a string of n letters. (b) sn_i is the number of plane trees with no vertex of degree one and with n end-points. (c) rn_i is the number of plane trees with n vertices and with a subset of the endpoints circled. 241 (d) sn is the number of binary trees with n vertices and with each right edge colored either red or blue. (e) sn is the number of lattice paths in the (x, y) plane from (0, 0) to the x-axis using steps (l,k), where A; G P or A; = — 1, never passing below the x-axis, and with n steps of the form (1,-1). (f) sn is the number of lattice paths in the (x,y) plane from (0,0) to (n,n) using steps (k, 0) or (0,1) with k G P, and never passing above the line y = x. (g) rn_i is the number of parallelogram polynominoes (defined in the solution to Exercise 19(1)) of perimeter 2n with each column colored either black or white. (h) sn is the number of ways to draw any number of diagonals of a convex (n + 2)-gon that do not intersect in their interiors (i) sn is the number of sequences i\i2 • • - ik, where ij G P or ij = — 1 (and k can be arbitrary), such that n = : ij = — 1}, i\ + i2 + • • • + ij > 0 for all j, and H + i2 H-----h ifc = 0. (j) rn is the number of lattice paths from (0, 0) to (n, n), with steps (1,0), (0,1), and (1,1), that never rise above the line y = x. (k) rn_i is the number of n x n permutation matrices P with the following property: We can eventually reach the all l's matrix by starting with P and continually replacing a 0 by a 1 if that 0 has at least two adjacent l's, where an entry a,j is defined to be adjacent to ai±ij and ay-ti. (1) Let u = Ui ■ ■ -Uk G &k- We say that a permutation w = W\ • • • wn G &n is u-avoiding if no subsequence wai,..., waie (with a± < ■ ■ ■ < a&) is in the same relative order as u, i.e., Ui < Uj if and only if wai < wa.. Let &n(u,v) denote the set of permutations w G &n avoiding both the permutations u,v G 64. There is a group G of order 16 that acts on the set of pairs (u, v) of unequal elements of 64 such that if (u, v) and («', v') are in the same G-orbit (in which case we say that they are equivalent), then there is a simple bijection between &n(u,v) and &n(u',v') (for all n). Namely, identifying a permutation with the corresponding permutation matrix, the orbit of (u, v) is obtained by possibly interchanging u and v, and then doing a simultaneous dihedral symmetry of the square matrices u and v. There are then ten inequivalent pairs (u, v) G 64 x 64 for which #&n(u, v) = r„_i, namely, (1234,1243), (1243,1324), (1243,1342), (1243,2143), (1324,1342), (1342,1423), (1342,1432), (1342,2341), (1342,3142), and (2413,3142). (m) rn_i is the number of permutations w = Wiw2 ■ ■ ■ wn of [n] with the following property: It is possible to insert the numbers wi,..., wn in order into a string, and to remove the numbers from the string in the order 1,2,... ,n. Each insertion must be at the beginning or end of the string. At any time we may remove the first (leftmost) element of the string. (Example: w = 2413. Insert 2, insert 4 at the right, insert 1 at the left, remove 1, remove 2, insert 3 at the left, remove 3, remove 4.) (n) rn is the number of sequences of length 2n from the alphabet A, B, C such that: (i) for every 1 < i < 2n, the number of A's and S's among the first i terms is not 242 Figure 9: A board with r3 = 22 domino tilings less than the number of C's, (ii) the total number of A's and B's is n (and hence the also the total number of C's), and (iii) no two consecutive terms are of the form CB. (o) rn-i is the number of noncrossing partitions (as defined in Exercise 3.68) of some set [k] into n blocks, such that no block contains two consecutive integers. (p) sn is the number of graphs G (without loops and multiple edges) on the vertex set [n + 2] with the following two properties: (a) All of the edges {1, n + 2} and + 1} are edges of G, and {(5) G is noncrossing, i.e., there are not both edges {a, c} and {b, d} with a < b < c < d. Note that an arbitrary noncrossing graph on [n + 2] can be obtained from those satisfying (a)-((3) by deleting any subset of the required edges in (a). Hence the total number of noncrossing graphs on [n + 2] is 2n+2sn. (q) rn-i is the number of reflexive and symmetric relations R on the set [n] such that if iRj with i < j, then we never have uRv for i < u < j < v. (r) rn_i is the number of reflexive and symmetric relations R on the set [n] such that if iRj with i < j, then we never have uRv for i < u < j < v. (s) rn_i is the number of ways to cover with disjoint dominos (or dimers) the set of squares consisting of 2i squares in the ith row for 1 < i < n — 1, and with 2(n — 1) squares in the nth row, such that the row centers lie on a vertical line. See Figure 9 for the case n = 4. [3-] Let an be the number of permutations w = W1W2 ■ ■ ■ wn G &n such that we never have Wi+i = Wi ± 1, e.g., = 2, corresponding to 2413 and 3142. Equivalently, an is the number of ways to place n nonattacking kings on an n x n chessboard with one king in every row and column. Let A(x) = y^anx" 7J>0 = 1 + x + 2xA + Ux5 + 90x6 + 646x7 + 5242x8 + • • •. Show that A(xR(x)) = ^2n>0n\xn := E(x), where R(x) = rnxn = — ^1 — x — Vl — 6x + x2^j , 7J>0 243 the generating function for Schröder numbers. Deduce that . / s ^ (x(l — x) A(x) = E -\-J- 41. [3] A permutation w G &n is called 2-stack sortable if S2(w) = w, where S is the operator of Exercise 19 (ii). Show that the number 52 (n) of 2-stack sortable permutations in &n is given by , _ 2(3w)! b2[n)~ (n+l)!(2n+l)!' 42. [2] A king moves on the vertices of the infinite chessboard Z x Z by stepping from to any of the eight surrounding vertices. Let f(n) be the number of ways in which a king can walk from (0,0) to (n, 0) in n steps. Find F(x) = Yln>o f(n)xni and find a linear recurrence with polynomial coefficients satisfied by f(n). 43. (a) [2+] A secondary structure is a graph (without loops or multiple edges) on the vertex set [n] such that (a) {i, i + 1} is an edge for all 1 < i < n — 1, (b) for all i, there is at most one j such that {i, j} is an edge and \j — i\ ^ 1, and (c) if {i, j} and {k,l} are edges with i < k < j, then i < I < j. (Equivalently, a secondary structure may be regarded as a 3412-avoiding involution (as in Exercise 19(kk)) such that no orbit consists of two consecutive integers.) Let s(n) be the number of secondary structures with n vertices. For instance, s(5) = 8, given by •—•—•—•—• » ^»—•—• •—» ^»—• •—•—» ^» • • N>-• •-S m m N> S m m m ^» m S m N> Let S(x) = X)„>o s{n)xn = 1 + x + x2 + 2x3 + 4x4 + 8x5 + 17x6 + 37x7 + 82x8 + 185x9 + 423x10 + • • •. Show that . x2 — x + 1 — \/l — 2x — x2 — 2x3 + x4 S(x) =- 2x2 (b) [3-] Show that s(n) is the number of walks in n steps from (0, 0) to the x-axis, with steps (1,0), (0,1), and (0,-1), never passing below the x-axis, such that (0,1) is never followed directly by (0, —1). 44. Define a Catalan triangulation of the Möbius band to be an abstract simplicial complex triangulating the Möbius band that uses no interior vertices, and has vertices labelled 1, 2,..., n in order as one traverses the boundary. (If we replace the Möbius band by a disk, then we get the triangulations of Corollary 2.3(vi) or Exercise 19(a).) Figure 10 shows the smallest such triangulation, with five vertices (where we identify the vertical edges of the rectangle in opposite directions). Let MB(n) be the number of Catalan 244 1 2 3 4 Figure 10: A Catalan triangulation of the Möbius band triangulations of the Möbius band with n vertices. Show that ^ n x2 ((2 - 5a - Ax2) + (-2 + x + 2x2)VT^Äx) > MB n i = —--—.----—. ^ w (1 - Ax) (1 - Ax + 2x2 + (1 - 2x)y/l ~ Ax) = x5 + 14x6 + 113xr + 720x8 + 4033x9 + 20864x10 + 45. [3-] Let f(n) be the number of nonisomorphic n-element posets with no 3-element antichain. For instance, f(A) = 10, corresponding to <0> M N I- II Let F(x) = En>o f(n)xn = 1 + x + 2x2 + Ax3 + 10x4 + 26x5 + 75x6 + 225x7 + 71 lx8 + 2311x9 + 7725xro + • • •. Show that F(x) = 2-2x + \/l - Ax + y/1 - Ax2' 46. (a) [3+] Let f(n) denote the number of subsets S of N x N of cardinality n with the following property: If p G S then there is a lattice path from (0, 0) to p with steps (0,1) and (1,0), all of whose vertices lie in S. Show that = x + 2x2 + 5x3 + 13x4 + 35x5 + 96x6 + 267x7 +750x8 + 2123x9 + 6046x10 + • • •. (b) [3+] Show that the number of such subsets contained in the first octant 0 < x < y is the Motzkin number Mn_i (defined in Exercise 37). 47. (a) [3] Let Pn be the Bruhat order on the symmetric group &n as defined in Exercise 3.75(a). Show that the following two conditions on a permutation w G &n are equivalent: i. The interval [0,w] of Pn is rank-symmetric, i.e., if p is the rank function of Pn (so p(w) is the number of inversions of w), then #{« G [6,w] : p{u) = i} = #{u G [6,w] : p(w) - p(u) = i}, for all 0 < i < p(w). 245 ii. The permutation w = w\W2---wn is 4231 and 3412-avoiding, i.e., there do not exist a < b < c < d such that < Wf, < wc < wa or wc < < wa < w^. (b) [3-] Call a permutation w G &n smooth if it satisfies (i) (or (ii)) above. Let f(n) be the number of smooth w G &n. Show that 1 1 - r__— (_—__l) 1 X l-x \l+x-(l-x)C(x) 1) = 1 + x + 2x2 + 6x3 + 22xA + 88x5 + 366x6 +1552x7 + 6652x8 + 28696x9 + • • •, where C(x) = (1 — \/l — Ax)/2x is the generating function for the Catalan numbers. 48. [3] Let f(n) be the number of 1342-avoiding permutations w = W1W2 ■ ■ - wn in &n, i.e., there do not exist a < b < c < d such that wa < wa < u>& < wc. Show that 32x 1 + 20x - 8x2 - (1 - 8x)3/2 = 1 + x + 2x2 + 6x3 + 23x4 + 103x5 + 512x6 + 2740xr + 15485x8 + • • •. 49. (a) [3-] Let Bn denote the board consisting of the following number of squares in each row (read top to bottom), with the centers of the rows lying on a vertical line: 2, 4, 6, ..., 2(n — 1), 2n (three times), 2{n — 1), ..., 6, 4, 2. Figure 11 shows the board B3. Let f(n) be the number of ways to cover Bn with disjoint dominos (or dimers). (A domino consists of two squares with an edge in common.) Show that f(n) is equal to the central Delannoy number D(n,n) (as defined in Section 3). (b) [3-] What happens when there are only two rows of length 2n? 50. [3] Let B denote the "chessboard" NxN. A position consists of a finite subset S of B, whose elements we regard as pebbles. A move consists of replacing some pebble, say at cell (i,j), with two pebbles at cells (i + and (i,j + 1), provided that each of these cells is not already occupied. A position S is reachable if there is some sequence of moves, beginning with a single pebble at the cell (0, 0), that terminates in the position S. A subset T of B is unavoidable if every reachable set intersects T. A subset T of B is minimally unavoidable if T is unavoidable, but no proper subset of T is unavoidable. Let u(n) be the number of n-element minimally unavoidable subsets of B. Show that 3 (1 - 3x + x2)\/l - Ax - 1 + 5x - x2 - 6x3 X 1 - 7x + Ux2 - 9x3 4x5 + 22x6 + 98xr + 412x8 + 1700x9 + 6974x10 + 28576X11 + • • •. n>0 2^f{n)x n>0 ^2u(n)xn = n>0 246 Figure 11: A board with D(3, 3) = 63 domino tiling 247