On Schreier-type Sets, Partitions, and Compositions

Abstract

A nonempty set $A\subset \mathbb{N}$ is $\ell$-strong Schreier if $\min A⩾\ell |A|-\ell +1$. We define a set of positive integers to be sparse if either the set has at most two numbers or the differences between consecutive numbers in increasing order are non-decreasing. This note establishes a connection between sparse Schreier-type sets and (restricted) partition numbers. One of our results states that if ${\mathcal{G}}_{n,\ell }$ consists of partitions of $n$ that contain no parts in $\{2,\dots ,\ell \}$, and \begin{equation*} \mathcal{A}_{n,\ell} \ :=\ \{A\subset \{1, \ldots, n\}\,:\, n\in A, A\mbox{ is sparse and }\ell\mbox{-strong Schreier}\}, \end{equation*} then $$|{\mathcal{A}}_{n,\ell }|=|{\mathcal{G}}_{n-1,\ell }|,n,\ell \in \mathbb{N}.$$ The special case ${\mathcal{G}}_{n-1,1}$ consists of all partitions of $n-1$. Besides partitions, integer compositions are also investigated.

10 pages