Linear Recurrences from Counting Schreier-Type Multisets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916935951712256 |
|---|---|
| author | Chu, Hung Viet Geng, Yubo King, Julian Miller, Steven J. Tresch, Garrett Vasseur, Zachary Louis |
| author_facet | Chu, Hung Viet Geng, Yubo King, Julian Miller, Steven J. Tresch, Garrett Vasseur, Zachary Louis |
| contents | 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}^{(s)}_{p, n}| = \sum_{i=0}^s|\mathcal{A}^{(s)}_{p, n-1-ip}|.$$ If we color $s$ copies of the same integer by different colors from $1$ to $s$, i.e., $\mathcal{B}^{(s)}_{p, n}:= $ $$\{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}^{(s)}_{p, n}| = \sum_{i=0}^s \binom{s}{i}| \mathcal{B}^{(s)}_{p, n-1-ip}|.$$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05158 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Recurrences from Counting Schreier-Type Multisets Chu, Hung Viet Geng, Yubo King, Julian Miller, Steven J. Tresch, Garrett Vasseur, Zachary Louis Combinatorics 05A19 (primary), 11B37, 11Y55, 05A15 (secondary) 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}^{(s)}_{p, n}| = \sum_{i=0}^s|\mathcal{A}^{(s)}_{p, n-1-ip}|.$$ If we color $s$ copies of the same integer by different colors from $1$ to $s$, i.e., $\mathcal{B}^{(s)}_{p, n}:= $ $$\{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}^{(s)}_{p, n}| = \sum_{i=0}^s \binom{s}{i}| \mathcal{B}^{(s)}_{p, n-1-ip}|.$$ 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. |
| title | Linear Recurrences from Counting Schreier-Type Multisets |
| topic | Combinatorics 05A19 (primary), 11B37, 11Y55, 05A15 (secondary) |
| url | https://arxiv.org/abs/2509.05158 |