On a Two-Parameter Family of Generalizations of Pascal’s Triangle
Michael A. Allen
Physics Department
Faculty of Science
Mahidol University
Rama 6 Road
Bangkok 10400
Thailand
<EMAIL_ADDRESS>

###### Abstract

We consider a two-parameter family of triangles whose $(n,k)$-th entry
(counting the initial entry as the $(0,0)$-th entry) is the number of tilings
of $N$-boards (which are linear arrays of $N$ unit square cells for any
nonnegative integer $N$) with unit squares and $(1,m-1;t)$-combs for some
fixed $m=1,2,\dots$ and $t=2,3,\dots$ that use $n$ tiles in total of which $k$
are combs. A $(1,m-1;t)$-comb is a tile composed of $t$ unit square sub-tiles
(referred to as teeth) placed so that each tooth is separated from the next by
a gap of width $m-1$. We show that the entries in the triangle are
coefficients of the product of two consecutive generalized Fibonacci
polynomials each raised to some nonnegative integer power. We also present a
bijection between the tiling of an $(n+(t-1)m)$-board with $k$
$(1,m-1;t)$-combs with the remaining cells filled with squares and the
$k$-subsets of $\\{1,\ldots,n\\}$ such that no two elements of the subset
differ by a multiple of $m$ up to $(t-1)m$. We can therefore give a
combinatorial proof of how the number of such $k$-subsets is related to the
coefficient of a polynomial. We also derive a recursion relation for the
number of closed walks from a particular node on a class of directed
pseudographs and apply it obtain an identity concerning the $m=2$, $t=5$
instance of the family of triangles. Further identities of the triangles are
also established mostly via combinatorial proof.

##  1 Introduction

In a recent paper [2], that we will henceforth refer to as AE22, we considered
two one-parameter families of generalizations of Pascal’s triangle. Regarding
the triangles as lower triangular matrices, the members of both families have
ones in the leftmost column and the repetition of 1 followed by $m-1$ zeros
along the leading diagonal, where $m$ is a positive integer. In the case of
the first family, the rest of the entries are obtained using Pascal’s
recurrence, i.e.,
$\tbinom{n}{k}_{m}=\tbinom{n-1}{k}_{m}+\tbinom{n-1}{k-1}_{m}$, where
$\tbinom{n}{k}_{m}$ is the $(n,k)$-th entry (counting the first entry as being
in row $n=0$ and column $k=0$) of the $m$-th triangle of the family. We showed
that this is equivalent to the triangles being row-reversed
$(1/(1-x^{m}),x/(1-x))$ Riordan arrays. A $(p(x),q(x))$ Riordan array is an
infinite lower triangular matrix whose $(n,k)$-th entry is the coefficient of
$x^{n}$ in the series expansion of $p(x)(q(x))^{k}$ [12, 3]. The row-reversed
version of a Riordan array has the entries up to and including the leading
diagonal in each row placed in reverse order [2].

The main focus of AE22 was on a second family of triangles whose $(n,k)$-th
entry (denoted by $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{m}$) is the number of ways to tile $N$-boards
(which are linear arrays of $N\geq 0$ unit square cells) using $k$
$(1,m-1)$-fences and $n-k$ squares (and thus $n$ tiles in total). A
$(1,m-1)$-fence is a tile composed to two unit-square sub-tiles separated by a
gap of width $m-1$ [4, 5]. The two families of triangles coincide for $m=1,2$
and the $m=1$ case is Pascal’s triangle, i.e.,
$\tbinom{n}{k}_{1}=\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{1}=\tbinom{n}{k}$ and
$\tbinom{n}{k}_{2}=\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2}$ for all $n$ and $k$. We showed that for $j\geq
0$, $k\geq 0$, $m\geq 1$, and $r=0,\ldots,m-1$, the entry
$\langle\begin{smallmatrix}mj+r-k\\\ k\end{smallmatrix}\rangle_{m}$ is the
coefficient of $x^{k}$ in $f_{j}^{m-r}(x)f_{j+1}^{r}(x)$, where in this
instance the Fibonacci polynomial $f_{n}(x)$ is defined by
$f_{n}(x)=f_{n-1}(x)+xf_{n-2}(x)+\delta_{n,0}$, $f_{n<0}(x)=0$, where
$\delta_{i,j}$ is 1 if $i=j$ and zero otherwise. By first identifying a
bijection between the tilings of an $(n+m)$-board with $k$ $(1,m-1)$-fences
and $n+m-2k$ squares and the subsets of $\mathbb{N}_{n}=\\{1,\ldots,n\\}$
containing $k$ elements none of which differ from another element in the
subset by $m$, we showed that the number of such subsets,
$S^{(m)}(n,k)=\langle\begin{smallmatrix}n+m-k\\\
k\end{smallmatrix}\rangle_{m}$. We thus arrived at a combinatorial proof of
the relation between $S^{(m)}(n,k)$ and the coefficient of $x^{k}$ in the
product of nonnegative integer powers of two successive Fibonacci polynomials.

Here we generalize the second family of triangles by considering the analogous
$n$-tile tilings of $N$-boards with $(1,m-1;t)$-combs and squares for positive
integer $m$ and $t=2,3,\ldots$. A $(w,g;t)$-comb contains $t$ sub-tiles of
dimensions $w\times 1$ (referred to as teeth) separated from one another by
gaps of width $g$ [1]. A $(1,m-1;2)$-comb is evidently a $(1,m-1)$-fence and
so the $t=2$ instances of the triangles we introduce here coincide with the
second family of triangles in AE22.

After introducing the two-parameter family of triangles (along with a less
compact version of the triangles which is used in some proofs) in §2, we show
how entries of the triangles are related to some generalized Fibonacci
polynomials in §3. Then in §4 we give a bijection between the tilings of an
$(n+(t-1)m)$-board with $k$ $(1,m-1;t)$-combs and $n+(t-1)m-kt$ squares and
the $k$-subsets of $\mathbb{N}_{n}$ such that no two elements of the subset
differ by any element of the set $\\{m,2m,\ldots,(t-1)m\\}$. This enables us
to relate the number of such subsets to coefficients of products of powers of
two successive generalized Fibonacci polynomials. The remainder of the paper
concerns finding identities satisfied by entries in the triangle. Most of the
identities are obtained via the enumeration of metatiles with a certain length
or number of tiles which can be problematic if the metatiles contain an
arbitrary number of tiles. A metatile is a gapless grouping of tiles that
completely covers a whole number of cells and cannot be split into smaller
metatiles. In most cases, there are infinitely many possible metatiles and
there have been various approaches to the enumeration problem: obtaining the
symbolic representation all the families of metatiles [6], obtaining a
recursion relation for the number of metatiles of a certain length and thus
expressing the number in terms of a known sequence [7], identifying a
bijection between the metatiles and a set of objects whose number is known
[1], and constructing a directed pseudograph (that we refer to as a digraph)
to represent the placing of tiles [5]. We will use the first and last of these
approaches and these are described further in §5. Recursion relations for
numbers of tilings corresponding to a particular class of digraph are derived
in the appendix and these are used to obtain identities for the $m=2$, $t=5$
triangle in §6 where further identities concerning the triangles are also
derived, mostly via combinatorial proof.

##  2 The two-parameter family of triangles

$n$ $\backslash$ $k$ |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 |  1 |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  1 |  0 |  |  |  |  |  |  |  |  |  |  |  |
2 |  1 |  0 |  1 |  |  |  |  |  |  |  |  |  |  |
3 |  1 |  1 |  2 |  0 |  |  |  |  |  |  |  |  |  |
4 |  1 |  2 |  4 |  0 |  1 |  |  |  |  |  |  |  |  |
5 |  1 |  3 |  6 |  3 |  3 |  0 |  |  |  |  |  |  |  |
6 |  1 |  4 |  9 |  8 |  9 |  0 |  1 |  |  |  |  |  |  |
7 |  1 |  5 |  13 |  17 |  18 |  6 |  4 |  0 |  |  |  |  |  |
8 |  1 |  6 |  18 |  30 |  36 |  20 |  16 |  0 |  1 |  |  |  |  |
9 |  1 |  7 |  24 |  48 |  66 |  55 |  40 |  10 |  5 |  0 |  |  |  |
10 |  1 |  8 |  31 |  72 |  114 |  120 |  100 |  40 |  25 |  0 |  1 |  |  |
11 |  1 |  9 |  39 |  103 |  186 |  234 |  221 |  135 |  75 |  15 |  6 |  0 |  |
12 |  1 |  10 |  48 |  142 |  289 |  420 |  456 |  350 |  225 |  70 |  36 |  0 |  1 |
13 |  1 |  11 |  58 |  190 |  431 |  709 |  876 |  805 |  581 |  280 |  126 |  21 |  7 |  0
Figure 1: The start of a Pascal-like triangle (A354665 in the OEIS [13]) whose
$(n,k)$-th entry, $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2,3}$, is the number of $n$-tile tilings using $k$
$(1,1;3)$-combs (and $n-k$ squares). Entries in bold font (and those in bold
font in Figs. 2–4) are covered by identities in §6.

For $m=1,2,\ldots$ and $t=2,3,\ldots$, let $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{m,t}$ denote the number of $n$-tile tilings of
$N$-boards that use $k$ $(1,m-1;t)$-combs (and $n-k$ squares). We choose that
$\langle\begin{smallmatrix}0\\\ 0\end{smallmatrix}\rangle_{m,t}=1$ and that
$\langle\begin{smallmatrix}n\\\
k<0\end{smallmatrix}\rangle_{m,t}=\langle\begin{smallmatrix}n\\\
k>n\end{smallmatrix}\rangle_{m,t}=0$. As a $(1,0;t)$-comb is just a $t$-omino
and the number of $n$-tile tilings using $n$ $t$-ominoes and $n-k$ squares is
simply $\tbinom{n}{k}$ for any $t$, we have $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{1,t\geq 2}=\tbinom{n}{k}$ which is Pascal’s
triangle (A007318). The triangles corresponding to $m=2,3,4,5$ with $t=2$ are
A059259, A350110, A350111, and A350112, respectively [2]. We show examples of
the starts of triangles for combs with at least 3 teeth in Figs. 1–4.

$n$ $\backslash$ $k$ |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 |  1 |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  1 |  0 |  |  |  |  |  |  |  |  |  |  |  |
2 |  1 |  0 |  1 |  |  |  |  |  |  |  |  |  |  |
3 |  1 |  0 |  2 |  0 |  |  |  |  |  |  |  |  |  |
4 |  1 |  1 |  4 |  0 |  1 |  |  |  |  |  |  |  |  |
5 |  1 |  2 |  6 |  0 |  3 |  0 |  |  |  |  |  |  |  |
6 |  1 |  3 |  9 |  4 |  9 |  0 |  1 |  |  |  |  |  |  |
7 |  1 |  4 |  12 |  10 |  18 |  0 |  4 |  0 |  |  |  |  |  |
8 |  1 |  5 |  16 |  21 |  36 |  10 |  16 |  0 |  1 |  |  |  |  |
9 |  1 |  6 |  21 |  36 |  60 |  30 |  40 |  0 |  5 |  0 |  |  |  |
10 |  1 |  7 |  27 |  57 |  100 |  81 |  100 |  20 |  25 |  0 |  1 |  |  |
11 |  1 |  8 |  34 |  84 |  158 |  168 |  200 |  70 |  75 |  0 |  6 |  0 |  |
12 |  1 |  9 |  42 |  118 |  243 |  322 |  400 |  231 |  225 |  35 |  36 |  0 |  1 |
13 |  1 |  10 |  51 |  160 |  361 |  560 |  736 |  560 |  525 |  140 |  126 |  0 |  7 |  0
Figure 2: The start of a Pascal-like triangle (A354666) with entries $\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,4}$. $n$ $\backslash$ $k$ |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 |  1 |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  1 |  0 |  |  |  |  |  |  |  |  |  |  |  |
2 |  1 |  0 |  1 |  |  |  |  |  |  |  |  |  |  |
3 |  1 |  0 |  2 |  0 |  |  |  |  |  |  |  |  |  |
4 |  1 |  0 |  4 |  0 |  1 |  |  |  |  |  |  |  |  |
5 |  1 |  1 |  6 |  0 |  3 |  0 |  |  |  |  |  |  |  |
6 |  1 |  2 |  9 |  0 |  9 |  0 |  1 |  |  |  |  |  |  |
7 |  1 |  3 |  12 |  5 |  18 |  0 |  4 |  0 |  |  |  |  |  |
8 |  1 |  4 |  16 |  12 |  36 |  0 |  16 |  0 |  1 |  |  |  |  |
9 |  1 |  5 |  20 |  25 |  60 |  15 |  40 |  0 |  5 |  0 |  |  |  |
10 |  1 |  6 |  25 |  42 |  100 |  42 |  100 |  0 |  25 |  0 |  1 |  |  |
11 |  1 |  7 |  31 |  66 |  150 |  112 |  200 |  35 |  75 |  0 |  6 |  0 |  |
12 |  1 |  8 |  38 |  96 |  225 |  224 |  400 |  112 |  225 |  0 |  36 |  0 |  1 |
13 |  1 |  9 |  46 |  134 |  325 |  424 |  700 |  364 |  525 |  70 |  126 |  0 |  7 |  0
Figure 3: The start of a Pascal-like triangle (A354667) with entries $\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,5}$. $n$ $\backslash$ $k$ |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 |  1 |  |  |  |  |  |  |  |  |  |  |  |  |
1 |  1 |  0 |  |  |  |  |  |  |  |  |  |  |  |
2 |  1 |  0 |  0 |  |  |  |  |  |  |  |  |  |  |
3 |  1 |  0 |  0 |  1 |  |  |  |  |  |  |  |  |  |
4 |  1 |  0 |  1 |  2 |  0 |  |  |  |  |  |  |  |  |
5 |  1 |  1 |  3 |  4 |  0 |  0 |  |  |  |  |  |  |  |
6 |  1 |  2 |  5 |  8 |  0 |  0 |  1 |  |  |  |  |  |  |
7 |  1 |  3 |  8 |  12 |  0 |  3 |  3 |  0 |  |  |  |  |  |
8 |  1 |  4 |  12 |  18 |  9 |  12 |  9 |  0 |  0 |  |  |  |  |
9 |  1 |  5 |  16 |  27 |  25 |  29 |  27 |  0 |  0 |  1 |  |  |  |
10 |  1 |  6 |  21 |  42 |  51 |  66 |  54 |  0 |  6 |  4 |  0 |  |  |
11 |  1 |  7 |  27 |  62 |  95 |  135 |  108 |  36 |  30 |  16 |  0 |  0 |  |
12 |  1 |  8 |  34 |  88 |  160 |  234 |  216 |  126 |  95 |  64 |  0 |  0 |  1 |
13 |  1 |  9 |  42 |  122 |  252 |  396 |  432 |  321 |  280 |  160 |  0 |  10 |  5 |  0
Figure 4: The start of a Pascal-like triangle (A354668) with entries
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{3,3}$.

We can also create a triangle of $[\begin{smallmatrix}n\\\
k\end{smallmatrix}]_{m,t}$ where this denotes the number of tilings of an
$n$-board that use $k$ $(1,m-1;t)$-combs (and therefore $n-kt$ squares) again
with $[\begin{smallmatrix}0\\\ 0\end{smallmatrix}]_{m,t}=1$. The two triangles
are related via the following identity.

######  Identity 1.

For $m\geq 1$, $t\geq 2$, and $n\geq k\geq 0$,

$\begin{bmatrix}n\\\
k\end{bmatrix}_{m,t}=\left\langle\begin{matrix}n-(t-1)k\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}.$

###### Proof.

If a tiling contains $n-(t-1)k$ tiles of which $k$ are $(1,m-1;t)$-combs (and
so $n-kt$ are squares), the total length is $n-kt+kt=n$. ∎

We will refer to the ray of entries given by $\langle\begin{smallmatrix}n-\mu
k\\\ k\end{smallmatrix}\rangle_{m,t}$ for $k=0,\ldots,\lfloor
n/(\mu+1)\rfloor$ as the $n$-th $(1,\mu)$-antidiagonal. A $(1,1)$-antidiagonal
is therefore what is normally referred to simply as an antidiagonal. As a
consequence of Identity 1, the $(1,t-1)$-antidiagonals of the
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{m,t}$ triangle are
the rows of the $[\begin{smallmatrix}n\\\ k\end{smallmatrix}]_{m,t}$ triangle.
In the rest of the paper we therefore only give identities for the
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{m,t}$ triangle as
it is more ‘compact’ in the sense that its rows contain fewer trailing zeros.
However, as in AE22, some of the identities are more straightforward to prove
by considering the tiling of an $n$-board, in which case we need to consider
$[\begin{smallmatrix}n\\\ k\end{smallmatrix}]_{m,t}$. The following bijection
(which is established in the proof of Theorem 2.1 in [1]) will be used in such
proofs.

######  Lemma 2.

For $t\geq 2$, $j\geq 0$, and $r=0,\ldots,m$, where $m\geq 1$, there is a
bijection between the tilings of an $(mj+r)$-board using $k$ $(1,m-1;t)$-combs
and $mj+r-kt$ squares and the tilings of an ordered $m$-tuple of $r$
$(j+1)$-boards followed by $m-r$ $j$-boards using $k$ $t$-ominoes and
$mj+r-kt$ squares.

##  3 Relation of the triangles to polynomials

For $t\geq 2$ we define a $(1,t)$-bonacci polynomial as follows:

$f^{(t)}_{n}(x)=f^{(t)}_{n-1}(x)+xf^{(t)}_{n-t}(x)+\delta_{n,0},\quad
f^{(t)}_{n<0}(x)=0.$ (1)

The $(1,2)$-bonacci polynomials $f^{(2)}_{n}(x)$ are the Fibonacci polynomials
used in AE22. We refer to the sequence defined by

$f^{(t)}_{n}=f^{(t)}_{n-1}+f^{(t)}_{n-t}+\delta_{n,0},\quad f^{(t)}_{n<0}=0,$
(2)

for $t\geq 2$ as the $(1,t)$-bonacci numbers. The $t=2,\ldots,8$ cases are,
respectively, the Fibonacci numbers (A000045), the Narayana’s cows sequence
(A000930) and sequences A003269, A003520, A005708, A005709, and A005710 in the
OEIS.

######  Lemma 3.

The sum of the coefficients of $f^{(t)}_{n}(x)$ is
$f^{(t)}_{n}(1)=f^{(t)}_{n}$.

###### Proof.

The sum of the coefficients of $f^{(t)}_{n}(x)$ can be expressed as
$f^{(t)}_{n}(1)$. Putting $x=1$ into (1) gives (2) with $f^{(t)}_{n}$ replaced
by $f^{(t)}_{n}(1)$. ∎

In the next lemma and theorem (which are generalizations of Lemma 13 and
Theorem 14 in AE22) we employ the coefficient operator $[x^{k}]$ which denotes
the coefficient of $x^{k}$ in the term it precedes.

######  Lemma 4.

Let $f(t,n,k)=[x^{k}]f^{(t)}_{n}(x)$ and let $b(t,n,k)$ be the number of
tilings of an $n$-board with squares and $t$-ominoes that use exactly $k$
$t$-ominoes. Then $f(t,n,k)=b(t,n,k)$ for all $n$ and $k$.

###### Proof.

This follows from Theorem 10 of AE22. The metatiles are the square and
$t$-omino. ∎

######  Theorem 5.

For $j\geq 0$, $k\geq 0$, $m\geq 1$, $t\geq 2$, and $r=0,\ldots,m-1$,

$\left\langle\begin{matrix}mj+r-(t-1)k\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}=[x^{k}]\bigl{(}f^{(t)}_{j}(x)\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+1}(x)\bigr{)}^{r}.$
(3)

###### Proof.

From Identity 1, $\langle\begin{smallmatrix}mj+r-(t-1)k\\\
k\end{smallmatrix}\rangle_{m,t}=[\begin{smallmatrix}mj+r\\\
k\end{smallmatrix}]_{m,t}$. From Lemma 2, $[\begin{smallmatrix}mj+r\\\
k\end{smallmatrix}]_{m,t}$ equals the number of ways to tile an ordered
$m$-tuple of $r$ $(j+1)$-boards followed by $m-r$ $j$-boards using $k$
$t$-ominoes (and $mj+r-kt$ squares). The number of such tilings of the
$m$-tuple of boards is

$\sum_{\begin{subarray}{c}k_{1}\geq 0,\,k_{2}\geq 0,\,\ldots,\,k_{m}\geq 0,\\\
k_{1}+k_{2}+\cdots+k_{m}=k\end{subarray}}\Biggl{(}\prod_{i=1}^{r}b(t,j+1,k_{i})\Biggr{)}\Biggl{(}\prod_{i=r+1}^{m}b(t,j,k_{i})\Biggr{)}$

in which the first product is omitted when $r=0$. The coefficient of $x^{k}$
in $\bigl{(}f^{(t)}_{j+1}(x)\bigr{)}^{r}\bigl{(}f^{(t)}_{j}(x)\bigr{)}^{m-r}$
is

$\displaystyle[x^{k}]\Biggl{(}\prod_{i=1}^{r}\sum_{k_{i}=0}^{\lfloor(j+1)/t\rfloor}f(t,j+1,k_{i})x^{k_{i}}\Biggr{)}\Biggl{(}\prod_{i=r+1}^{m}\sum_{k_{i}=0}^{\lfloor
j/t\rfloor}f(t,j,k_{i})x^{k_{i}}\Biggr{)}$
$\displaystyle\qquad=[x^{k}]\sum_{k_{1}\geq 0,k_{2}\geq 0,\ldots,k_{m}\geq
0}\Biggl{(}\prod_{i=1}^{r}f(t,j+1,k_{i})\Biggr{)}\Biggl{(}\prod_{i=r+1}^{m}f(t,j,k_{i})\Biggr{)}x^{k_{1}+k_{2}+\cdots+k_{m}}$
$\displaystyle\qquad=\sum_{\begin{subarray}{c}k_{1}\geq 0,\,k_{2}\geq
0,\,\ldots,\,k_{m}\geq 0,\\\
k_{1}+k_{2}+\cdots+k_{m}=k\end{subarray}}\Biggl{(}\prod_{i=1}^{r}f(t,j+1,k_{i})\Biggr{)}\Biggl{(}\prod_{i=1}^{r}f(t,j,k_{i})\Biggr{)}.$

The result then follows from Lemma 4. ∎

The following identity gives the sums of the $(1,t-1)$-antidiagonals of the
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{m,t}$ triangle.

######  Identity 6.

For $t\geq 2$, $j\geq 0$, $m\geq 1$, and $r=0,\ldots,m-1$,

$\sum_{k=0}^{\lfloor(mj+r)/t\rfloor}\left\langle\begin{matrix}mj+r-(t-1)k\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\bigl{(}f^{(t)}_{j}\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+1}\bigr{)}^{r}.$

###### Proof.

Summing (3) over all permitted $k$ gives the sum of all coefficients of

$F(x)=\bigl{(}f^{(t)}_{j}(x)\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+1}(x)\bigr{)}^{r}$

which is $F(1)$ and equals
$\bigl{(}f^{(t)}_{j}\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+1}\bigr{)}^{r}$ by Lemma
3. ∎

##  4 Relation of the triangles to restricted combinations

We now look at $S^{(m,t)}(n,k)$, the number of subsets of $\mathbb{N}_{n}$ of
size $k$ such that the difference of any two elements of the subset does not
equal any element in the set $\mathcal{Q}=\\{m,2m,\ldots,(t-1)m\\}$. For
example, $S^{(2,3)}(5,0)=1$, $S^{(2,3)}(5,1)=5$, $S^{(2,3)}(5,2)=6$, and
$S^{(2,3)}(5,k>2)=0$ since the possible subsets of $\mathbb{N}_{5}$ such that
no two elements in the subset differ by 2 or 4 are $\\{\\}$, $\\{1\\}$,
$\\{2\\}$, $\\{3\\}$, $\\{4\\}$, $\\{5\\}$, $\\{1,2\\}$, $\\{2,3\\}$,
$\\{3,4\\}$, $\\{4,5\\}$, $\\{1,4\\}$, and $\\{2,5\\}$. There is a formula for
$S^{(m,t)}(n,k)$ in terms of sums of products of binomial coefficients [11].
Here we will show that
$S^{(m,t)}(n,k)=\langle\begin{smallmatrix}n+(t-1)(m-k)\\\
k\end{smallmatrix}\rangle_{m,t}$ and hence obtain an expression for the number
of subsets in terms of coefficients of products of $(1,t)$-bonacci polynomials
which is a generalization of earlier results [10, 2]. We first establish the
following bijection.

######  Lemma 7.

For $m,n\geq 1$, $t\geq 2$, and $k\geq 0$, there is a bijection between the
$k$-subsets of $\mathbb{N}_{n}$ such that all pairs of elements taken from a
subset do not differ by an element from the set
$\mathcal{Q}=\\{m,2m,\ldots,(t-1)m\\}$, and the tilings of an
$(n+(t-1)m)$-board with $k$ $(1,m-1;t)$-combs and $n+(t-1)m-kt$ squares.

###### Proof.

We label the cells of the $(n+(t-1)m)$-board from 1 to $n+(t-1)m$. If a
$k$-subset contains element $i$ then we place a comb so that its left tooth
occupies cell $i$. Notice that if $i=n$ then the rightmost tooth occupies the
final cell on the board. After placing combs corresponding to each element of
the subset, the rest of the board is filled with squares of which there must
be $n+(t-1)m-kt$. Conversely, the tiling of any $(n+(t-1)m)$-board with $k$
combs corresponds to a $k$-subset where no two elements differ by an element
of $\mathcal{Q}$ since the remaining teeth of a comb whose leftmost tooth
occupies cell $i$ lie on cells $i+m,i+2m,\ldots,i+(t-1)m$ which means none of
these cells can be occupied by the leftmost tooth of another comb. ∎

######  Corollary 8.

For $m,n\geq 1$, $t\geq 2$, and $k\geq 0$,
$S^{(m,t)}(n,k)=\langle\begin{smallmatrix}n+(t-1)(m-k)\\\
k\end{smallmatrix}\rangle_{m,t}$.

###### Proof.

From Lemma 7, $S^{(m,t)}(n,k)=[\begin{smallmatrix}n+(t-1)m\\\
k\end{smallmatrix}]_{m,t}$. Identity 1 then gives the result. ∎

######  Corollary 9.

For $m,n\geq 1$, $t\geq 2$, the sum of the elements in the $n$-th
$(1,t-1)$-antidiagonal of $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{m,t}$ is the number of subsets of
$\mathbb{N}_{n-(t-1)m}$ chosen so that no two elements of the subsets differ
by any member of the set $\\{m,\ldots,(t-1)m\\}$.

###### Proof.

The elements in the $(1,t-1)$-antidiagonal are, for $k\geq 0$,
$\langle\begin{smallmatrix}n-(t-1)k\\\
k\end{smallmatrix}\rangle_{m,t}=S^{(m,t)}(n-(t-1)m,k)$ by Corollary 8. Summing
over all $k$ then gives the result. ∎

The next two corollaries follow from Theorem 5 and Identity 6, respectively.

######  Corollary 10.

For $j,k\geq 0$, $m\geq 1$, $t\geq 2$, and $r=0,\ldots,m-1$,

$S^{(m,t)}(mj+r,k)=[x^{k}]\bigl{(}f^{(t)}_{j+t-1}(x)\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+t}(x)\bigr{)}^{r}.$

######  Corollary 11.

For $j\geq 0$, $m\geq 1$, $t\geq 2$, and $r=0,\ldots,m-1$, the number of
subsets of $\mathbb{N}_{mj+r}$ each of which lack pairs of elements that
differ by a multiple of $m$ up to $(t-1)m$ is
$\bigl{(}f^{(t)}_{j+t-1}\bigr{)}^{m-r}\bigl{(}f^{(t)}_{j+t}\bigr{)}^{r}$.

##  5 Metatiles and digraphs

The simplest metatiles when tiling with squares ($S$) and $(1,m-1;t)$-combs
($C$) are the free square ($S$), what we will refer to as an $m$-comb
($C^{m}$) which is $m$ interlocking combs with no gaps, and the filled comb
($CS^{(m-1)(t-1)}$) which is a comb with all the gaps filled with squares. The
$m=2$, $t=3$ instances of these are the first three metatiles depicted in Fig.
5(a).

Figure 5: Metatiles when tiling with squares and $(1,1;3)$-combs ($m=2$,
$t=3$). (a) A 31-board tiled with all the metatiles containing less than 6
tiles. Shaded (white) cells are occupied by squares (combs). Bold lines
indicate which teeth belong to the same comb. Dashed lines show boundaries
between metatiles. The symbolic representation is above each metatile. (b) The
digraph for generating metatiles.

When $m=1$, the only metatiles are the two individual tiles themselves: a
square and a comb, which, as the gaps are of zero width, is just a $t$-omino.
When $m>1$, the only case when there is a finite number of metatiles is when
$t=2$ [9]. There are two cases when there is a single infinite sequence of
metatiles: the $(m,t)=(3,2)$ case, which was dealt with in AE22, and when
$m=2$ and $t=3$. In the latter case, the metatiles are $S$, $C^{2}$, and
$CSC^{j}S$ for $j\geq 0$, as illustrated in Fig. 5(a). This infinite sequence
of metatiles is analogous to that found for the $(m,t)=(3,2)$ case [2, §6]:
$CS$ has a single remaining unit-width slot which can be filled either with an
$S$, thus completing the metatile, or with the left tooth of a $C$ (to give
$CSC$) which again results in a slot of unit width.

For a particular choice of types of tiles, a systematic way to generate all
metatiles and, in the simpler cases, obtain finite-order recursion relations
for the number of tilings is via a directed pseudograph (henceforth referred
to as a digraph) in which each arc represents the addition of a tile and each
node represents the current state of the yet-to-be-completed metatile [5, 8].
Any such digraph contains a 0 node which represents the empty board or the
completed metatile. The remaining nodes are named using binary strings: the
$i$-th digit of the string is 0 (1) if the $i$-th cell, starting at the first
unoccupied cell of the incomplete metatile and ending at its last occupied
cell, is empty (filled). Thus all nodes (except the 0 node) start with 0 and
end with 1\. There is a bijection between each possible metatile and each path
on the digraph which starts and finishes at the 0 node without visiting it in
between. To obtain the symbolic representation of the metatile, one simply
reads off the names of the arcs along the path and then simplifies the
resulting expression by, for example, replacing $CC$ by $C^{2}$. The digraph
for generating metatiles when tiling with squares and $(1,1;3)$-combs is shown
in Fig. 5(b).

##  6 Further identities

We start by deriving identities that apply to all the triangles and later on
obtain recursion relations for some particular instances of the triangles
after constructing the corresponding metatile-generating digraphs. The
following three identities arise from considering the simplest types of
$n$-tile tilings.

######  Identity 12.

For $n\geq 0$, $m\geq 1$, and $t\geq 2$, $\langle\begin{smallmatrix}n\\\
0\end{smallmatrix}\rangle_{m,t}=1$.

###### Proof.

There is only one way to create an $n$-tile tiling without using any combs,
namely, the all-square tiling. ∎

######  Identity 13.

For $n\geq 0$, $m\geq 1$, and $t\geq 2$, $\langle\begin{smallmatrix}n\\\
n\end{smallmatrix}\rangle_{m,t}=\delta_{n\bmod m,0}$.

###### Proof.

The only way to tile without squares is the all $m$-comb tiling which can only
occur if the number of tiles is a multiple of $m$. ∎

######  Identity 14.

For $n,m\geq 1$ and $t\geq 2$,

$\left\langle\begin{matrix}n\\\
1\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\begin{cases}0,&\text{if
$n<(m-1)(t-1)+1$};\\\ n-(m-1)(t-1),&\text{otherwise}.\end{cases}$

###### Proof.

Any $n$-tile tiling using exactly one $(1,m-1;t)$-comb must have a filled comb
which itself contains $(m-1)(t-1)+1$ tiles. Thus there can be no $n$-tile
tilings using 1 comb that use less than this number of tiles. If
$n\geq(m-1)(t-1)+1$, the tiling consists of a filled comb and $n-(m-1)(t-1)-1$
free squares which gives a total of $n-(m-1)(t-1)$ metatile positions in which
the filled comb can be placed. ∎

The pattern of zeros seen in the triangles is a result of the following
identity.

######  Identity 15.

For $j\geq 1$, $m,t\geq 2$, $p=1,\ldots,m-1$, and $r=1-(t-2)p,\ldots,p$,

$\left\langle\begin{matrix}mj-r\\\
mj-p\end{matrix}\right\rangle_{\\!\\!\\!m,t}=0.$

###### Proof.

We first derive an expression for $K$, the maximum number of combs that can be
used in the tiling of an $(mJ+R)$-board where $R=0,\ldots,m-1$. From Lemma 2,
$K$ is also the maximum number of $t$-ominoes that can be used in the tiling
of $R$ $(J+1)$-boards and $m-R$ $J$-boards. Then it is straightforward to show
that

$K=\begin{cases}\displaystyle\frac{m\bigl{(}J-(J\bmod t)\bigr{)}}{t},&\text{if
$J\bmod t<t-1$};\\\ \displaystyle\frac{m(J-t+1)}{t}+R,&\text{if $J\bmod
t=t-1$}.\end{cases}$ (4)

From Identity 1,

$\left\langle\begin{matrix}mj-r\\\
mj-p\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\begin{bmatrix}tmj-r-(t-1)p\\\
mj-p\end{bmatrix}_{m,t}.$

Writing $tmj-r-(t-1)p$ in the form $mJ+R$, if $J=tj-s$ where $s=1,\ldots,t$
then $R=sm-r-(t-1)p$. The condition that $0\leq R<m$ gives
$(s-1)m<r+(t-1)p\leq sm$. This condition is compatible with the minimum and
maximum values $r+(t-1)p$ can take which are, respectively, 2 and $tm$. From
(4) we find for $s>1$ that $K=m(j-1)$ which is always less than $mj-p$. When
$s=1$, $K=mj-p-r-(t-2)p$. Since $r+(t-2)p\geq 1$ we have $K<mj-p$ in this case
as well. ∎

The following identity explains the entries that appear at the vertical
boundaries of the nonzero parts of the triangles and start with rising powers
of ascending positive integers. Identities 16 and 17 reduce to Identity 24 of
AE22 when $t=2$.

######  Identity 16.

For $j,m\geq 1$, $t\geq 2$, $s=0,\ldots,t-2$, and $r=0,\ldots,m$,

$\displaystyle\left\langle\begin{matrix}m(j+s-1)+r\\\
m(j-1)\end{matrix}\right\rangle_{\\!\\!\\!m,t}$
$\displaystyle=\binom{j+s-1}{s}^{m-r}\binom{j+s}{s+1}^{r}$
$\displaystyle=\begin{cases}j^{r},&\text{if $s=0$};\\\
\biggl{(}\dfrac{j(j+1)\cdots(j+s-1)}{s!}\biggr{)}^{m}\biggl{(}\dfrac{j+s}{s+1}\biggr{)}^{r},&\text{if
$s>0$}.\end{cases}$

###### Proof.

From Identity 1,

$\left\langle\begin{matrix}m(j+s-1)+r\\\
m(j-1)\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\begin{bmatrix}m(t(j-1)+s)+r\\\
m(j-1)\end{bmatrix}_{m,t}.$

By Lemma 2, this is the number of ways to tile $m-r$ boards of length
$t(j-1)+s$ and $r$ boards of length $t(j-1)+s+1$ with $m(j-1)$ $t$-ominoes
(and $sm+r$ squares). As $s+1<t$, each of the $m$ boards always contains
exactly $j-1$ $t$-ominoes. A board of length $t(j-1)+s$ has $s$ squares and so
there are $j+s-1$ metatile positions in which to put the squares (the rest
being filled by $t$-ominoes) and thus $\tbinom{j+s-1}{s}$ ways to tile it.
Likewise, a board of length $t(j-1)+s+1$ has $j+s$ metatile positions and so
there are $\tbinom{j+s}{s+1}$ ways to tile it. The result follows from the
numbers of each type of board. ∎

The next identity explains the rising powers of integers on non-vertical rays
of entries at the boundaries of the nonzero parts of the triangles.

######  Identity 17.

For $m,j\geq 1$, $t\geq 2$, and $p=0,\ldots,m$,

$\left\langle\begin{matrix}mj+(t-2)p\\\
mj-p\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\binom{j+t-2}{t-1}^{p}.$

###### Proof.

From Identity 1 we have

$\left\langle\begin{matrix}mj+(t-2)p\\\
mj-p\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\begin{bmatrix}tmj-p\\\
mj-p\end{bmatrix}_{m,t}=\begin{bmatrix}m(jt-1)+m-p\\\
(m-p)j+p(j-1)\end{bmatrix}_{m,t},$

which is also the number of ways to tile $m-p$ $jt$-boards and $p$ boards of
length $jt-1$ using $(m-p)j+p(j-1)$ $t$-ominoes and $(t-1)p$ squares. The
$jt$-boards are completely filled by $j$ $t$-ominoes and the $p$
$(jt-1)$-boards each have $j-1$ $t$-ominoes and $t-1$ squares. As on these $p$
shorter boards there are $j+t-2$ tiles in total, there are
$\tbinom{j+t-2}{t-1}$ ways to tile each of them which leads to a total of
$\tbinom{j+t-2}{t-1}^{p}$ tilings for the set of boards. ∎

The following two identities are generalizations of Identities 25 and 26 in
AE22.

######  Identity 18.

For $j,m\geq 1$ and $t\geq 2$,

$\left\langle\begin{matrix}mj+t-1\\\
mj-1\end{matrix}\right\rangle_{\\!\\!\\!m,t}=m\binom{j+t-1}{t}.$

###### Proof.

From Identity 1, $\langle\begin{smallmatrix}mj+t-1\\\
mj-1\end{smallmatrix}\rangle_{m,t}=[\begin{smallmatrix}tmj\\\
mj-1\end{smallmatrix}]_{m,t}$, which, from Lemma 2, is the number of ways to
tile an $m$-tuple of $jt$-boards with $mj-1$ $t$-ominoes and $t$ squares. As
the length of each board is a multiple of $t$, all the squares must lie on the
same board. On such a board there are $j-1$ $t$-ominoes and $t$ squares making
$j+t-1$ tiles in total. Hence there are $\tbinom{j+t-1}{t}$ possible ways to
tile it. As there are $m$ possible boards on which to place all the squares,
the result follows. ∎

######  Identity 19.

For $t\geq 2$ and $m,j\geq 1$ provided $mj\geq 2$,

$\left\langle\begin{matrix}mj+2(t-1)\\\
mj-2\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\begin{cases}\displaystyle\binom{m}{2},&\text{if
$j=1,m>1$};\\\ \displaystyle
m\binom{j+2(t-1)}{2t}+\binom{m}{2}\binom{j+t-1}{t}^{2},&\text{if $m,j>1$},\\\
\displaystyle\binom{j+2(t-1)}{2t},&\text{if $m=1,j>1$}.\\\ \end{cases}$

###### Proof.

From Identity 1, $\langle\begin{smallmatrix}mj+2(t-1)\\\
mj-2\end{smallmatrix}\rangle_{m,t}=[\begin{smallmatrix}tmj\\\
mj-2\end{smallmatrix}]_{m,t}$, which, from Lemma 2, is the number of ways to
tile an $m$-tuple of $jt$-boards with $mj-2$ $t$-ominoes and $2t$ squares. If
$j>1$, all $2t$ squares can be on the same $jt$-board which, with the $j-2$
$t$-ominoes on that board, makes $j-2+2t$ tiles in total and hence
$\tbinom{j+2(t-1)}{2t}$ tilings of it. With $m$ boards to choose from, this
gives the first term on the right-hand sides of the identity when $j>1$.
Otherwise, if $m>1$, two of the boards have $t$ squares each. There are
$\tbinom{j+t-1}{t}$ ways to tile each of those boards and $\tbinom{m}{2}$ ways
to choose them. ∎

The following identity is a generalization of the previous two.

######  Identity 20.

For $s\geq 1$, $t\geq 2$, and $m,j\geq 1$ provided $mj\geq s$,

$\left\langle\begin{matrix}mj+s(t-1)\\\
mj-s\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\sum_{\begin{subarray}{c}r_{i}\geq
1;\\\
r_{1}+\cdots+r_{p}=s\end{subarray}}\\!\\!\\!\binom{m}{p}\prod_{i=1}^{p}\binom{j+r_{i}(t-1)}{r_{i}t},$

where the sum is over compositions of $s$, $p$ is the number of parts of the
composition, and $\tbinom{a}{b}$ is understood to equal zero if $a<b$.

###### Proof.

From Identity 1, $\langle\begin{smallmatrix}mj+s(t-1)\\\
mj-s\end{smallmatrix}\rangle_{m,t}=[\begin{smallmatrix}tmj\\\
mj-s\end{smallmatrix}]_{m,t}$, which, from Lemma 2, is the number of ways to
tile an $m$-tuple of $jt$-boards with $mj-s$ $t$-ominoes and $st$ squares. We
partition the squares into $p$ parts of sizes $r_{i}t$ where
$r_{i}\in\mathbb{Z}^{+}$ such that $r_{1}+\cdots+r_{p}=s$. A $jt$-board
containing $r_{i}t$ squares has $j-r_{i}$ $t$-ominoes and thus
$j-r_{i}+r_{i}t$ tiles in total and so $\tbinom{j+r_{i}(t-1)}{r_{i}t}$
possible ways to tile it. There are $\binom{m}{p}$ ways to choose which of the
$m$ boards have any squares. ∎

In order to truly deserve to be called a Pascal-like triangle, a triangle
ought to have a portion where Pascal’s recurrence is obeyed. We now show that
this is the case for our triangles by using a result from a study on
restricted combinations [11] to extend and prove Conjecture 30 of AE22.

######  Theorem 21.

For integers $k\geq 0$, $m\geq 1$, $t\geq 2$, and $n>(m-1)(t-1)k$,

$\left\langle\begin{matrix}n\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\left\langle\begin{matrix}n-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}+\left\langle\begin{matrix}n-1\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!m,t}.$ (5)

###### Proof.

The result holds for $k=0$ since $\langle\begin{smallmatrix}n\geq 0\\\
1\end{smallmatrix}\rangle_{m,t}=1$ by Identity 12 and
$\langle\begin{smallmatrix}n<0\\\
k\end{smallmatrix}\rangle_{m,t}=\langle\begin{smallmatrix}n\\\
k<0\end{smallmatrix}\rangle_{m,t}=0$ by definition. Mansour and Sun give the
result in Theorem 3.5 of their paper [11], when rewritten in our own notation,
that for any integers $m,k\geq 1$, and $t\geq 2$,

$S^{(m,t)}(N,k)=S^{(m,t)}(N-1,k)+S^{(m,t)}(N-t,k-1),$ (6)

provided that $N\geq m(t-1)(k-1)$. However, the condition for this relation
between numbers of subsets to hold should read $N>m(t-1)(k-1)$ (personal
communication with Mansour). By Corollary 8, $n=N+(t-1)(m-k)$ and we can
rewrite (6) as

$\left\langle\begin{matrix}N+(t-1)(m-k)\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}=\left\langle\begin{matrix}N+(t-1)(m-k)-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!m,t}+\left\langle\begin{matrix}N+(t-1)(m-k+1)-t\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!m,t}$

which reduces to (5). The corrected condition becomes
$n-(t-1)(m-k)>m(t-1)(k-1)$ which gives the condition in our theorem. ∎

We now turn to obtaining recursion relations for particular instances of the
triangles. For all but the last triangle we consider, we require the following
theorem which extends a result proved elsewhere for tilings of an $n$-board
when the digraph has a common node [5, Theorem 5.4 and Identity 5.5] to also
include $n$-tile tilings of boards.

######  Theorem 22.

For a digraph possessing a common node, let $l_{\mathrm{o}i}$ be the length of
the $i$-th outer cycle ($i=1,\ldots,N_{\rm o}$), let $L_{r}$ be the length of
the $r$-th inner cycle ($r=1,\ldots,N$) and let $K_{r}$ be the number of combs
it contains, and let $l_{\mathrm{c}i}$ be the length of the $i$-th common
circuit ($i=1,\ldots,N_{\rm c}$) and let $k_{\mathrm{c}i}$ be the number of
combs it contains. Then for all integers $n$ and $k$,

$\displaystyle B_{n}$
$\displaystyle=\delta_{n,0}+\sum_{r=1}^{N}(B_{n-L_{r}}-\delta_{n,L_{r}})+\sum_{i=1}^{N_{\rm
o}}\biggl{(}B_{n-l_{\mathrm{o}i}}-\sum_{r=1}^{N}B_{n-l_{\mathrm{o}i}-L_{r}}\biggr{)}+\sum_{i=1}^{N_{\rm
c}}B_{n-l_{\mathrm{c}i}},$ (7) $\displaystyle B_{n,k}$
$\displaystyle=\delta_{n,0}\delta_{k,0}+\sum_{r=1}^{N}(B_{n-L_{r},k-K_{r}}-\delta_{n,L_{r}}\delta_{k,K_{r}})+\sum_{i=1}^{N_{\rm
o}}\biggl{(}B_{n-l_{\mathrm{o}i},k-k_{\mathrm{o}i}}-\sum_{r=1}^{N}B_{n-l_{\mathrm{o}i}-L_{r},k-k_{\mathrm{o}i}-K_{r}}\biggr{)}$
$\displaystyle\qquad\mbox{}+\sum_{i=1}^{N_{\rm
c}}B_{n-l_{\mathrm{c}i},k-k_{\mathrm{c}i}},$ (8)

where $B_{n<0}=B_{n,k<0}=B_{n<k,k}=0$. If the lengths of the cycles and
circuits are calculated as the number of tiles (the total contribution made to
the number of cells occupied) then $B_{n}$ is the number of $n$-tile tilings
(the number of tilings of an $n$-board) and $B_{n,k}$ is the number of such
tilings that use $k$ combs.

In the proofs of Identities 23, 24, 26, 27, 29, and 30 which use Theorem 22
(and Identities 32 and 33 which use Theorem 36), the lengths of the cycles and
circuits are the number of tiles they contain. In the proofs of Identities 25,
28, 31, and 34, the lengths of the cycles and circuits are the total number of
cells that the tiles along the arcs occupy. An $S$ occupies 1 cell whereas a
$C$ occupies $t$ cells. Thus if $L$ is the length of a cycle or circuit
containing $K$ combs when finding the recursion relations for $n$-tile tilings
then $L^{\prime}=L+(t-1)K$ is the length of that cycle or circuit when the
recursion relations are for the tilings of an $n$-board.

######  Identity 23.

For all $n,k\in\mathbb{Z}$,

$\left\langle\begin{matrix}n\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,3}=\delta_{n,0}\delta_{k,0}-\delta_{n,1}\delta_{k,1}+\left\langle\begin{matrix}n-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,3}+\left\langle\begin{matrix}n-1\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,3}-\left\langle\begin{matrix}n-2\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,3}+\left\langle\begin{matrix}n-2\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,3}\\\
+\left\langle\begin{matrix}n-3\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,3}-\left\langle\begin{matrix}n-3\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!2,3}.$ (9)

###### Proof.

The digraph for tiling with squares and $(1,1;3)$-combs has a single inner
cycle connecting the 01 node to itself by a $C$ (Fig. 5(b)). Hence 01 is the
common node and $L_{1}=K_{1}=1$. There are 2 outer cycles ($S$ and $C^{2}$)
and so $l_{\mathrm{o}1}=1$, $k_{\mathrm{o}1}=0$, and
$l_{\mathrm{o}2}=k_{\mathrm{o}2}=2$. There is a single common circuit
($CS^{2}$) which gives $l_{\mathrm{c}1}=3$ and $k_{\mathrm{c}1}=1$. ∎

######  Identity 24.

If $B_{n}$ is the sum of the $n$-th row of $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2,3}$ then for all $n$,

$B_{n}=\delta_{n,0}-\delta_{n,1}-\delta_{n,2}+2B_{n-1},$

where $B_{n<0}=0$.

###### Proof.

Sum each term in (9) over all $k$ or use (36). ∎

As defined above, $(B_{n})_{n\geq 0}=1,1,2,4,8,16,32,64,128,256,\ldots$ is
A011782.

######  Identity 25.

If $A_{n}$ is the sum of the $n$-th $(1,2)$-antidiagonal of
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,3}$ then for all
$n$,

$A_{n}=\delta_{n,0}-\delta_{n,3}+A_{n-1}+A_{n-3}-A_{n-4}+A_{n-5}+A_{n-6}-A_{n-9},$

where $A_{n<0}=0$.

###### Proof.

By Identity 1, the $n$-th $(1,2)$-antidiagonal of
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,3}$ is the $n$-th
row of $[\begin{smallmatrix}n\\\ k\end{smallmatrix}]_{2,3}$. From the
definition of the latter triangle, $A_{n}$ is the number of tilings of an
$n$-board using squares and $(1,1;3)$-combs and is given by (36) (with $B_{n}$
replaced by $A_{n}$) applied to the same digraph as in the proof of Identity
23 but with the following changes made to the lengths: $L_{1}=3$,
$l_{\mathrm{o}2}=6$, $l_{\mathrm{c}1}=5$. ∎

As defined above, $(A_{n})_{n\geq
0}=1,1,1,1,1,2,4,6,9,12,16,24,36,54,81,117,\ldots$ is A224809. From Corollary
9, $A_{n}$ is the number of subsets of $\mathbb{N}_{n-4}$ chosen so that no
two elements differ by 2 or 4.

Figure 6: Digraph for generating metatiles when tiling with squares and
$(1,1;4)$-combs ($m=2$, $t=4$).

######  Identity 26.

For all $n,k\in\mathbb{Z}$,

$\left\langle\begin{matrix}n\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,4}=\delta_{n,0}\delta_{k,0}-\delta_{n,2}(\delta_{k,1}+\delta_{k,2})+\left\langle\begin{matrix}n-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,4}+\left\langle\begin{matrix}n-2\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,4}+2\left\langle\begin{matrix}n-2\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,4}\\\
-\left\langle\begin{matrix}n-3\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,4}-\left\langle\begin{matrix}n-3\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,4}+\left\langle\begin{matrix}n-4\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,4}+\left\langle\begin{matrix}n-4\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,4}-\left\langle\begin{matrix}n-4\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!2,4}-\left\langle\begin{matrix}n-4\\\
k-4\end{matrix}\right\rangle_{\\!\\!\\!2,4}.$ (10)

###### Proof.

The digraph for tiling with squares and $(1,1;4)$-combs has 2 inner cycles
($SC$ and $C^{2}$) both of which pass though the 0101 and 01 nodes (Fig. 6).
We choose 0101 as the common node. We see that $L_{1}=L_{2}=2$, $K_{1}=1$, and
$K_{2}=2$. There are 2 outer cycles ($S$ and $C^{2}$) and so
$l_{\mathrm{o}1}=1$, $k_{\mathrm{o}1}=0$, and
$l_{\mathrm{o}2}=k_{\mathrm{o}2}=2$. There are 2 common circuits:
$CS\\{S,C\\}S$ where $X\\{Y,Z\\}$ means $XY$ and $XZ$. Hence
$l_{\mathrm{c}1}=l_{\mathrm{c}2}=4$, $k_{\mathrm{c}1}=1$, and
$k_{\mathrm{c}2}=2$. ∎

######  Identity 27.

If $B_{n}$ is the sum of the $n$-th row of $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2,4}$ then for all $n$,

$B_{n}=\delta_{n,0}-2\delta_{n,2}+B_{n-1}+3B_{n-2}-2B_{n-3},$

where $B_{n<0}=0$.

###### Proof.

Sum each term in (10) over all $k$ or use (36). ∎

As defined above, $(B_{n})_{n\geq 0}=1,1,2,3,7,12,27,49,106,199,419,\ldots$ is
A099163.

The proofs of the following identity and Identities 31 and 34 are analogous to
that of Identity 25. We just need to find the modified lengths of the cycles
and circuits in the digraph before using the theorem giving the recursion
relation.

######  Identity 28.

If $A_{n}$ is the sum of the $n$-th $(1,3)$-antidiagonal of
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,4}$ then for all
$n$,

$A_{n}=\delta_{n,0}-\delta_{n,5}-\delta_{n,8}+A_{n-1}+A_{n-5}-A_{n-6}+A_{n-7}+2A_{n-8}-A_{n-9}+A_{n-10}-A_{n-13}-A_{n-16},$

where $A_{n<0}=0$.

###### Proof.

We use the same digraph and associated parameters as in the proof of Identity
26 except that $L_{1}=5$, $L_{2}=8$, $l_{\mathrm{o}2}=8$, $l_{\mathrm{c}1}=7$,
and $l_{\mathrm{c}2}=10$. ∎

As defined above, $(A_{n})_{n\geq
0}=1,1,1,1,1,1,1,2,4,6,9,12,16,20,25,35,\ldots$ is A224808. From Corollary 9,
$A_{n}$ is the number of subsets of $\mathbb{N}_{n-6}$ chosen so that no two
elements differ by 2, 4, or 6.

######  Identity 29.

For all $n,k\in\mathbb{Z}$,

$\left\langle\begin{matrix}n\\\
k\end{matrix}\right\rangle_{\\!\\!\\!4,2}=\delta_{n,0}\delta_{k,0}-\delta_{n,2}\delta_{k,1}-\delta_{n,3}\delta_{k,2}-\delta_{n,4}\delta_{k,4}+\left\langle\begin{matrix}n-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!4,2}+\left\langle\begin{matrix}n-2\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-3\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!4,2}+\left\langle\begin{matrix}n-3\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!4,2}\\\
+\left\langle\begin{matrix}n-4\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!4,2}+\left\langle\begin{matrix}n-4\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!4,2}+2\left\langle\begin{matrix}n-4\\\
k-4\end{matrix}\right\rangle_{\\!\\!\\!4,2}+\left\langle\begin{matrix}n-5\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!4,2}+2\left\langle\begin{matrix}n-5\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-5\\\
k-4\end{matrix}\right\rangle_{\\!\\!\\!4,2}\\\
-\left\langle\begin{matrix}n-6\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-6\\\
k-5\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-7\\\
k-4\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-7\\\
k-5\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-7\\\
k-6\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-8\\\
k-7\end{matrix}\right\rangle_{\\!\\!\\!4,2}-\left\langle\begin{matrix}n-8\\\
k-8\end{matrix}\right\rangle_{\\!\\!\\!4,2}.$ (11)

###### Proof.

The digraph for tiling with squares and $(1,3;2)$-combs (which are also called
$(1,3)$-fences) has 3 inner cycles all of which contain the nodes 001 and 01
(Fig. 7). We choose 001 as the common node. The cycles, given as lists of arcs
starting from 001, are $\\{S,C\\{S,C^{2}\\}\\}C$. Hence $L_{i}=2,3,4$ and
$K_{i}=1,2,4$, respectively, for $i=1,2,3$. There are 5 outer cycles:
$S,C^{2}\\{S\\{S,CS\\},C\\{S,C\\}\\}$. Thus $l_{\mathrm{o}i}=1,4,5,4,4$ and
$k_{\mathrm{o}i}=0,2,3,3,4$, respectively, for $i=1,\ldots,5$. There are 8
common circuits: $C\\{S,CSC^{2}\\}\\{S^{2},C\\{S^{2},C\\{S,CS\\}\\}\\}$. Hence
$l_{\mathrm{c}i}=4,5,5,6,7,8,8,9$ and $k_{\mathrm{c}i}=1,2,3,4,4,5,6,7$,
respectively, for $i=1,\ldots,8$. ∎

Figure 7: Digraph for generating metatiles when tiling with squares and
$(1,3;2)$-combs ($m=4$, $t=2$).

######  Identity 30.

If $B_{n}$ is the sum of the $n$-th row of $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{4,2}$ then for all $n$,

$B_{n}=\delta_{n,0}-\delta_{n,2}-\delta_{n,3}-\delta_{n,4}+B_{n-1}+B_{n-2}+4B_{n-4}+2B_{n-5}-2B_{n-6}-3B_{n-7}-2B_{n-8},$

where $B_{n<0}=0$.

###### Proof.

Sum each term in (11) over all $k$ or use (36). ∎

As defined above, $(B_{n})_{n\geq 0}=1,1,1,1,5,12,21,34,70,155,318,610,\ldots$
has the generating function
$(1-x-x^{3})/((1-2x)(1-x^{2})(1+2x^{2}+x^{3}+x^{4}))$.

######  Identity 31.

If $A_{n}$ is the sum of the $n$-th antidiagonal of
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{4,2}$ then for all
$n$,

$A_{n}=\delta_{n,0}-\delta_{n,3}-\delta_{n,5}-\delta_{n,8}+A_{n-1}+A_{n-3}-A_{n-4}+2A_{n-5}+2A_{n-7}+4A_{n-8}-2A_{n-9}\\\
-2A_{n-11}-A_{n-12}-A_{n-13}-A_{n-15}-A_{n-16},$

where $A_{n<0}=0$.

###### Proof.

We use the same digraph and associated parameters as in the proof of Identity
29 except that $L_{1}=3$, $L_{2}=5$, $L_{3}=8$, $l_{\mathrm{o}i}=6,8,7,8$ for
$i=2,\ldots,5$, and for $i=1,\ldots,8$,
$l_{\mathrm{c}i}=5,7,8,10,11,13,14,16$. ∎

As defined above, $(A_{n})_{n\geq
0}=1,1,1,1,1,2,4,8,16,24,36,54,81,135,225,\ldots$ (after removing the first
four 1s) is A031923. From Corollary 9, $A_{n}$ is the number of subsets of
$\mathbb{N}_{n-4}$ chosen so that no two elements differ by 4.

Figure 8: Digraph for generating metatiles when tiling with squares and
$(1,1;5)$-combs ($m=2$, $t=5$).

######  Identity 32.

For all $n,k\in\mathbb{Z}$,

$\left\langle\begin{matrix}n\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,5}=\delta_{n,0}\delta_{k,0}-\delta_{n,1}\delta_{k,1}-\delta_{n,2}\delta_{k,2}+\delta_{n,3}(\delta_{k,3}-\delta_{k,1})+\left\langle\begin{matrix}n-1\\\
k\end{matrix}\right\rangle_{\\!\\!\\!2,5}+\left\langle\begin{matrix}n-1\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,5}-\left\langle\begin{matrix}n-2\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,5}\\\
+2\left\langle\begin{matrix}n-2\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,5}+\left\langle\begin{matrix}n-3\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,5}-\left\langle\begin{matrix}n-3\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,5}-2\left\langle\begin{matrix}n-3\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!2,5}-\left\langle\begin{matrix}n-4\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,5}\\\
+\left\langle\begin{matrix}n-4\\\
k-2\end{matrix}\right\rangle_{\\!\\!\\!2,5}+\left\langle\begin{matrix}n-4\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!2,5}-\left\langle\begin{matrix}n-4\\\
k-4\end{matrix}\right\rangle_{\\!\\!\\!2,5}+\left\langle\begin{matrix}n-5\\\
k-1\end{matrix}\right\rangle_{\\!\\!\\!2,5}-2\left\langle\begin{matrix}n-5\\\
k-3\end{matrix}\right\rangle_{\\!\\!\\!2,5}+\left\langle\begin{matrix}n-5\\\
k-5\end{matrix}\right\rangle_{\\!\\!\\!2,5}.$ (12)

###### Proof.

The digraph for tiling with squares and $(1,1;5)$-combs has 3 inner cycles but
no common node (Fig. 8). If the loop at the 0101 node were not present, the
digraph would have a common node. Using terminology and notation we introduce
in the appendix, the loop at 0101 is an errant loop and has length $L_{0}=1$
and number of combs $K_{0}=1$. We take the 010101 node as the pseudo-common
node (we could have also chosen the 01 node instead). There are two common
circuits, $CSCS$ and $CS^{4}$, the first of which is plain. Thus
$l_{\mathrm{c}1}=l_{\mathrm{pc}1}=4$, $k_{\mathrm{c}1}=k_{\mathrm{pc}1}=2$,
$l_{\mathrm{c}2}=5$, $k_{\mathrm{c}2}=1$, $N_{\mathrm{c}}=2$, and
$N_{\mathrm{pc}}=1$. Of the other two inner cycles, $C^{2}$ is plain, $S^{2}C$
is not. Thus $L_{1}=2$, $K_{1}=2$, $L_{2}=3$, and $K_{2}=1$. The outer cycles
are $S$ and $C^{2}$ and are both plain. Hence $l_{\mathrm{o}1}=1$,
$k_{\mathrm{o}1}=0$, $l_{\mathrm{o}2}=k_{\mathrm{o}2}=2$, and
$N_{\mathrm{o}}=2$. The identity then follows from applying (14). ∎

######  Identity 33.

If $B_{n}$ is the sum of the $n$-th row of $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2,5}$ then for all $n$,

$B_{n}=\delta_{n,0}-\delta_{n,1}-\delta_{n,2}+2B_{n-1}+B_{n-2}-2B_{n-3},$

where $B_{n<0}=0$.

###### Proof.

Sum each term in (12) over all $k$ or use (36). ∎

As defined above, $(B_{n})_{n\geq 0}=1,1,2,3,6,11,22,43,86,171,342,683,\ldots$
is A005578.

######  Identity 34.

If $A_{n}$ is the sum of the $n$-th $(1,4)$-antidiagonal of
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{2,5}$ then for all
$n$,

$A_{n}=\delta_{n,0}-\delta_{n,5}-\delta_{n,7}-\delta_{n,10}+\delta_{n,15}+A_{n-1}+A_{n-5}-A_{n-6}+A_{n-7}-A_{n-8}+A_{n-9}\\\
+2A_{n-10}-A_{n-11}+A_{n-12}-2A_{n-15}+A_{n-16}-2A_{n-17}-A_{n-20}+A_{n-25}$

where $A_{n<0}=0$.

###### Proof.

We use the same digraph and associated parameters as in the proof of Identity
32 except that $L_{0}=5$, $L_{1}=10$, $L_{2}=7$, $l_{\mathrm{o}2}=10$,
$l_{\mathrm{c}1}=l_{\mathrm{pc}1}=12$, and $l_{\mathrm{pc}2}=9$. ∎

As defined above, $(A_{n})_{n\geq
0}=1,1,1,1,1,1,1,1,1,2,4,6,9,12,16,20,25,30,36,48,64,\ldots$ is A224811. From
Corollary 9, $A_{n}$ is the number of subsets of $\mathbb{N}_{n-8}$ chosen so
that no two elements differ by 2, 4, 6, or 8.

##  7 Discussion

In this paper and AE22 we considered tiling-derived triangles whose entries
were shown to be numbers of $k$-subsets of $\mathbb{N}_{n}$ such that no two
elements of the subset differ by an element in a set $\mathcal{Q}$ of
disallowed differences. In AE22, $\mathcal{Q}=\\{m\\}$ for fixed
$m\in\mathbb{Z}^{+}$, whereas in the present paper,
$\mathcal{Q}=\\{m,2m,\ldots,(t-1)m\\}$, where $t=2,3,\ldots$. One is then led
to ask whether there is a correspondence between restricted combinations
specified by other types of $\mathcal{Q}$ and tilings. When
$\mathcal{Q}=\mathbb{N}_{q}$ for some $q\in\mathbb{Z}^{+}$, using the same
ideas as in the proof of Lemma 7, it is straightforward to show that there is
a bijection between the tilings of an $(n+q)$-board using $k$ $(q+1)$-ominoes
and squares and the number of $k$-subsets. However, the corresponding $n$-tile
tilings triangles are just Pascal’s triangle for any $q$. In order to obtain a
tiling interpretation of restricted combinations with other classes of
$\mathcal{Q}$ one needs a form of a tiling where some parts of the tiles are
allowed to overlap with parts of other tiles. This will be explored in depth
in another paper. Whether or not such tiling schemes can be used to generate
further aesthetically pleasing families of number triangles remains to be
seen.

From some of the entries in the OEIS that give the sums of the
$(1,t-1)$-antidiagonals of the triangle (see A224809, A224808, and A224811) it
appears that the number of subsets of $\mathbb{N}_{n-(t-1)m}$ whose elements
do not differ by an element of the set $\\{m,2m,\ldots,(t-1)m\\}$ is also the
number of permutations $\pi$ of $\mathbb{N}_{n}$ such that
$\pi(i)-i\in\\{-m,0,(t-1)m\\}$ for all $i\in\mathbb{N}_{n}$. This is indeed
true in general as we will demonstrate combinatorially using combs and fences
elsewhere.

In AE22 it was noted that the $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{1,2}$ and $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{2,2}$ triangles are row-reversed Riordan arrays and
it was shown (in Corollary 37 of AE22) that the
$\langle\begin{smallmatrix}n\\\ k\end{smallmatrix}\rangle_{m>2,2}$ triangles
are not. From Theorem 35 of AE22, the $\langle\begin{smallmatrix}n\\\
k\end{smallmatrix}\rangle_{m\geq 2,t\geq 3}$ triangles are not row-reversed
Riordan arrays since when tiling with $(1,m-1;t)$-combs and squares, the
filled-comb metatile contains more than one square if $(m-1)(t-1)>1$. The same
theorem tells us that, except for the $m=1$ cases, the triangles are also not
Riordan arrays since there are metatiles containing more than one comb.

There are a number of types of tiling that lead to common-node-free digraphs
that have only a few inner cycles. As far as we are aware, Theorem 36 is the
first result giving recursion relations for a class of such cases. The theorem
can be modified or generalized to cope with a wider variety of classes and we
will present these results in future studies involving applications of tilings
where instances of such digraphs arise.

##  8 Appendix: Recursion relations for 3-inner-cycle digraphs with a pseudo-
common node

For a digraph lacking a common node, we refer to an inner cycle that can be
represented as a single arc linking a node $\mathcal{E}$ to itself as an
errant loop if the digraph would have a common node $\mathcal{P}$ if the
errant loop arc were removed. The node $\mathcal{P}$ is then referred to as a
pseudo-common node. Evidently, $\mathcal{E}$ and $\mathcal{P}$ cannot be the
same node; if they were the same node, the original digraph would have a true
common node. For a digraph with an errant loop, a common circuit is defined as
two concatenated simple paths from the 0 node to $\mathcal{P}$ and from
$\mathcal{P}$ to the 0 node. An outer cycle, inner cycle, or common circuit is
said to be plain if it does not include the errant loop node $\mathcal{E}$.
See the proof of Identity 32 for examples.

We use the $N=2$ case of the following lemma in the proof of Theorem 36.

######  Lemma 35.

For positive integers $j_{0},j_{1},\ldots,j_{N}$ where $N\geq 2$,

$\binom{j_{1}+\cdots+j_{N}}{j_{1},\ldots,j_{N}}\binom{j_{0}+j_{N}-1}{j_{0}}\\!=\\!\sum_{r=1}^{N-1}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots}\Biggl{(}\\!\binom{j_{0}+j_{N}-1}{j_{0}}-\binom{j_{0}+j_{N}-2}{j_{0}-1}\\!\Biggr{)}\\\
+\binom{j_{1}+\cdots+j_{N}}{j_{1},\ldots,j_{N}}\binom{j_{0}+j_{N}-2}{j_{0}-1}+\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{N}-1}\binom{j_{0}+j_{N}-2}{j_{0}}.$

###### Proof.

Using the result for multinomial coefficients that

$\binom{j_{1}+\cdots+j_{N}}{j_{1},\ldots,j_{N}}=\sum_{r=1}^{N}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots,j_{N}},$

we have

$\displaystyle\binom{j_{1}+\cdots+j_{N}}{j_{1},\ldots,j_{N}}\binom{j_{0}+j_{N}-1}{j_{0}}$
$\displaystyle\qquad\qquad=\Biggl{(}\sum_{r=1}^{N-1}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots}+\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{N}-1}\Biggr{)}\binom{j_{0}+j_{N}-1}{j_{0}}$
$\displaystyle\qquad\qquad=\sum_{r=1}^{N-1}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots}\binom{j_{0}+j_{N}-1}{j_{0}}$
$\displaystyle\qquad\qquad\qquad+\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{N}-1}\Biggl{(}\binom{j_{0}+j_{N}-2}{j_{0}}+\binom{j_{0}+j_{N}-1}{j_{0}-1}\Biggr{)}$
$\displaystyle\qquad\qquad=\sum_{r=1}^{N-1}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots}\binom{j_{0}+j_{N}-1}{j_{0}}+\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{N}-1}\binom{j_{0}+j_{N}-2}{j_{0}}$
$\displaystyle\qquad\qquad\qquad+\Biggl{(}\binom{j_{1}+\cdots+j_{N}}{j_{1},\ldots,j_{N}}-\sum_{r=1}^{N-1}\binom{j_{1}+\cdots+j_{N}-1}{j_{1},\ldots,j_{r}-1,\ldots,j_{N}}\Biggr{)}\binom{j_{0}+j_{N}-2}{j_{0}-1},$

which gives the required result on rearranging. ∎

######  Theorem 36.

For a digraph with an errant loop of length $L_{0}$ containing $K_{0}$ combs,
a plain inner cycle of length $L_{1}$ containing $K_{1}$ combs, a non-plain
inner cycle of length $L_{2}$ containing $K_{2}$ combs, and outer cycles that
are all plain and have length $l_{\mathrm{o}i}$ and contain $k_{\mathrm{o}i}$
combs for $i=1,\ldots,N_{\rm o}$, let $l_{\mathrm{c}i}$ be the length of the
$i$-th common circuit and let $k_{\mathrm{c}i}$ be the number of combs it
contains ($i=1,\ldots,N_{\rm c}$), and let $l_{\mathrm{pc}i}$ be the length of
the $i$-th plain common circuit and let $k_{\mathrm{pc}i}$ be the number of
combs it contains ($i=1,\ldots,N_{\rm pc}$). Then for all integers $n$ and
$k$,

$\displaystyle B_{n}$
$\displaystyle=\delta_{n,0}+\sum_{r=0}^{2}(B_{n-L_{r}}-\delta_{n,L_{r}})+\delta_{n,L_{0}+L_{1}}-B_{n-L_{0}-L_{1}}$
$\displaystyle\qquad+\sum_{i=1}^{N_{\rm
o}}\biggl{(}B_{n-l_{\mathrm{o}i}}+B_{n-l_{\mathrm{o}i}-L_{0}-L_{1}}-\sum_{r=0}^{N}B_{n-l_{\mathrm{o}i}-L_{r}}\biggr{)}+\sum_{i=1}^{N_{\rm
c}}B_{n-l_{\mathrm{c}i}}-\sum_{i=1}^{N_{\rm pc}}B_{n-l_{\mathrm{pc}i}-L_{0}},$
(13) $\displaystyle B_{n,k}$
$\displaystyle=\delta_{n,0}\delta_{k,0}+\sum_{r=0}^{2}(B_{n-L_{r},k-K_{r}}-\delta_{n,L_{r}}\delta_{k,K_{r}})+\delta_{n,L_{0}+L_{1}}\delta_{k,K_{0}+K_{1}}-B_{n-L_{0}-L_{1},k-K_{0}-K_{1}}$
$\displaystyle\qquad+\sum_{i=1}^{N_{\rm
o}}\biggl{(}B_{n-l_{\mathrm{o}i},k-k_{\mathrm{o}i}}+B_{n-l_{\mathrm{o}i}-L_{0}-L_{1},k-k_{\mathrm{o}i}-K_{0}-K_{1}}-\sum_{r=0}^{N}B_{n-l_{\mathrm{o}i}-L_{r},k-k_{\mathrm{o}i}-K_{r}}\biggr{)}$
$\displaystyle\qquad+\sum_{i=1}^{N_{\rm
c}}B_{n-l_{\mathrm{c}i},k-k_{\mathrm{c}i}}-\sum_{i=1}^{N_{\rm
pc}}B_{n-l_{\mathrm{pc}i}-L_{0},k-k_{\mathrm{pc}i}-K_{0}},$ (14)

where $B_{n<0}=B_{n,k<0}=B_{n<k,k}=0$. If the lengths of the cycles and
circuits are calculated as the number of tiles (the total contribution made to
the number of cells occupied) then $B_{n}$ is the number of $n$-tile tilings
(the number of tilings of an $n$-board) and $B_{n,k}$ is the number of such
tilings that use $k$ combs.

###### Proof.

To keep the algebra looking as simple as possible while retaining the
essentials at the heart of the proof, we just prove the formula for $B_{n}$
when there is a single outer cycle, one plain common circuit, and one non-
plain common circuit. Their respective lengths are $l_{\rm o}$, $l_{\rm pc}$,
and $l_{\rm npc}$. It is straightforward to modify the proof we give here to
include the sums over outer cycles and common circuits. The proof of (14) is
entirely analogous.

Conditioning on the final metatile gives

$B_{n}=\delta_{n,0}+B_{n-l_{\rm o}}+\sum_{j_{1}\geq 0}B_{n-l_{\rm
pc}-j_{1}L_{1}}+\sum_{\begin{subarray}{c}j_{0},j_{1}\geq 0,\\\ j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}B_{n-l_{\rm
pc}-j_{0}L_{0}-j_{1}L_{1}-j_{2}L_{2}}\\\ +\sum_{e,j_{1}\geq 0}B_{n-l_{\rm
npc}-eL_{0}-j_{1}L_{1}}+\sum_{\begin{subarray}{c}e,j_{0},j_{1}\geq 0,\\\
j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}B_{n-l_{\rm
npc}-(j_{0}+e)L_{0}-j_{1}L_{1}-j_{2}L_{2}}$ (15)

with $B_{n<0}=0$. We now explain the origin of the four sums in (15) while
referring to the digraph in Fig. 8 (taking the 010101 node as $\mathcal{P}$)
for examples of metatiles. The first sum is from metatiles obtained by taking
the first part of the plain common circuit to $\mathcal{P}$, then following
the plain inner cycle $j_{1}$ times, and then returning to the 0 node via the
second half of the plain common circuit (e.g., $CSC^{2j_{1}}CS$ is the
symbolic representation of the metatiles corresponding to the terms in the
sum).

The second sum corresponds to metatiles with the same start and end as with
the first sum but on reaching $\mathcal{P}$ the plain and non-plain inner
cycles are executed $j_{1}$ and $j_{2}$ times, respectively, in any order but
the non-plain inner cycle is executed at least once. The number of ways of
choosing the order is $\tbinom{j_{1}+j_{2}}{j_{1}}$. The errant loop is also
traversed a total of $j_{0}$ times. Each time the path reaches $\mathcal{E}$
(during an execution of the non-plain inner cycle), it can detour and traverse
the errant loop any number of times. This is the origin of the
$\tbinom{j_{0}+j_{2}-1}{j_{0}}$ factor which has $j_{2}-1$ rather than $j_{2}$
as the non-plain inner cycle must be started before the errant loop can be
traversed. E.g., the metatiles corresponding to the terms in the sum when
$j_{0}=j_{1}=j_{2}=1$ are $CS\\{C^{2}SCS,SCSC^{2}\\}CS$.

The third and fourth sums are analogous to the first and second but
$\mathcal{P}$ is reached via the first half of the non-plain common circuit,
and after the inner cycles have been traversed $j_{r}$ times (with $r=1$ in
the third sum and $r=0,1,2$ in the fourth), the 0 node is returned to via the
second half of the non-plain common circuit but the errant loop is executed an
extra $e$ times when the path reaches $\mathcal{E}$. E.g., the metatiles
corresponding to the terms in the third sum are $CSC^{2j_{1}}SC^{e}S^{2}$, and
in the fourth sum when $j_{0}=j_{1}=j_{2}=1$ they are
$CS\\{C^{2}SCS,SCSC^{2}\\}SC^{e}S^{2}$.

Representing (15) by $E(n)$, we write down

$E(n)-E(n-L_{0})-E(n-L_{1})+E(n-L_{0}-L_{1})-E(n-L_{2})$

and re-index the sums so that, where possible, the $B_{n-\alpha}$ inside the
sums for any $\alpha$ appear the same as for $E(n)$ (e.g., $\sum_{j_{1}\geq
0}B_{n-L_{1}-l_{\rm pc}-j_{1}L_{1}}=\sum_{j_{1}\geq 1}B_{n-l_{\rm
pc}-j_{1}L_{1}}$). This leaves

$B_{n}-\sum_{r=0}^{2}B_{n-L_{r}}+B_{n-L_{0}-L_{1}}=\delta_{n,0}+B_{n-l_{\rm
o}}-\sum_{r=0}^{2}(\delta_{n,L_{r}}+B_{n-l_{\rm
o}-L_{r}})+\delta_{n,L_{0}+L_{1}}+B_{n-l_{\rm o}-L_{0}-L_{1}}\\\
+\sum_{j_{1}\geq 0}\beta_{j_{1}L_{1}}-\sum_{j_{1}\geq
1}\beta_{j_{1}L_{1}}-\sum_{j_{1}\geq
0}\beta_{L_{0}+j_{1}L_{1}}+\sum_{j_{1}\geq
1}\beta_{L_{0}+j_{1}L_{1}}-\sum_{j_{1}\geq 0}\beta_{j_{1}L_{1}+L_{2}}\\\
+\sum_{e,j_{1}\geq 0}\hat{\beta}_{j_{1}L_{1}}-\sum_{\begin{subarray}{c}e\geq
0,\\\ j_{1}\geq
1\end{subarray}}\hat{\beta}_{j_{1}L_{1}}-\sum_{\begin{subarray}{c}e\geq 1,\\\
j_{1}\geq 0\end{subarray}}\hat{\beta}_{j_{1}L_{1}}+\sum_{e,j_{1}\geq
1}\hat{\beta}_{j_{1}L_{1}}-\sum_{e,j_{1}\geq
0}\hat{\beta}_{j_{1}L_{1}+L_{2}}\\\ +\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
0,\\\ j_{2}\geq
1\end{subarray}}\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}-\sum_{\begin{subarray}{c}j_{0}\geq
0,\\\ j_{1},j_{2}\geq
1\end{subarray}}\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}\\\
-\sum_{\begin{subarray}{c}j_{0},j_{2}\geq 1,\\\ j_{1}\geq
0\end{subarray}}\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}+\sum_{j_{0},j_{1},j_{2}\geq
1}\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}\\\
-\sum_{\begin{subarray}{c}j_{0},j_{1}\geq 0,\\\ j_{2}\geq
2\end{subarray}}\binom{j_{1}+j_{2}-1}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}}\beta_{\lambda}\\\
+\text{the above 3 lines with $\beta_{\lambda}$ replaced by
$\hat{\beta}_{\lambda}$ and also summed over all $e\geq 0$},$ (16)

where $\beta_{a}=B_{n-l_{\rm pc}-a}$, $\hat{\beta}_{a}=B_{n-l_{\rm
npc}-eL_{0}-a}$, and $\lambda=j_{0}L_{0}+j_{1}L_{1}+j_{2}L_{2}$. On
rearranging (16) it is immediately apparent where all but the last two sums in
(36) come from. The first two sums in the second line of (16) reduce to
$\beta_{0}=B_{n-l_{\rm pc}}$. The next two sums reduce to
$-\beta_{L_{0}}=-B_{n-l_{\rm pc}-L_{0}}$ which accounts for the final sum in
(36). The first four sums in the third line of (16) reduce to $B_{n-l_{\rm
npc}}$ which when added to the $B_{n-l_{\rm pc}}$ accounts for the penultimate
sum in (36).

We now complete the proof by showing that the remaining terms in (16) cancel
out. We regroup terms in each of the sums in the fourth, fifth, and sixth
lines in (16) to give

$\displaystyle\sum_{\begin{subarray}{c}j_{0},j_{1}\geq 0,\\\ j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}=\\!\\!\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}$
$\displaystyle\qquad+\sum_{j_{0},j_{1}\geq
1}\\!\\!\\!\binom{j_{1}+1}{j_{1}}\beta_{j_{0}L_{0}+j_{1}L_{1}+L_{2}}+\sum_{\begin{subarray}{c}j_{0}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{j_{0}L_{0}+j_{2}L_{2}}+\sum_{\begin{subarray}{c}j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{1}+j_{2}}{j_{1}}\beta_{j_{1}L_{1}+j_{2}L_{2}}$
$\displaystyle\qquad+\sum_{j_{0}\geq
1}\beta_{j_{0}L_{0}+L_{2}}+\sum_{j_{1}\geq
1}\binom{j_{1}+1}{j_{1}}\beta_{j_{1}L_{1}+L_{2}}+\sum_{j_{2}\geq
2}\beta_{j_{2}L_{2}}+\beta_{L_{2}},$ (17a)
$\displaystyle\sum_{\begin{subarray}{c}j_{0}\geq 0,\\\ j_{1},j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}=\\!\\!\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{\lambda}$
$\displaystyle\qquad+\sum_{j_{0},j_{1}\geq
1}\\!\\!\\!\binom{j_{1}}{j_{1}-1}\beta_{j_{0}L_{0}+j_{1}L_{1}+L_{2}}+\sum_{\begin{subarray}{c}j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{1}+j_{2}-1}{j_{1}-1}\beta_{j_{1}L_{1}+j_{2}L_{2}}+\sum_{j_{1}\geq
1}\binom{j_{1}}{j_{1}-1}\beta_{j_{1}L_{1}+L_{2}},$ (17b)
$\displaystyle\sum_{\begin{subarray}{c}j_{0},j_{2}\geq 1,\\\ j_{1}\geq
0\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}=\\!\\!\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}$
$\displaystyle\qquad+\sum_{j_{0},j_{1}\geq
1}\\!\\!\\!\binom{j_{1}+1}{j_{1}}\beta_{j_{0}L_{0}+j_{1}L_{1}+L_{2}}+\sum_{\begin{subarray}{c}j_{0}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{0}+j_{2}-1}{j_{0}-1}\beta_{j_{0}L_{0}+j_{2}L_{2}}+\sum_{j_{0}\geq
1}\beta_{j_{0}L_{0}+L_{2}},$ (17c) $\displaystyle\sum_{j_{0},j_{1},j_{2}\geq
1}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}=\\!\\!\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}-1}\binom{j_{0}+j_{2}-2}{j_{0}-1}\beta_{\lambda}$
$\displaystyle\qquad+\sum_{j_{0},j_{1}\geq
1}\\!\\!\\!\binom{j_{1}}{j_{1}-1}\beta_{j_{0}L_{0}+j_{1}L_{1}+L_{2}},$ (17d)
$\displaystyle\sum_{\begin{subarray}{c}j_{0},j_{1}\geq 0,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}}\beta_{\lambda}=\\!\\!\sum_{\begin{subarray}{c}j_{0},j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}-1}{j_{1}}\binom{j_{0}+j_{2}-2}{j_{0}}\beta_{\lambda}$
$\displaystyle\qquad+\sum_{\begin{subarray}{c}j_{0}\geq 1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{0}+j_{2}-1}{j_{0}}\beta_{j_{0}L_{0}+j_{2}L_{2}}+\sum_{\begin{subarray}{c}j_{1}\geq
1,\\\ j_{2}\geq
2\end{subarray}}\\!\binom{j_{1}+j_{2}-1}{j_{1}}\beta_{j_{1}L_{1}+j_{2}L_{2}}+\sum_{j_{2}\geq
2}\beta_{j_{2}L_{2}}.$ (17e)

We denote the $p$-th sum (or term) on the right-hand side of (17$x$) by
$x_{p}$ where $x$ is a–e. Then
$\mathrm{a}_{1}-\mathrm{b}_{1}-\mathrm{c}_{1}+\mathrm{d}_{1}-\mathrm{e}_{1}=0$
by virtue of Lemma 35, $\mathrm{a}_{2}$ cancels $\mathrm{c}_{2}$,
$\mathrm{a}_{3}$ cancels $\mathrm{c}_{3}+\mathrm{e}_{2}$, $\mathrm{a}_{4}$
cancels $\mathrm{b}_{3}+\mathrm{e}_{3}$, $\mathrm{a}_{5}$ cancels
$\mathrm{c}_{4}$,
$\mathrm{a}_{6}-\mathrm{b}_{4}+\mathrm{a}_{8}=\sum_{j_{1}\geq
0}\beta_{j_{1}L_{1}+L_{2}}$ and therefore cancels the last sum in the second
line of (16), $\mathrm{a}_{7}$ cancels $\mathrm{e}_{4}$, and $\mathrm{b}_{2}$
cancels $\mathrm{d}_{2}$. The simplification works in the same way for the
terms represented by the last line of (16). Denoting sums or terms in the
corresponding set of equations by $\hat{x}_{p}$,
$\hat{\mathrm{a}}_{6}-\hat{\mathrm{b}}_{4}+\hat{\mathrm{a}}_{8}=\sum_{e,j_{1}\geq
0}\hat{\beta}_{j_{1}L_{1}+L_{2}}$ and therefore cancels the last sum in the
third line of (16).

The proof of (14) proceeds in an analogous way. Again considering the case
where there is a single outer cycle (with $k_{\rm o}$ combs), a plain common
circuit (with $k_{\rm pc}$ combs), and a non-plain common circuit (with
$k_{\rm npc}$ combs), conditioning on the final metatile gives

$B_{n,k}=\delta_{n,0}\delta_{k,0}+B_{n-l_{\rm o},k-k_{\rm o}}+\sum_{j_{1}\geq
0}B_{n-l_{\rm pc}-j_{1}L_{1},n-k_{\rm pc}-j_{1}K_{1}}\\\
+\sum_{\begin{subarray}{c}j_{0},j_{1}\geq 0,\\\ j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}B_{n-l_{\rm
pc}-\lambda,k-k_{\rm pc}-\kappa}+\sum_{e,j_{1}\geq 0}B_{n-l_{\rm
npc}-eL_{0}-j_{1}L_{1},k-k_{\rm npc}-eK_{0}-j_{1}K_{1}}\\\
+\sum_{\begin{subarray}{c}e,j_{0},j_{1}\geq 0,\\\ j_{2}\geq
1\end{subarray}}\\!\\!\\!\binom{j_{1}+j_{2}}{j_{1}}\binom{j_{0}+j_{2}-1}{j_{0}}B_{n-l_{\rm
npc}-eL_{0}-\lambda,k-k_{\rm npc}-eK_{0}-\kappa}$ (18)

with $B_{n,k>n}=B_{n,k<0}=0$ and where
$\kappa=j_{0}K_{0}+j_{1}K_{1}+j_{2}K_{2}$. Denoting (18) by $E(n,k)$, writing
down

$E(n,k)-E(n-L_{0},k-K_{0})-E(n-L_{1},k-K_{1})+E(n-L_{0}-L_{1},k-K_{0}-K_{1})-E(n-L_{2},k-K_{2}),$

and then proceeding in the same way as for the proof of (36) gives the
required result. ∎

## References

  * [1] M. A. Allen and K. Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, _Lin. Multilin. Algebra_ (2022), https://doi.org/10.1080/03081087.2022.2107979, https://arxiv.org/abs/2107.02589.
  * [2] M. A. Allen and K. Edwards, On two families of generalizations of Pascal’s triangle, _J. Integer Sequences_ 25 (2022), Article 22.7.1.
  * [3] P. Barry, _Riordan Arrays: A Primer_ , Logic Press, Kilcock, 2016.
  * [4] K. Edwards, A Pascal-like triangle related to the tribonacci numbers, _Fibonacci Quart._ 46/47 (2008/2009), 18–25.
  * [5] K. Edwards and M. A. Allen, Strongly restricted permutations and tiling with fences, _Discrete Appl. Math._ 187 (2015), 82–90.
  * [6] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, _Fibonacci Quart._ 57 (5) (2019), 48–53.
  * [7] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers cubed, _Fibonacci Quart._ 58 (5) (2020), 128–134.
  * [8] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared. Part II, _Fibonacci Quart._ 58 (2020), 169–177.
  * [9] K. Edwards and M. A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, _J. Integer Sequences_ 24 (2021), Article 21.3.8.
  * [10] J. Konvalina and Y.-H. Liu, Subsets without $q$-separation and binomial products of Fibonacci numbers, _J. Combin. Theor. A_ 57 (1991), 306–310.
  * [11] T. Mansour and Y. Sun, On the number of combinations without certain separations, _Eur. J. Combinator._ 29 (2008), 1200–1206.
  * [12] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, _Discrete Appl. Math._ 34 (1991), 229–239.
  * [13] N. J. A. Sloane, _The Online Encyclopedia of Integer Sequences_ , published electronically, 2010. Available at https://oeis.org.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 05A19,
05A15.

_Keywords_ : combinatorial proof, combinatorial identity, $n$-tiling, Pascal-
like triangle, directed pseudograph, Fibonacci polynomial, restricted
combination

(Concerned with sequences A000045, A000930, A003269, A003520, A005578,
A005708, A005709, A005710, A007318, A011782, A031923, A099163, A224808,
A224809, A224811, A350110, A350111, A350112, A354665, A354666, A354667, and
A354668)