Linear Recurrences of Generalized Schreier Sets Revisited

2025/06/17 by Chu, Hung Viet, Vasseur, Zachary Louis · 1 citation
Computer Science · Mathematics · #05A15 (secondary) #05A19 (primary) #11B37 #11Y55 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2506.14312

openalex publication_date 2025/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

For p, q∈ ℕ, a finite nonempty set F is said to be (p,q)-Schreier (or maximal (p,q)-Schreier, respectively) if qmin F≥ p|F| (or qmin F = p|F|, respectively). For n∈ ℕ, let S^p/q_n := |\F⊂\1, 2, …, n\ : qmin F≥ p|F| and n∈ F\|. Using the Inclusion-Exclusion Principle, Beanland et al. proved the recurrence |S^p/q_n| = ∑_k=1^q(-1)^k+1\binomqk|S^p/q_n-k| + |S^p/q_n-(p+q)|. We show that (|S^p/q_n|)_n=1^∞ 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 (|M^p/q_n|)_n=1^∞ that counts maximal (p,q)-Schreier sets. We end with a discussion of the relation between (|S^p/q_n|)_n=1^∞ and (|M^p/q_n|)_n=1^∞.

Citations

• Schreier Multisets and the s-step Fibonacci Sequences

Cited by

• Linear Recurrences from Counting Schreier-Type Multisets
• Schreier Sets of Intervals, Super-Schreier Sets, and Catalan Numbers

Related

• Linear Recurrences from Counting Schreier-Type Multisets
• A Note on the Fibonacci Sequence and Schreier-type Sets
• Schreier Multisets and the s-step Fibonacci Sequences
• Higher Order Fibonacci Sequences from Generalized Schreier sets
• Schreier Numbers and Nontrivial Small Divisors Satisfying Linear Recurrence of Order at Most Two