Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings
Issued Date
2025-01-01
Resource Type
eISSN
15307638
Scopus ID
2-s2.0-105011988503
Journal Title
Journal of Integer Sequences
Volume
28
Issue
3
Rights Holder(s)
SCOPUS
Bibliographic Citation
Journal of Integer Sequences Vol.28 No.3 (2025)
Suggested Citation
Allen M.A. Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings. Journal of Integer Sequences Vol.28 No.3 (2025). Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/111517
Title
Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings
Author(s)
Author's Affiliation
Corresponding Author(s)
Other Contributor(s)
Abstract
Let S<inf>n</inf> and S<inf>n,k</inf> be, respectively, the number of subsets and k-subsets of N<inf>n</inf> = {1, …, n} such that no two subset elements differ by an element of the set Q, the largest element of which is q. We prove a bijection between such k-subsets when Q = {m, 2m, …, jm} with j, m > 0 and permutations π of N<inf>n+jm</inf> with k excedances satisfying π(i) − i ∈{−m, 0, jm} for all i ∈ N<inf>n+jm</inf> . We also identify a bijection between another class of restricted permutation and the cases Q = {1, q} and derive the generating function for S<inf>n</inf> when q = 4, 5, 6. We give some classes of Q for which S<inf>n</inf> 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 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.