Combinations without specified separations

The problem of enumerating combinations with disallowed separations is as follows. We wish to find the number $S_{n}$ of subsets of $\mathbb{N}_{n}=\{1,2,\ldots,n\}$ satisfying the condition $\left\lvert x-y\right\rvert\notin\mathcal{Q}$ where $x,y$ is any pair of elements in the subset and $\mathcal{Q}$ is a given nonempty subset of $\mathbb{Z}^{+}$. We also wish to find the number $S_{n,k}$ of such subsets of $\mathbb{N}_{n}$ that are of size $k$. For $\mathcal{Q}=\{1\}$ it is well known that $S_{n}=F_{n+2}$ where $F_{j}$ is the $j$-th Fibonacci number defined by $F_{j}=F_{j-1}+F_{j-2}+\delta_{j,1}$ with $F_{j<1}=0$, where $\delta_{i,j}$ is 1 if $i=j$ and 0 otherwise, and $S_{n,k}=\tbinom{n+1-k}{k}$ [12]. The quantity $\tbinom{n+1-k}{k}$ is also the number of ways of tiling an $(n+1)$-board (i.e., an $(n+1)\times 1$ board of unit square cells) using unit squares and $k$ dominoes ($2\times 1$ tiles) [6]. This correspondence can be regarded as a result of the bijection given in [3], generalized in [1], and that we will extend to the most general case here. It also appears to be well known that if $\mathcal{Q}=\{1,\ldots,q\}$ then $S_{n}=S_{n-1}+S_{n-q-1}+\delta_{n+q,0}$ with $S_{n+q<0}=0$. Expressions for the number of combinations when $\mathcal{Q}=\{2\}$, $\mathcal{Q}=\{q\}$ for $q\geq 2$, and $\mathcal{Q}=\{m,2m,\ldots,jm\}$ for $j,m\geq 1$ are derived in [14], [19, 16, 15], and [17, 1], respectively.

$S_{n,k}$ also has links with graph theory. A path scheme $P(n,\mathcal{Q})$ is an undirected graph with vertex set $V=\mathbb{N}_{n}$ and edge set $\{(x,y):\left\lvert x-y\right\rvert\in\mathcal{Q}\}$ [13]. A subset $\mathcal{S}$ of $V$ is said to be an independent set (or a stable set) if no two elements of $\mathcal{S}$ are adjacent. The number of independent sets of path scheme $P(n,\mathcal{Q})$ of size $k$ is then clearly $S_{n,k}$ (and the total number is $S_{n}$). The elements $q_{i}$ for $i=1,\ldots,\left\lvert\mathcal{Q}\right\rvert$ of set $\mathcal{Q}$ are said to form a well-based sequence if, when ordered so that $q_{j}>q_{i}$ for all $j>i$, then $q_{1}=1$ and for all $j>1$ and $\Delta=1,\ldots,q_{j}-1$, there is some $q_{i}$ such that $q_{j}=q_{i}+\Delta$ [21, 13]. Equivalently, the sequence of elements of $\mathcal{Q}$, the largest of which is $q$, is well based if $a=\left\lvert\mathbb{N}_{q}-\mathcal{Q}\right\rvert$ is zero or if for all $i,j=1,\ldots,a$ (where $i$ and $j$ can be equal), $p_{i}+p_{j}\notin\mathcal{Q}$ where the $p_{i}$ are the elements of $\mathbb{N}_{q}-\mathcal{Q}$. E.g., the only well-based sequences of length 3 are the elements of the sets $\{1,2,3\}$, $\{1,2,4\}$, $\{1,2,5\}$, and $\{1,3,5\}$. By considering $P(n,\mathcal{Q})$, Kitaev obtained an expression for the generating function of $S_{n}$ when the elements of $\mathcal{Q}$ are a well-based sequence [13]. We will show the result via combinatorial proof and also obtain a recursion relation for $S_{n,k}$.

We define a $(w_{1},g_{1},w_{2},g_{2},\ldots,g_{t-1},w_{t})$-comb as a linear array of $t$ sub-tiles (which we refer to as teeth) of dimensions $w_{i}\times 1$ separated by $t-1$ gaps of width $g_{i}$. The length of a comb is $\sum_{i=1}^{t-1}(w_{i}+g_{i})+w_{t}$. When the $t$ teeth are all of width $w$ and the $t-1$ gaps are all of width $g$, it is referred to as a $(w,g;t)$-comb [4]; such combs can be used to give a combinatorial interpretation of products of integer powers of two consecutive generalized Fibonacci numbers [5]. Evidently, a $(w,g;1)$-comb (or $w$-comb) is just a $w$-omino (and a $(w,0;n)$-comb is an $nw$-omino). A $(w,g;2)$-comb is also known as a $(w,g)$-fence. The fence was introduced in [7] to obtain a combinatorial interpretation of the tribonacci numbers as the number of tilings of an $n$-board using just two types of tiles, namely, squares and $(\frac{1}{2},1)$-fences. $(\frac{1}{2},g)$-fences have also been used to obtain results on strongly restricted permutations [8].

In this paper, we start in §2 by giving the bijection between combinations with disallowed separations and the restricted-overlap tilings of boards with squares and combs. Counting these types of tilings requires knowledge of all permissible minimal gapless configurations of square-filled and/or restricted overlapping combs known as metatiles which are introduced in §3. In §4 we derive results from which recursion relations for $S_{n,k}$ (or $S_{n}$) for various classes of the set of disallowed differences $\mathcal{Q}$ can be obtained.

In order to formulate the bijection we first introduce the concept of the restricted-overlap tiling of an $n$-board. In this type of tiling, any cell but the leftmost cell of a tile is permitted to overlap any non-leftmost cell of another tile. The $C^{2}$, $C^{2}S$, and $C^{3}S$ metatiles in Figure 1 are examples where such overlap occurs (note that in that figure and in Figure 3, for clarity, some of the overlapping tiles are shown displaced downwards a little from their final position). It is readily seen that when tiling an $n$-board, only tiles with gaps can overlap in this sense and so restricted-overlap tiling of $n$-boards with just squares and other $w$-ominoes is the same as ordinary tiling.

Let $q$ be the largest element in the set $\mathcal{Q}$ of disallowed differences. The comb corresponding to $\mathcal{Q}$ is of length $q+1$, has cells numbered from 0 to $q$, and is constructed as follows. By definition, cells 0 and $q$ are filled (as they are the end teeth or parts of them). For the cells in between, cell $i$ (for $i=1,\ldots,q-1$) is filled if and only if $i\in\mathcal{Q}$. For example, $\mathcal{Q}=\{1,2,4\}$ corresponds to a $(3,1,1)$-comb. One could also regard it as a $(1,0,2,1,1)$-comb but for simplicity we insist that all teeth and gaps in a comb corresponding to $\mathcal{Q}$ are of positive width. This ensures that there is only one comb that corresponds to a given $\mathcal{Q}$.

To illustrate the bijection, we return to the $\mathcal{Q}=\{1,2,4\}$ example. The first case of an allowed subset of $\mathbb{N}_{n}$ with more than one element is $\{1,4\}$ which can only occur if $n\geq 4$. This subset corresponds to the restricted-overlap tiling of an $(n+4)$-board with the first comb (corresponding to the element 1) placed at the start (cell number 1) of the board and the second comb (corresponding to the element 4) placed with its start in the gap of the first comb which is at cell number 4 of the board. As the length of a $(3,1,1)$-comb is 5, a board of length at least 8 is required for such a tiling. The remaining empty cells on the board (cell 7 and any cells beyond cell 8) are filled with squares.

The bijection also applies in the $\mathcal{Q}=\varnothing$ case if we set $q=0$. The comb corresponding to $\mathcal{Q}$ is then a square (but we still call it a comb to distinguish it from the ordinary squares) so $S_{n,k}$ is the number of tilings of an $n$-board using $k$ square combs (and $n-k$ ordinary squares) which is $\tbinom{n}{k}$.

Let $B_{n}$ be the number of ways to restricted-overlap tile an $n$-board with squares and combs corresponding to $\mathcal{Q}$, and let $B_{n,k}$ be the number of such tilings that use $k$ combs. We choose to set $B_{0}=B_{0,0}=1$.

It can be seen that restricted-overlap tiling with squares and just one type of $(1,g;t)$-comb, where $g=0,1,2\ldots$, will result in no overlap of the combs and so the number of such tilings is the same as for ordinary tiling. For other types of comb, there will be some tilings where overlap occurs. The case $\mathcal{Q}=\{m,2m,\ldots,jm\}$ with $j,m\geq 1$ as studied in [17, 1], which is a generalization of all the other cases for which results for $S_{n,k}$ were obtained previously, corresponds to tiling with squares and $(1,m-1;j+1)$-combs. Thus any results for $S_{n,k}$ we obtain for nonempty $\mathcal{Q}$ not of this form (and so overlap does occur) will be new ones.

We extend the definition of a metatile given in [7, 8] to the case of restricted-overlap tiling. A metatile is a minimal arrangement of tiles with restricted overlap that exactly covers a number of adjacent cells without leaving any gaps. It is minimal in the sense that if one or more tiles are removed from a metatile then the result is no longer a metatile.

When tiling with squares (denoted by $S$) and combs corresponding to $\mathcal{Q}$ (denoted by $C$), the two simplest metatiles are the free square (i.e., a square which is not inside a comb), and a comb with all the gaps filled with squares. The symbolic representation of the latter metatile is $CS^{g}$ where $g=\sum_{i}g_{i}$. If a comb has no gaps then it is a $(q+1)$-omino and is therefore a metatile by itself.

If the comb contains a gap, we can initiate the creation of at least one more metatile by placing the start of another comb in the gap. For instance, in the case of an $(l,1,r)$-comb where $r\geq l$, this is the only other possible metatile and so there are three metatiles in total (Figure 1a). However, if $r<l$, adding a comb leaves a gap which can be filled either with a square to form a completed metatile ($C^{2}S$) or with another comb which will leave a further gap, and so on (Figure 1b). Thus the possible metatiles in this case are $C^{m}S$ for $m=0,1,2,\ldots$. More generally, we have the following lemma.

As with fence tiling [8], we can systematically construct all possible metatiles with the aid of a directed pseudograph (henceforth referred to as a digraph). As before, the 0 node corresponds to the empty board or the completion of the metatile. The other nodes represent the state of the incomplete metatile. The occupancy of a cell in it is represented by a binary digit: 0 for empty, 1 for filled. We label the node by discarding the leading 1s and trailing zeros and so the label always starts with a 0 and ends with a 1, with $1^{r}$ denoting 1 repeated $r$ times. Each arc represents the addition of a tile and any walk beginning and ending at the 0 node without visiting it in between corresponds to a metatile. With our restricted-overlap tiling, all nodes have an out-degree of 2 as a gap may always be filled by a square or the start of a comb. The destination node is obtained by performing a bitwise OR operation on the bits representing the added tile and the label of the current node, and then discarding the leading 1s. Figure 1 illustrates this for the metatiles involved when tiling with squares and $(l,1,r)$-combs.

The most important property of a metatile is its length. This is obtained by summing the contribution to the length associated with each arc in the walk representing the metatile. The contribution to the length associated with an arc is zero if it corresponds to the addition of a square (except in the case of the trivial $S$ metatile) and for a comb arc equals $q+1-d$ where $d$ is the number of digits in the node label from which the arc emanates except when that node is the 0 node in which case $d=0$. In the digraphs, the contribution to the length associated with each arc is given as a subscript in square brackets if it is not zero. For example, from the digraph in Figure 1b, for tiling with squares and $(l,1,r<l)$-combs we see that the length of a $C^{m}S$ metatile where $m>0$ is $q+1+(m-1)(q-r)=ml+r+1$ as in this case $q=l+r$.

For brevity, we just give results for $B_{n}$ and $B_{n,k}$ as these are easily converted to recursion relations for $S_{n}$ and $S_{n,k}$ and the generating function for $S_{n}$ using Theorem 2 and Lemma 1. As with ordinary (non-overlapping) tiling, the following lemma is the basis for obtaining recursion relations for $B_{n}$ and $B_{n,k}$.

As an example of the application of the above theorem, we consider the case $\mathcal{Q}=\{2\}$. Then $l=r=1$ and $q=2$ and we obtain the recursion relation $B_{n,k}=\delta_{n,0}\delta_{k,0}+B_{n-1,k}+B_{n-2,k-1}+B_{n-4,k-2}$. Using Theorem 2 gives $S_{n,k}=\delta_{n,-2}\delta_{k,0}+S_{n-1,k}+S_{n-2,k-1}+S_{n-4,k-2}$ which is in agreement with the recursion relation first obtained by Konvalina [14]. Note that the metatiles in this case are the square ($S$), a comb with its gap filled by a square ($CS$), and two interlocking combs ($C^{2}$). No overlapping occurs in this case and so it also an ordinary tiling which has been examined extensively [9].

For instances where the largest element of $\mathbb{N}_{q}-\mathcal{Q}$ (the set of allowed differences less than $q$) is $q-r$ and $2r\geq q$ but the other conditions in Theorem 3 do not hold, as the number of possible metatiles is finite (by Lemma 2), it is straightforward to find the length and number of combs in each of them and then use (2) to obtain recursion relations for $B_{n}$ and $B_{n,k}$.

To enable us to tackle some cases where there are an infinite number of possible metatiles, we begin by reviewing some terminology describing features of the digraphs used to construct metatiles [8]. A cycle is a closed walk in which no node or arc is repeated aside from the starting node. We refer to cycles by the arcs they contain. For example, the digraph in Figure 1(a) has 3 cycles: $S_{[1]}$, $C_{[q+1]}S$, and $C_{[q+1]}C_{[q-r]}$. An inner cycle is a cycle that does not include the 0 node. For example, the digraph in Figure 1(b) has a single inner cycle, namely, $C_{[q-r]}$. If a digraph has an inner cycle, there are infinitely many possible metatiles as, once reached, the cycle can be traversed an arbitrary number of times before the walk returns to the 0 node. If all of the inner cycles of a digraph have one node (or more than one node) in common, that node (or any one of those nodes) is said to be the common node. In the case of a digraph with one inner cycle, any of the nodes of the inner cycle can be chosen as the common node. A common circuit is a simple path from the 0 node to the common node followed by a simple path from the common node back to the 0 node. For example, in the digraph in Figure 1(b), the common node is $01^{r}$ and the common circuit is $C_{[q+1]}S$. If a digraph has a common node, members of an infinite family of metatiles can be obtained by traversing the first part of the common circuit from the 0 node to the common node and then traversing the inner cycle(s) an arbitrary number of times (and in any order if there are more than one) before returning to the 0 node via the second part of the common circuit. An outer cycle is a cycle that includes the 0 node but does not include the common node. Thus any metatile which is not a member of an infinite family of metatiles has a symbolic representation derived from an outer cycle. E.g., the only outer cycle in the digraph in Figure 1(b) is $S_{[1]}$.

The following theorem is a restatement of Theorem 5.4 and Identity 5.5 in [8] but with more compact expressions for $B_{n}$ and $B_{n,k}$ and improved proofs. Note that the length of a cycle or circuit is simply the total contributions to the length of the arcs it contains.

The rest of the theorems in this section concern families of $\mathcal{Q}$ whose corresponding digraphs each have a common node. Once the lengths of and the number of combs in each cycle and common circuit have been determined, the recursion relations for $B_{n}$ and $B_{n,k}$ follow immediately from Theorem 4.

It can be seen from (3) that the recursion relation for $B_{n}$ can be obtained from that for $B_{n,k}$ by replacing $B_{n-\nu,k-\kappa}$ and $\delta_{n,\nu}\delta_{k,\kappa}$ by $B_{n-\nu}$ and $\delta_{n,\nu}$, respectively, for any $\nu$ and $\kappa$. For the remaining theorems we therefore give the recursion relation for $B_{n,k}$ and only also show the one for $B_{n}$ if we use the expression for $B_{n}$ elsewhere.

For the more generally applicable theorems that follow, $B_{n}$ and $B_{n,k}$ are given most simply in terms of the elements $p_{i}$ of $\mathbb{N}_{q}-\mathcal{Q}$, the set of allowed differences less than $q$. We order the $p_{i}$ so that $p_{i}<p_{i+1}$ for all $i=1,\ldots,a-1$, where $a=\left\lvert\mathbb{N}_{q}-\mathcal{Q}\right\rvert$, the number of allowed differences less than $q$. Note that if the comb corresponding to $\mathcal{Q}$ has leftmost and rightmost teeth of widths $l$ and $r$, respectively, then $p_{1}=l$ and $p_{a}=q-r$. In digraphs, we let $\sigma_{i}$ (for $i=1,\ldots,a$) denote the bit string corresponding to filling the first $i-1$ empty cells of a comb with squares and discarding the leading 1s. Thus $\sigma_{a}$ is always $01^{r}$. It is also easily seen that the comb arc leaving the $\sigma_{i}$ node is $C_{[p_{i}]}$.

The following corollary was established via graph theory and results concerning bit strings in [13].

We consider the case $\mathcal{Q}=\{1,3,5\}$ as an example for the application of Theorem 5. Then $q=5$, $a=2$, $p_{1}=2$, and $p_{2}=4$. Hence $B_{n,k}=\delta_{n,0}\delta_{k,0}-\delta_{n,2}\delta_{k,1}-\delta_{n,4}\delta_{k,1}+B_{n-1,k}+B_{n-2,k-1}-B_{n-3,k-1}+B_{n-4,k-1}-B_{n-5,k-1}+B_{n-6,k-1}$. Since in this case $c=1+x+x^{3}+x^{5}$, Corollary 1 gives the generating function for $S_{n}$ of $(1+x+x^{3}+x^{5})/(1-x-x^{2}+x^{3}-x^{4}+x^{5}-x^{6})$ as found by Kitaev [13].

The proofs of some of the results that follow (starting with the next lemma which is used in the proof of Theorem 6) require combs where the number of gaps depends on the particular instance of $\mathcal{Q}$. We therefore extend our notation: an $(l,[g],r)$-comb is a comb of length $l+g+r$ whose left and right teeth have widths of $l$ and $r$, respectively.

It is straightforward to verify that the following four classes of $\mathcal{Q}$ satisfy the conditions for Theorem 6 to apply: (i) $\mathcal{Q}=\{2,\ldots,q-r-1,q-r+1,\ldots,q\}$ where $r\geq 1$ and $q\geq\max(2r+1,4)$ (e.g., for $q\leq 7$: $\{2,4\}$, $\{2,3,5\}$, $\{2,4,5\}$, $\{2,3,4,6\}$, $\{2,3,5,6\}$, $\{2,3,4,5,7\}$, $\{2,3,4,6,7\}$, $\{2,3,5,6,7\}$); (ii) $\mathcal{Q}=\{1,\ldots,l-1,l+1,\ldots,q-r-1,q-r+1,\ldots,q\}$ where $r\geq l\geq 2$ and $q\geq 2r+1$ and $2l\neq q-r$ (e.g., for $q\leq 8$: $\{1,3,4,6,7\}$, $\{1,2,4,6,7,8\}$, $\{1,3,4,5,7,8\}$, $\{1,3,4,6,7,8\}$); (iii) $q=2r+1$, $p_{1}=l$, $p_{a}=r+1$, and $l\leq r\leq 2l-2$ (e.g., for $q\leq 9$: $\{1,4,5\}$, $\{1,2,5,6,7\}$, $\{1,2,6,7,8,9\}$, $\{1,2,3,6,7,8,9\}$, $\{1,2,4,6,7,8,9\}$); (iv) $\mathcal{Q}=\{2,4,\ldots,2a,2a+1,\ldots,q\}$ where $a\geq 3$ and $q=4a-4,4a-3$ (e.g., for $q\leq 9$: $\{2,4,6,7,8\}$, $\{2,4,6,7,8,9\}$). These classes cover all cases where the theorem applies for $q\leq 9$.