Combinatorial problems related to sequences with repeated entries

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.