18.212 Algebraic Combinatorics, Problem Set 3 Solutions

Problem Set 3 Solutions We’re going over the problem set 3 solutions today. Problem 1 Find a bijective proof for the number of spanning trees in a complete bipartite graph (mn−1 nm−1 ). Solution by Sanzeed. We will construct a sequence of vertices of length m + n − 2. Notice that if one side has more vertices than the other, then there will be at least one vertex with degree 1 on that side. Pick the vertex with degree 1 with smallest index on that side, and just like in the Prufer code, add its neighbor to our sequence. Now repeat this: check which side has more vertices, remove the vertex of smallest index with degree 1, and add its neighbor to our code. Just like in the Prufer code, we can recover our original tree with this sequence. Since we start with m and n vertices, respectively, we’ll get n − 1 and m − 1 vertices from each part of our bipartition, respectively, in our sequence. This can be written in any of mn−1 nm−1 ways, as desired! Problem 2 Prove the equivalence of the parking functions conditions: (1) f is a parking function if and only if (2) the number of f (i )s that are ≥ n − k + 1 is at least k for all i , which happens if and only if (3) there is a permutation w (i ) such that f (i ) ≤ w (i ) for all i . SOlution by Fadi. Show (1) implies (2) with the contrapositive. If there are more than k cars that want to park in the last k spots, f can’t be a parking function because there aren’t enough spots! For (2) implies (1), again use the contrapositive. assume f is not a parking function: then there has to exist some car i that doesn’t park. Spots f (i ), f (i ) + 1, · · · must all be full, all cars that park in the spots after i must have had their initial values of f at least equal to f (i ) + 1, which violates condition 2. For (1) implies (3), make the permutation where i goes to its eventual parking spot: each eventual spot is at least the value of f (i ). Finally, (3) implies (1) comes from decreasing entries one by one: (2) is never violated, so we must always have a parking function. 1 Problem 3 Show Abel’s identity (that will be seen in the proof). Solution by Congyue. Consider the graph of n + 2 vertices A, B, and n others, where we have edges A → B with weight 1, A → [n] with weight x, and B → [n] with weight y . Finally, all edges in [n] have directed weight z in both directions. The number of out-trees spanning trees here rooted at A can be found by taking A → B, and now we put some k vertices in the same connected component as A and n − k vertices in that of B. The number of forests of i + 1 components �
k−1−i in Kk is k−1 k , and then we need to pick i + 1 edges: this gives a weight of x i+1 . We also need to pick some edges i below to connect the rest of the k vertices, which gives a weight of z k−1−i . So this contribution is  k−1  X k − 1 k−1−i i+1 k−i−1 x z = x(x + kz )k−1 . k i i=0 Similarly, the other n − k vertices give a contribution of y (y + (n − k)z)n−k−1 , so for all trees, we have a weighted sum of n   X n x(x + kz )k−1 y (y + (n − k)z)n−k−1 . k k=0 But on the other hand, we can use the directed matrix tree theorem to compute the weight: the Laplacian has form 0 1 0 −1 −x · · · − x Lin = @0 1 −y · · · − y A 0 0 A where A is an n by n matrix with diagonal entries x + y + (n − 1)z and all other entries −z, which has a determinant that evaluates to (x + y )(x + y + nz )n−1 by taking the product of eigenvalues. This yields the desired result n   X n n−1 = x(x + kz )k−1 y (y + (n − k)z)n−k−1 . (x + y )(x + y + nz ) k k=0 For the first identity, we can replace y + nz = sand finish by induction on n. Alternative solution by Ganatra. The second one follows from the first: we’ll show an algebraic proof for the first one. �
P We’ll induct on n. n = 0 is trivia, and so is n = 1: (x + y ) = 1k=0 k1 y (y + kz )k−1 (x − kz )1−k can be directly verified. Assume for n ≥ 2 that we already know (x + y )n−1 =  n−1  X n−1 y (y + Kz)k−1 (x − kz )n−k−1 . k k=0 We just need to show that we have equality of derivatives to show that the coeÿcients are the same. The derivative with respect to x and y are essentially symmetric: the derivative d [(x + y )n ] = n(x + y )n−1 , dx and " n   # " n   # X n d X n k−1 n−k k−1 n−k−1 = y (y + kz ) (n − k)(x − kz ) . y (y + kz ) x(x − kz ) dx k k k=0 k=0 �
�
Since kn (n − k) = n n−1 , this now simplifies to k  n−1  X n−1 n y (y + kz )k−1 (x − kz )n−k−1 , k k=0 2 and by the induction hypothesis, this is just n(x + y )n−1 , which is just the derivative. Now check the constant terms: replacing x = −y , the left side becomes 0, and we can show that the right hand side also vanishes because we have alternating binomial coeÿcients. Problem 4 Compute the number of Eulerian cycles in a bidirected n-cube graph. Solution by Sophia. By the BEST theorem, this number is just the number of intrees rooted at some vertex r , multiplied by (outdeg(v ) − 1)! for all v . An n-cube has 2n vertices, and each term has outdegree n, so this product becomes n [(n − 1)!]2 . We also know the number of spanning trees on an n-cube: the number of spanning trees is equal to the number of in-trees, because we can direct all edges of a spanning tree towards the root. That gives us a factor of 22 n −n−1 n Y k (k ) n k=1 and multiplying these gives the answer. Problem 5 Prove that the generating function X An n! x n = tan x + sec x. Solution by Song Wenzhu. We proved during lecture that n   X n 2An = Ak−1 An−k k k=1 which simplifies to (n − 1)! n X An−k Ak−1 . (k − 1)! (n − k)! k=1 We know that our generating function (if we denote ck = Ak k! ) X G(x) = ck x k satisfies G(x)2 = c02 + 1 n X X (ck c1−k )x + · · · + (ck cn−k )x n k=0 k=0 and plugging in the recurrence relation, = c02 +2 ∞ X kck x k−1 = 2G 0 (x) + 1. k=2 This is a di˙erential equation: 1 1 G2 + 1 = =⇒ x + C = arctan G, 0 G 2 2 and use initial conditions to yield  G = tan 1 x +C 2  3 = tan x + sec x. Problem 6 Find bijections between the following sets: (1) the set of labelled trees on n + 1 vertices, (2) the set of plane binary trees on n vertices labelled by [n] such that the left child of a vertex always has a bigger label than its parent, (3) the set of Dyck paths of length 2n with up steps labelled by [n] (and unlabelled down steps) such that, for any two consecutive up steps, the label of the second step is greater than the label of the first step, (4) the set of parking functions of size n. Proof by Vanshika. We’ll do just one of them for time. Do a “depth-first search:” go around the tree starting from the left, turning back whenever you run out of space. Every time you go down, go up on the Dyck path, and every time we go up, go down on the Dyck path. This works because consecutive sequences of up steps are always increasing, and by construction, we never go below the x-axis. To go backwards, construct a sequence of arrows: go down every time we go up, and vice versa. There’s n numbers in our tree, so we have 2n number in our Dyck path. To construct the parking function, put f (x) = d if x is in the dth diagonal. 4