Linear Recurrences from Counting Schreier-Type Multisets

Abstract

A nonempty set $F$ is Schreier if $\min F\ge |F|$. Bird observed that counting Schreier sets in a certain way produces the Fibonacci sequence. Since then, various connections between variants of Schreier sets and well-known sequences have been discovered. Building on these works, we prove a linear recurrence for the sequence that counts multisets $F$ with $\min F\ge p|F|$. In particular, if we let $$\mathcal{A}^{(s)}_{p, n}\ :=\ \{F\subset \{\underbrace{1, \ldots, 1}_{s}, \ldots, \underbrace{n-1, \ldots, n-1}_{s}, n\}\,:\,n\in F\mbox{ and }\min F\ge p|F|\},$$ then $$|{\mathcal{A}}_{p,n}^{(s)}|=\sum _{i=0}^s|{\mathcal{A}}_{p,n-1-ip}^{(s)}|.$$ If we color $s$ copies of the same integer by different colors from $1$ to $s$, i.e., ${\mathcal{B}}_{p,n}^{(s)}:=$ $$\{F\subset \{1_{1}, \ldots, 1_{s}, \ldots, (n-1)_1, \ldots, (n-1)_{s}, n\}\,:\,n\in F\mbox{ and }\min F\ge p|F|\},$$ then $$|{\mathcal{B}}_{p,n}^{(s)}|=\sum _{i=0}^s\left(\genfrac{}{}{0ex}{}{s}{i}\right)|{\mathcal{B}}_{p,n-1-ip}^{(s)}|.$$ Lastly, we count Schreier sets that do not admit multiples of a given integer $u\ge 2$ and witness linear recurrences whose coefficients are drawn from the $u$th row of the Pascal triangle and have alternating signs, except possibly the last one.

22 pages, 3 tables