Document Type

Dissertation

Date of Award

1976

Keywords

Combinatorial enumeration problems, Trees (Graph theory)

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematical Sciences

First Advisor

David A. Klarner

Second Advisor

Louis F. McAuley

Third Advisor

David L. Hanson

Abstract

Combinatorics involves a wide range of enumeration problems. Many such problems have some characteristics in common. As an example, various structures can be related to a set of plane trees that has eliminated all trees that contain any element of a defined set of forbidden substructures. In computer science, such a set of plane trees can be used to describe lists. The cell growth problem can also be investigated in a similar manner.

This thesis defines a general process to handle plane tree enumeration problems. The purpose is to develop a process to enumerate the number of r–ary, rooted, plane trees with n vertices of degree r that do not contain any elements of a defined set of forbidden trees as subtrees. The process is developed in terms of a finite set of forbidden trees but it can also handle an infinite set of forbidden structures. In the latter case, a decreasing sequence of upper bounds are calculated by applying the process to an increasing sequence of forbidden subsets. Whether this sequence of upper bounds converges to the desired number is an open question. The development is divided into three chapters.

Chapter 2 formally defines the enumeration problem. A structure defined as a twig is introduced to serve as a substructure of a tree which retains a record of the directions of additional paths. Forbidden substructures are defined in terms of these twigs. The set of all twigs is partially ordered and the generating function F=n=1 f(n)xn of the desired set if defined. The major result is the reduction of the combinatorial problem to an analytic problem. A system of polynomial equations is created, each of which is satisfied by F and an additional set of generating functions related to the desired set of trees.

The following chapter begins with the analytic problem created previously. A process is defined that reduces a system of polynomials created from enumeration problems to a single polynomial that is satisfied by a function F. Results that relate the radius of convergence of F to the discriminant of the polynomial it satisfies follows. Other general properties of algebraic functions are also investigated.

Chapter 4 applies the technique developed to some specific enumeration problems. The technique is first modified to provide for a simpler application to these specific examples. Then upper bounds are calculated for the number of leftist trees with n vertices of degree 2 and for the number of square, hexagonal, and triangular-celled animals with n cells.

Download

Share

COinS