This thesis concerns the use of labelled infinite trees to solve families of nested recursions of the form $R(n)=\sum_{i=1}^kR(n-a_i-\sum_{j=1}^{p_i}R(n-b_{ij}))+w$, where $a_i$ is a nonnegative integer, $w$ is any integer, and $b_{ij},k,$ and $p_i$ are natural numbers. We show that the solutions to many families of such nested recursions have an intriguing combinatorial interpretation, namely, they count nodes on the bottom level of labelled infinite trees that correspond to the recursion. Furthermore, we show how the parameters defining these recursion families relate in a natural way to specific structural properties of the corresponding tree families. We introduce a general tree ``pruning" methodology that we use to establish all the required tree-sequence correspondences.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/65478 |
| Date | 19 June 2014 |
| Creators | Isgur, Abraham |
| Contributors | Tanny, Stephen |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds