Connections Between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings

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.