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

Let Sₙ and S₍, ₊ be, respectively, the number of subsets and k-subsets of Nₙ=\1, , n\ such that no two subset elements differ by an element of the set Q. We prove a bijection between such k-subsets when Q=\m, 2m, , jm\ with j, m>0 and permutations of N₍+₉₌ with k excedances satisfying (i) -i\-m, 0, jm\ for all i₍+₉₌. We also identify a bijection between another class of restricted permutation and the cases Q=\1, q\. This bijection allows us to prove a conjectured recursion relation for the number of such permutations which corresponds to the case Q=\1, 4\. We also obtain recursion relations for Sₙ and S₍, ₊ in the case Q=\1, 5\ by first obtaining related recursion relations for the numbers of closed walks of a given length on a particular class of directed pseudograph. We give some classes of Q for which Sₙ is also the number of compositions of n+q into a given set of allowed parts, where q is the largest element of Q. A bijection between the k-subsets for any Q and bit strings is also noted. Aided by this, an efficient algorithm for finding Sₙ and S₍, ₊ is given. 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.