A new combinatorial interpretation of partial sums of $m$-step Fibonacci numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917957017272320 |
|---|---|
| author | Bates, Erik Morrison, Blan Rogers, Mason Serafini, Arianna Sood, Anav |
| author_facet | Bates, Erik Morrison, Blan Rogers, Mason Serafini, Arianna Sood, Anav |
| contents | The sequence of partial sums of Fibonacci numbers, beginning with $2$, $4$, $7$, $12$, $20$, $33,\dots$, has several combinatorial interpretations (OEIS A000071). For instance, the $n$-th term in this sequence is the number of length-$n$ binary words that avoid $110$. This paper proves a related but new interpretation: given a length-$3$ binary word -- called the keyword -- we say two length-$n$ binary words are equivalent if one can be obtained from the other by some sequence of substitutions: each substitution replaces an instance of the keyword with its negation, or vice versa. We prove that the number of induced equivalence classes is again the $n$-th term in the aforementioned sequence. When the keyword has length $m+1$ (instead of $3$), the same result holds with $m$-step Fibonacci numbers. What makes this result surprising -- and distinct from the previous interpretation -- is that it does not depend on the keyword, despite the fact that the sizes of the equivalence classes do. On this final point, we prove several results on the structure of equivalence classes, and also pose a variety of open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_11055 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A new combinatorial interpretation of partial sums of $m$-step Fibonacci numbers Bates, Erik Morrison, Blan Rogers, Mason Serafini, Arianna Sood, Anav Combinatorics 05A05, 05A15, 11B39 The sequence of partial sums of Fibonacci numbers, beginning with $2$, $4$, $7$, $12$, $20$, $33,\dots$, has several combinatorial interpretations (OEIS A000071). For instance, the $n$-th term in this sequence is the number of length-$n$ binary words that avoid $110$. This paper proves a related but new interpretation: given a length-$3$ binary word -- called the keyword -- we say two length-$n$ binary words are equivalent if one can be obtained from the other by some sequence of substitutions: each substitution replaces an instance of the keyword with its negation, or vice versa. We prove that the number of induced equivalence classes is again the $n$-th term in the aforementioned sequence. When the keyword has length $m+1$ (instead of $3$), the same result holds with $m$-step Fibonacci numbers. What makes this result surprising -- and distinct from the previous interpretation -- is that it does not depend on the keyword, despite the fact that the sizes of the equivalence classes do. On this final point, we prove several results on the structure of equivalence classes, and also pose a variety of open problems. |
| title | A new combinatorial interpretation of partial sums of $m$-step Fibonacci numbers |
| topic | Combinatorics 05A05, 05A15, 11B39 |
| url | https://arxiv.org/abs/2503.11055 |