Combinations without specified separations

Michael A. Allen*
open access article published in Communications in Combinatorics and Optimization 11(2), 695–711 (2026)

Abstract
We consider the restricted subsets of ℕ_n={1,2,…,n} with q≥1 being the largest member of the set Q of disallowed differences between subset elements. We obtain new results on various classes of problem involving such combinations lacking specified separations. In particular, we find recursion relations for the number of k-subsets for any Q when |ℕ_q−Q|≤2. The results are obtained, in a quick and intuitive manner, as a consequence of a bijection we give between such subsets and the restricted-overlap tilings of an (n+q)-board (a linear array of n+q square cells of unit width) with squares (1×1 tiles) and combs. A (w₁,g₁,w₂,g₂,…,g_t−1,w_t)-comb is composed of t sub-tiles known as teeth. The i-th tooth in the comb has width w_i and is separated from the (i+1)-th tooth by a gap of width g_i. Here we only consider combs with w_i,g_i∈ℤ⁺. When performing a restricted-overlap tiling of a board with such combs and squares, the leftmost cell of a tile must be placed in an empty cell whereas the remaining cells in the tile are permitted to overlap other non-leftmost filled cells of tiles already on the board.

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). In the present paper the author shows that there is 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 one to easily find recursion relations for S_n and S_n,k for various other classes of Q.

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 simplest non-trivial example of a class of Q-combs (denoted by C) is shown in the figure; a comb in this class is referred to as an (l,1,r)-comb as it has a left tooth of length l, a gap of length 1, and a right tooth of length r. This corresponds to a Q containing all positive integers up to q=l+r except one value, namely, l. In general, restricted-overlap tiling using Q-combs and squares (denoted by S) is best analysed in terms of tilings using metatiles. A metatile is a grouping of tiles with no gaps that cannot be split into smaller metatiles. The construction of some metatiles when tiling with squares and (l,1,r)-combs are illustrated in the figure (where, for clarity, some of the overlapping tiles are shown displaced downwards a little from their final position). All possible metatiles can be generated with the aid of digraph: any path starting and ending at the 0 node without visiting it in between corresponds to a metatile. There are just 3 possible metatiles when r is not less than l. If r is less than l then there is an infinite family of metatiles owing to the loop at the 01^r node which can be traversed an arbitrary number of times. The numbers in the subscripts in the arc labels give the contribution of the addition of that tile to the overall length of the metatile. Knowing the lengths of all possible metatiles allows us to obtain the recursion relations for S_n and S_n,k.

Key results
• A bijection between combinations with disallowed separations and restricted-overlap tilings with squares and combs.
• Recursion relations for S_n and S_n,k for 5 classes of Q.

Related resources
[1] Allen MA (2025) Connections between combinations without specified separations and strongly restricted permutations, compositions, and bit strings. J Integer Sequences 28, 25.3.7.