Combinatorial problems related to sequences with repeated entries
Date
2006-11-15T09:25:22Z
Authors
Archibald, Margaret Lyn
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Sequences of numbers have important applications in the field of Computer Science.
As a result they have become increasingly regarded in Mathematics, since analysis
can be instrumental in investigating algorithms.
Three concepts are discussed in this thesis, all of which are concerned with ‘words’
or ‘sequences’ of natural numbers where repeated letters are allowed:
• The number of distinct values in a sequence with geometric distri-
bution
In Part I, a sample which is geometrically distributed is considered, with the
objective of counting how many different letters occur at least once in the
sample. It is concluded that the number of distinct letters grows like log n as
n → ∞. This is then generalised to the question of how many letters occur
at least b times in a word.
• The position of the maximum (and/or minimum) in a sequence
with geometric distribution
Part II involves many variations on the central theme which addresses the
question: “What is the probability that the maximum in a geometrically distributed
sample occurs in the first d letters of a word of length n?” (assuming
d ≤ n). Initially, d is considered fixed, but in later chapters d is allowed to
grow with n. It is found that for 1 ≤ d = o(n), the results are the same as
when d is fixed.
• The average depth of a key in a binary search tree formed from a
sequence with repeated entries
Lastly, in Part III, random sequences are examined where repeated letters
are allowed. First, the average left-going depth of the first one is found,
and later the right-going path to the first r if the alphabet is {1, . . . , r} is
examined. The final chapter uses a merge (or ‘shuffle’) operator to obtain
the average depth of an arbitrary node, which can be expressed in terms of
the left-going and right-going depths.
Description
Student Number : 9708525G -
PhD thesis -
School of Mathematics -
Faculty of Science
Keywords
generating functions, Mellin transforms, Rice's method, geometric distribution, binary search trees