18.212 Algebraic Combinatorics, Lecture 34: Pascal Triangle and More

18.212: Algebraic Combinatorics May 3 The problem set is posted! It will be due in a week (on May 10). Today, we’ll go over some concepts that will be helpful for the problem set. (Again, solving six problems completely is generally good enough.) Last time, we considered the tree inversion polynomial X In (x) = x inv(T) = T spanning trees of Kn+1 X x( n+1 2 )− P i f (i) . f :[n]→[n] parking function Three problems from the problem set are related to alternating permutations w ∈ Sn , which satisfy the condition w1 < w2 > w3 · · · . Letting An be the number of alternating permutations of Sn (also known as Euler, Andre, zigzag, tangent and secant numbers, up-down numbers, and so on), these are closely related to the Bernoulli numbers Bn ! Fact 1 Plugging in x = −1 yields the Euler numbers An . Fact 2 Taking the exponential generating function X An n≥0 xn n! (we do this so that our series is not divergent!), we get tan(x) + sec(x). In fact, if we only add odd or even n, X X xn xn An = tan x, An = sec x. n! n! n≥1 odd n≥0 even Fact 3 We can draw something similar to the Pascal triangle: 1 1 0 1 1 0 1 1 5 0 2 5 4 2 2 0 Basically, alternate from left to right, adding up the entries from the row above! Then the nonzero numbers on the sides of the triangle are just An . We can call the right side the “Bernoulli side” and the left side the “Euler side:” the right side is then the numbers that appear in the series expansion of tan x, and the left side is those for sec x. Definition 4 The Bernoulli numbers Bn are given by X Bn n≥0 xn x = x . n! e −1 If we expand out, we have     x 1 1 x2 1 x4 1 x6 = 1 + − x + · + − + · + ··· x e −1 2 6 2! 30 4! 42 6! Note that all Bn are only nonzero if n is even or n = 1. The exact formula is actually given by (through the tan x expansion) 2n A2n−1 . 42n − 22n So really the An s are the heart of the combinatorial tricks here! B2n = (−1)n−1 Fact 5 By the way, these are related to the Riemann zeta function, which can written in integral form as ˆ ∞ x−1 1 u ζ(x) = du. Γ(x) 0 e u − 1 We can find that at integer values, there’s a useful relationship: B2n = (−1)n−1 · 2(2n)! ζ(2n), (2π)2n which allows us to find ζ(2), ζ(4), and so on. One thing that makes it easier for us to deal with Bernoulli numbers is the useful recurrence relation for An : Proposition 6 We have for all n ≥ 1 that 2An+1 = n   X n Ak An−k . k k=0 (Also, we have the initial conditions A0 = A1 = 1.) This looks a little like the Catalan number relation (if we remove the 2 and version of the Catalan numbers! 2 �n
k ). So these are somehow the “labeled” Proof. The left hand side is the number of ways to have alternating permutations on n + 1 elements that are either up-down or down-up: w1 < w2 > w3 · · · or w1 > w2 < w3 · · · . Take any permutation in this set, and find the position of (n + 1): let’s say it’s in spot k + 1. In front, we have k entries, and after, we have n − k entries: both must be alternating, and the orientation (up-down or down-up) is fixed, �
because (n + 1) is the largest element. Thus we have kn ways to pick which k elements are before n + 1, Ak · An−k ways to arrange the remaining elements, and then summing over all k gives the result! It turns out that we can turn this recurrence relation to a di˙erential equation for our generating function A(x): 2A0 (x) + A2 (x) + 1. This is good to look over as an exercise! Note that A0 (x) for an exponential generating function shifts the indices by one, and also notice how similar this looks to the Catalan functional equation. It turns out these ideas are also related to binary trees! There are two versions: a regular binary tree is one where every vertex has at most 2 children: a left child and a right child. There’s also a notion of a full binary tree: this is the subset of normal binary trees where every vertex either has no children (is a leaf) or has both children. Fact 7 Each full binary tree has an odd number of vertices, because we always add 2 vertices as a time. It turns out both kinds of binary trees are related to Catalan numbers! Claim 7.1. The Catalan number Cn is the number of (regular) binary trees on n vertices, and it’s also the number of full binary trees on 2n + 1 vertices. Proof. It’s pretty easy to find a bijection between the sets of trees here: given a binary tree on n vertices, add all missing children (so add both children to each leaf as well). This will create a full binary tree with n non-leafs and n + 1 leaves: that means we indeed have a 2n + 1 vertex full binary tree! To go backwards, just remove all leaves from our tree. To show that these are equal to Cn , let’s find a bijection between Dyck paths of length 2n and full binary trees with 2n + 1 vertices. Given any Dyck path, we can break it up into consecutive up-steps: let a1 , a2 , · · · be the lengths of those groups. (If we have consecutive down-steps, then we still have ai = 0 in the middle: basically, ai counts the number of up steps on the i th diagonal.) Now we can construct our tree: attach a1 vertices along a left chain (with all children), attach a2 vertices starting from the bottom-most right child of the a1 -chain, and now repeat. If we have ai = 0, then move one up the diagonal and keep going! This is one way to search through a binary tree. Next lecture, we’ll discuss what happens when we label the vertices of our binary trees by numbers (with increasing labels downward). Then the number of increasing-labeled binary trees on n nodes is equal to n!, and the number of increasing-labeled full binary trees on 2n + 1 nodes is equal to An . So alternating numbers are the “labeled version” of Catalan numbers! 3