Connections between combinations without specified separations and strongly restricted permutations, compositions, and bit strings

Michael A. Allen*
open access article published in Journal of Integer Sequences 28(3), Article 25.3.7 (2025)

Abstract
Let S_n and S_n,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, 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+jm with k excedances satisfying π(i)−i∈{−m,0,jm} for all i∈ℕ_n+jm. We also identify a bijection between another class of restricted permutation and the cases Q={1,q} and derive the generating functions for S_n when q=4,5,6. We give some classes of 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 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.

Background
An ordinary combination refers to choosing any k objects from n objects, which we can take as the numbers ℕ_n={1,…,n}. A subset containing k objects is called a k-subset. The number of k-subsets of ℕ_n is well known to be ⁿC_k. Combinations without specified separations (also called restricted combinations) refers to choosing k-subsets such that no two elements of the subset differ by an element of the set Q, the largest member of which is q. We let S_n,k denote the number of such subsets and S_n the number of all subsets of ℕ_n that satisfy the disallowed separations requirement. For example, if Q={1} then the allowed subsets of ℕ₄={1,2,3,4} are {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, and {2,4}, and so S_4,0=1, S_4,1=4, S_4,2=3, and S₄=8 in this case. In fact, when Q={1}, it is a classic result that S_n is the Fibonacci number f_n+1 (where f_n=f_n−1+f_n−2+δ_0,n, f_n<0=0), and S_n,k=^n+1−kC_k. Up until recently, the only results for S_n and S_n,k known were the general case Q={m,2m,…,jm} with j,m>0 along with another class of Q (which, among other properties, has 1∈Q). Then the author came up with a 1-1 correspondence between restricted combinations of ℕ_n and a form of tiling of an (n+q)-board (an (n+q)×1 board consisting of 1×1 cells). This bijection allows other results for various other classes of Q to be obtained easily, and in the present paper the author explains how this can be used to obtain the generating functions for S_n and S_n,k for any Q. The coefficients of xⁿ and xⁿy^k in the expansions of generating functions g(x) and g(x,y) equal S_n and S_n,k, respectively. For example, the generating functions for the Q={1} case are g(x)=1/(1−x−x²)=1+x+2x²+3x³+5x⁴+8x⁵+… and g(x,y)=1/(1−x−x²y)=1+x+x²(1+y)+x³(1+2y)+x⁴(1+3y+y²)+x⁵(1+4y+3y²)+…. The n-board is restricted-overlap tiled with 1×1 squares and Q-combs. In general a Q-comb is composed of a number of sub-tiles (called teeth) which, if there is more than one tooth, are separated by gaps. The cells of the Q-comb (whether occupied by a tooth or not) are numbered from 0 to q. Cell 0 of a Q-comb is always occupied by the (start of) the leftmost tooth of the comb. Cell i, where i=1,…,q, is occupied by a tooth if and only if i is in Q. Restricted-overlap tiling means that all but cell 0 of a Q-comb can overlap all but cell 0 of one or more other Q-combs already placed on the board. After all the combs have been placed on the board, any remaining gaps are filled with squares.

The author noticed that S_n for various Q matched existing sequences in the On-Line Encyclopedia of Integer Sequences. One of these connections is illustrated in the figure. A (½,w)-fence is a tile composed of two sub-tiles each of width ½ and separated by a gap of w. They, along with squares, can be used to represent a particular type of restricted permutation characterized by a set D of allowed displacements of the items. A fence representing an upward displacement (known as an excedance) is called an up fence and must be placed so that the left sub-tile is in the left cell side of a cell. A fence representing a downward displacement must be placed so that its right sub-tile is in the left side of a cell on the board. When placed as illustrated in the figure, the fences form a Q-comb (in the figure, the Q-comb correponding to Q={3,6,9}). This forms the basis for the connection between a class of restricted permutation and a class of restricted combination.

Key results
• Bivariate generating functions for the number of walks of a certain length and containing a certain number of objects on two general classes of digraph.
• General procedures for obtaining bivariate generating functions from digraphs with and without the use of transfer matrices.
• A bijection between the cases Q={1,q} and a type of restricted permutation.
• Generating functions for S_n when Q={1,q} for q=4,5,6.
• A bijection between the cases Q={m,2m,…,jm} and restricted permutations with D={−m,0,jm}.
• Expressions for numbers of restricted permutations with D={−m,0,jm} and numbers of such permutations with k excedances in terms of generalized Fibonacci numbers and coefficients of their associated polynomials.
• Condition on Q for S_n to equal the number of compositions of n+q into parts drawn from a finite set and two classes of Q for which this condition holds.
• Necessary conditions on digraph corresponding to Q for S_n to equal the number of compositions of n+q into parts drawn from an infinite set and two classes of Q where S_n does equal the number of such compositions.
• Bijection between subsets of N_n−q for certain Q and the equivalence classes of the appearance of length-(q+1) subword ω in length-n binary words and the associated generating functions.
• Condition on Q for there to exist a corresponding ω.
• An algorithm for efficiently calculating S_n and S_n,k (from first principles) for n up to 32 or 64 for any given Q.

Related resources
[1] Allen MA (2024) Combinations without specified separations. Comm Combinator Optim (in press) doi.org/10.22049/CCO.2024.29370.1959.
[2] Edwards K (2008/2009) A Pascal-like triangle related to the tribonacci numbers. Fibonacci Quart 46/47(1), 18–25.
[3] Edwards K, Allen MA (2015) Strongly restricted permutations and tiling with fences. Discrete Appl. Math. 187, 82–90.
[4] Sloane NJA (2025) The On-Line Encyclopedia of Integer Sequences, oeis.org.