pre brown

Slide1: 

By Tomislav Doslic Presented by Cody Brown

What the flip is a Catalan number?: 

What the flip is a Catalan number? Belgian mathematician – Eugene Charles Catalan A sequence of natural numbers used in combinatorial mathematics; used often in problems involving recursion.

Benzenoid Graph: 

Benzenoid Graph A graph of congruent hexagons that are constructed in such a way that two hexagons are either completely disjoint or have one common edge. Gets its name from chemistry. Benzenoid hydrocarbons that are constructed in a plane pattern of rings of length six.

Perfect Matching: 

Perfect Matching In a graph, G, it is the collection M of edges of G such that every vertex of G connects with exactly one edge from M. The number of different perfect matchings in a graph, G, are denoted as Φ(G).

Slide5: 

Monotonic path – connects peak and valley such that after starting at a peak, it always goes downwards. w i, j (B) are the number of monotonic paths is graph B. W (B) is the matrix that is constructed with those elements. W (B) will be restricted to a square matrix, since we deal with graphs that have perfect matchings. W (B) need not be symmetric. Φ (B) = │det W (B)│ according to formula given by John and Sachs. Formula also can be obtained by using the Gessel – Viennot theorem.

Slide6: 

W (B) = det W (B) = 27

Slide7: 

Triangular benzenoid graph Tn where counting monotonic paths becomes too tedious. To do so, construct a graph R (i) where i is the peak with property Graph is induced by all the vertices of Tn that can be reached from peak i by monotonic paths. Graph is called a wetting region of peak i.

Slide8: 

To get the number of monotonic paths from peak i to valley v at level m+1, you would sum the number of monotonic paths from peak i to valleys v’ and v”. Number of monotonic paths has similar pattern to that of Pascal’s triangle.

Slide9: 

From the formula Pascal used to get the binomial coefficient, we obtain the formula: By substituting j=i+k , the formula becomes: The same reasoning works for a wetting region of peak i that is not triangular, as well.

Slide10: 

Elements of matrix W (Tn) are given by: By using John-Sachs formula, the determinant is equal to the number of perfect matchings: Formula 1 →

Slide11: 

Now we must find Φ (Tn). To do so, we use a benzenoid parallelogram, B3,4 that contains perfect matchings as the one below. The number of perfect matchings in Bm,n is We will now go on to prove the bijective correspondence between perfect matchings in Bm,n and lattice paths in a rectangular lattice from (0,0) to (n,m) with steps travelling east and north.

Lemma 1 & 2: 

Lemma 1 & 2 Lemma 1 – Every perfect matching in a benzenoid parallelogram Bm,n contains precisely one vertical edge of each row. Use Direct Proof to show that when vertical edges of one row are taken out, then all vertices are not accounted for in the perfect matching. Lemma 2 – The sequence (i1,……, im) is non-decreasing for every perfect matching M of a benzenoid parallelogram Bm,n . Proof by contradiction, saying that the sequence does decrease.

More fun proof stuff: 

More fun proof stuff Corollary 3 – Let M be a perfect matching in Bm,n containing the vertical edge ip in row p. Then the part of M lying in the rows p+1,……, m, left from their respective ipth vertical edges, is uniquely determined. Similarly, the part of M lying in the rows 1,……, p-1, right to their respective ipth rows, is uniquely determined. Saying that the perfect matching is uniquely determined when you’ve designated an edge as part of a perfect matching. You can only have one way of finding the rest of the edges in the perfect matching.

Proposition 4 & 5: 

Proposition 4 & 5 Proposition 4 – There is a bijection between the set of all perfect matchings in Bm,n and the set of all non-decreasing sequences of length m with elements from {0,1,…,n}. Direct proof using Lemma 2 and Corollary 3 Proposition 5 – There is a one-to-one correspondence between the set of all lattice paths from (0,0) to (n,m) with east and north steps and the set of all non-decreasing sequences of length m with elements from {0,1,…,n}. Direct Proof proving that abscissas of a lattice path is a non-decreasing sequence and that a non-decreasing sequence can construct a lattice path with given parameters.

Proof continued: 

Proof continued By combining Proposition 4 & 5, we get our bijective correspondence between lattice paths and perfect matchings.

Result: 

Result Lattice paths are found using the nth Catalan number Therefore, by deriving recurrence formulas for the number of perfect matchings in benzenoid graphs, we obtain Φ (Tn) = Cn+1. Therefore, by substitution of our other formula (1), we get: