Linear Recurrences of Generalized Schreier Sets Revisited

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\mathrm{\mid }F\mathrm{\mid }$ (or $q\min F=p\mathrm{\mid }F\mathrm{\mid }$, respectively). For $n\in \mathbb{N}$, let $${\mathcal{S}}_n^{p\mathrm{/}q}:=\mathrm{\mid }\{F\subset \{1,2,\dots ,n\}:q\min F\ge p\mathrm{\mid }F\mathrm{\mid }andn\in F\}\mathrm{\mid }\mathrm{.}$$ Using the Inclusion-Exclusion Principle, Beanland et al. proved the recurrence $$\mathrm{\mid }{\mathcal{S}}_n^{p\mathrm{/}q}\mathrm{\mid }=\sum _{k=1}^q(-1{)}^{k+1}\left(\genfrac{}{}{0px}{}{q}{k}\right)\mathrm{\mid }{\mathcal{S}}_{n-k}^{p\mathrm{/}q}\mathrm{\mid }+\mathrm{\mid }{\mathcal{S}}_{n-(p+q)}^{p\mathrm{/}q}\mathrm{\mid }\mathrm{.}$$ We show that $(\mathrm{\mid }{\mathcal{S}}_n^{p\mathrm{/}q}\mathrm{\mid }{)}_{n=1}^{\mathrm{\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 $(\mathrm{\mid }{\mathcal{M}}_n^{p\mathrm{/}q}\mathrm{\mid }{)}_{n=1}^{\mathrm{\infty }}$ that counts maximal $(p,q)$-Schreier sets. We end with a discussion of the relation between $(\mathrm{\mid }{\mathcal{S}}_n^{p\mathrm{/}q}\mathrm{\mid }{)}_{n=1}^{\mathrm{\infty }}$ and $(\mathrm{\mid }{\mathcal{M}}_n^{p\mathrm{/}q}\mathrm{\mid }{)}_{n=1}^{\mathrm{\infty }}$.