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

Let Sₙ and Sn,k 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=,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 Sn,k 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 Sn,k 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.