Some Combinatorial And Asymptotic Results On Weighted Trees

The class of rooted trees is one of the most important nonlinear structures inthe field of combinatorics. Ordered trees are rooted trees with an ordering asso-ciated with the subtrees of each vertex. It is well-known that lattice paths areclosely related to ordered trees. We present lattice-path interpretations for somecombinatorial identities. Chen, Deutsch and Elizalde gave a bijection between or-dered trees and 2-Motzkin paths; their argument involved distinguishing betweenrightmost and non-rightmost leaves in ordered trees. Coker recently used generat-ing functions to derive two combinatorial identities involving Narayana numbersand Catalan numbers and asked for combinatorial proofs. We answer Coker'squestions by using the Chen-Deutsch-Elizalde bijection and transforming weightsin 2-Motzkin paths. In studying the parity of the number of leaves in orderedtrees, Eu, Liu and Yeh used generating functions to derive a combinatorial iden-tity involving Narayana numbers and Catalan numbers; they also gave a partialbijective proof. We give three di?erent bijections for this identity.At the conference honoring Richard Stanley's 60th birthday Postnikov gavea combinatorial identity involving hook lengths of binary trees, and asked for acombinatorial proof. We give a simple inductive proof of Postnikov's identity. Seoconstructed a bijective proof that involved the composition of three bijections;he also derived analogous identities for hook lengths of k-ary trees and forests ofordered trees. Seo's proofs involved an interpretation in terms of what are calledproper vertices in trees. We use the Lambert-Rothe identity to give a unified proofof Seo's formulas and Postnikov-type identities.Meir and Moon and others have studied simply-generated families of trees;these are weighted families of ordered trees in which the weights are assigned ina certain way. We define a sub-family of simply-generated trees, binomial trees,in which the underlying weights are coe?cients in binomial expansions. Binomialtrees include the ordinary ordered trees and the k-ary trees, for example; and,as we shall see, the labelled unordered trees can be regarded as a limiting case of certain binomial trees. The main purpose of this thesis is to investigate fourstatistics on simply-generated families: leaves, non-rightmost leaves, proper edgesand proper vertices. We use Darboux's theorem to obtain asymptotic results ontheir expectationsμi(n) and variances, where n denotes the number of vertices inthe trees being considered. For any constant 0≤c≤1 (for proper edges, 0≤c≤1/2), we prove that there exists a simply-generated family such thatμi(n)/ntends to c when n→∞. For binomial trees, we derive explicit expressions forμi(n). Using Lyapunov's condition, we prove that the distribution of the numberof proper vertices is asymptotically normal.We conclude this abstract with a chapter-by-chapter summary. We begin Chap-ter 1 with definitions and enumeration formulas for rooted trees and give combi-natorial interpretations of some Abel identities; next we define simply-generatedfamilies and review some basic results; then we introduce binomial families and givesome examples. We study leaves and non-rightmost leaves in Chapter 2 and obtainsome results on their distribution; then we answer questions raised by Coker andby Eu-Liu-Yeh by giving bijective proofs of certain identities involving Narayananumbers and Catalan numbers. In Chapter 3 we use the Lambert-Rothe identityto prove Seo's formulas and Postnikov-type identities. In Chapter 4 we investigateproper edges and proper vertices and obtain results on their distributions.