Title page for ETD etd-09192005-201149

Type of Document

Master's Thesis

Author

D'Souza, Erwin Francis,

URN

etd-09192005-201149

Title

Automating the enumeration of sequences defined by digraphs

Degree

Master of Science

Graduate Program

Computer Science

Advisory Committee

Advisor Name	Title
Dr. Carla Savage	Committee Chair
Dr. Erich Kaltofen	Committee Member
Dr. Jon Doyle	Committee Member
Dr. Mehmet Ozturk	Committee Member

Keywords

GFPartitions
Maple
constraint graphs
recurrences
generating functions
integer sequences

Date of Defense

2005-09-19

Availability

unrestricted

Abstract

We consider sequences of nonnegative integers $S=(s_1,s_2,ldots, s_n)$
defined by systems of constraints represented as
weighted directed graphs
in which edge $(s_a,s_b)$ of weight $w$
indicates constraint $s_a~geq~s_b~+~w$.
We propose a set of seven rules and a decomposition technique
for obtaining multivariate and single-variable
generating functions for families of such graphs.
Our method compares to existing techniques
by offering an elegant and intuitive approach to obtaining generating functions and recurrences,
albeit only for a subset of the partition and composition enumeration problems
addressed by other techniques.
The decomposition technique we propose
remains relevant, nevertheless, to a wide range of applications, including several
well-known ones.
Moreover, our objective is to obtain recurrences for
generating functions so as to assist the formulation and proof of
their closed-form solutions.
For integer sequences defined by directed graphs with $w in {0,1}$,
we prove that our technique
holds sufficient.

We describe the formulation of finite-variable generating function recurrences
from multi-variable ones and provide a set of rules to determine
the variables chosen.
The construction tree is introduced as
the tree representation of the construction of a generating function from the
decomposition of a weighted directed graph.
Given such a construction tree,
automation of the process of building the multi-variable and finite-variable recurrences
is possible, and we implement it as a computer program.

Finally, we apply our techniques and tools to a wide range of famous problems, including
2-rowed plane partitions, up-down compositions and hexagonal plane partitions,
as well as some new problems, and obtain recurrences to each.
We find that our methods are not only effective but also easy and simple to use.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	964.99 Kb	00:04:28	00:02:17	00:02:00	00:01:00	00:00:05