Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915399061209088 |
|---|---|
| author | Allen, Michael A. |
| author_facet | Allen, Michael A. |
| contents | Let $S_n$ and $S_{n,k}$ be, respectively, the number of subsets and $k$-subsets of $\mathbb{N}_n=\{1,\ldots,n\}$ such that no two subset elements differ by an element of the set $\mathcal{Q}$, the largest element of which is $q$. We prove a bijection between such $k$-subsets when $\mathcal{Q}=\{m,2m,\ldots,jm\}$ with $j,m>0$ and permutations $π$ of $\mathbb{N}_{n+jm}$ with $k$ excedances satisfying $π(i)-i\in\{-m,0,jm\}$ for all $i\in\mathbb{N}_{n+jm}$. We also identify a bijection between another class of restricted permutation and the cases $\mathcal{Q}=\{1,q\}$ and derive the generating function for $S_n$ when $q=4,5,6$. We give some classes of $\mathcal{Q}$ for which $S_n$ is also the number of compositions of $n+q$ into a given set of allowed parts. We also prove a bijection between $k$-subsets for a class of $\mathcal{Q}$ and the set representations of size $k$ of equivalence classes for the occurrence of a given length-($q+1$) subword within bit strings. We then formulate a straightforward procedure for obtaining the generating function for the number of such equivalence classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00624 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings Allen, Michael A. Combinatorics 05A15 (Primary) 05A19, 05B45, 05A05, 05C20, 11B39 (Secondary) Let $S_n$ and $S_{n,k}$ be, respectively, the number of subsets and $k$-subsets of $\mathbb{N}_n=\{1,\ldots,n\}$ such that no two subset elements differ by an element of the set $\mathcal{Q}$, the largest element of which is $q$. We prove a bijection between such $k$-subsets when $\mathcal{Q}=\{m,2m,\ldots,jm\}$ with $j,m>0$ and permutations $π$ of $\mathbb{N}_{n+jm}$ with $k$ excedances satisfying $π(i)-i\in\{-m,0,jm\}$ for all $i\in\mathbb{N}_{n+jm}$. We also identify a bijection between another class of restricted permutation and the cases $\mathcal{Q}=\{1,q\}$ and derive the generating function for $S_n$ when $q=4,5,6$. We give some classes of $\mathcal{Q}$ for which $S_n$ is also the number of compositions of $n+q$ into a given set of allowed parts. We also prove a bijection between $k$-subsets for a class of $\mathcal{Q}$ and the set representations of size $k$ of equivalence classes for the occurrence of a given length-($q+1$) subword within bit strings. We then formulate a straightforward procedure for obtaining the generating function for the number of such equivalence classes. |
| title | Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings |
| topic | Combinatorics 05A15 (Primary) 05A19, 05B45, 05A05, 05C20, 11B39 (Secondary) |
| url | https://arxiv.org/abs/2409.00624 |