Linear Recurrences of Generalized Schreier Sets Revisited

Abstract

For $p,q\in \mathbb{N}$, a finite nonempty set $F$ is said to be $(p,q)$-Schreier (or maximal $(p,q)$-Schreier, respectively) if $q\min F\ge p|F|$ (or $q\min F=p|F|$, respectively). For $n\in \mathbb{N}$, let $$\mathcal{S}^{p/q}_{n}\ :=\ |\{F\subset\{1, 2, \ldots, n\}\,:\, q\min F\ge p|F|\mbox{ and }n\in F\}|.$$ Using the Inclusion-Exclusion Principle, Beanland et al. proved the recurrence $$|{\mathcal{S}}_n^{p/q}|=\sum _{k=1}^q(-1{)}^{k+1}(\genfrac{}{}{0ex}{}{q}{k})|{\mathcal{S}}_{n-k}^{p/q}|+|{\mathcal{S}}_{n-(p+q)}^{p/q}|.$$ We show that $(|{\mathcal{S}}_n^{p/q}|{)}_{n=1}^{\infty }$ is a subsequence with terms taken periodically from Padovan-like sequences which satisfy simple recurrence relations. As an application, we obtain an alternative proof of the above linear recurrence. Furthermore, a similar result holds for the sequence $(|{\mathcal{M}}_n^{p/q}|{)}_{n=1}^{\infty }$ that counts maximal $(p,q)$-Schreier sets. We end with a discussion of the relation between $(|{\mathcal{S}}_n^{p/q}|{)}_{n=1}^{\infty }$ and $(|{\mathcal{M}}_n^{p/q}|{)}_{n=1}^{\infty }$.

arXiv comment16 pages, 4 tables