pre brown

50 %
50 %
Information about pre brown

Published on January 16, 2008

Author: Carmina


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:

Add a comment

Related presentations

Related pages

Pre-College Programs at Brown University | Brown University

Your Summer Starts Here. Challenge, Discovery, Success. Talented students from around the world choose Brown University Pre-College Programs to prepare for ...
Read more

Brown-PRE-Stutfohlen - Andalusier zu verkaufen: Stute ...

Quiera, Brown PRE-Stutfohlen zu verkaufen Originalarbeiten ANCCE registriert Guter Geist und bewegt sich 6 andere PRE-Fohlen im Jahr 2016 kommen
Read more

Pre-reptile may be earliest known to walk upright on all ...

PROVIDENCE, R.I. [Brown University] — A newly published analysis of the bones of Bunostegos akokanensis, a 260-million-year-old pre-reptile, finds that ...
Read more

Brown Pre-Med - Facebook

Brown Pre-Med, Providence, RI. 466 likes · 1 talking about this. Brown Pre-med AMSA (American Medical Students Association) is a student-governed,...
Read more

P.R.E. Mare Foal Brown

Horse's name STELLA Breed P.R.E. Gender Mare Age Foal Color Brown Ability
Read more

Ford Madox Brown - Wikipedia, the free encyclopedia

Ford Madox Brown (16 April 1821 ... Julian Treuherz, Ford Madox Brown: Pre-Raphaelite Pioneer, Philip Wilson Publishers, 2011, ISBN 978-0-856677-00-7, p. 12.
Read more

Brown University Pre-College Programs - Facebook

Brown University Pre-College Programs, Providence, RI. 43,296 likes · 478 talking about this · 1,768 were here. The official page for Brown University...
Read more

Brown University Pre-College - YouTube

An inside look at Brown University's Pre-College program and the Summer@Brown experience. Learn more at
Read more

Home - Chris Brown

Dec 18 2015 Chris Brown’s new album “ROYALTY” Available Everywhere! Sep 18 2015 “Zero” Available For Download Now! Get The Newsletter
Read more

PremiCron® - B. Braun Sharing Expertise

PremiCron® ist ein synthetisches, nicht resorbierbares, geflochtenes Multifilament bestehend aus Polyesterfasern. PremiCron® Nahtmaterial ist ...
Read more