Partitions enumerated by self-similar sequences

Abstract

The Fibonacci numbers are the prototypical example of a recursive sequence, but grow too quickly to enumerate sets of integer partitions. The same is true for the other classical sequences $a(n)$ defined by Fibonacci-like recursions: the tribonacci, Padovan, Pell, Narayana's cows, and Lucas sequences. For each sequence $a(n)$, however, we can define a related sequence $\text{sa}(n)$ by defining $\text{sa}(n)$ to have the same recurrence and initial conditions as $a(n)$, except that $\text{sa}(2n)=\text{sa}(n)$. Growth is no longer a problem: for each $n$ we construct recursively a set $\mathcal{S}\mathcal{A}(n)$ of partitions of $n$ such that the cardinality of $\mathcal{S}\mathcal{A}(n)$ is $\text{sa}(n)$. We study the properties of partitions in $\mathcal{S}\mathcal{A}(n)$ and in each case we give non-recursive descriptions. We find congruences for $\text{sa}(n)$ and also for $\text{psa}(n)$, the total number of parts in all partitions in $\mathcal{S}\mathcal{A}(n)$.

36 pages