
%perms.tex: a Plain TeX file George Spahn and Doron Zeilberger
%Counting permutations such that Pi[i+r]-Pi[i]<>s
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
Counting Permutations Where The Difference Between Entries Located r Places Apart 
}
\centerline
{\bf
Can never be s (For any given positive integers r and s)
}
\bigskip
\centerline
{\it George SPAHN and Doron ZEILBERGER}

\bigskip

\qquad \qquad {\it In fond memory of David Peter Robbins (12 August 1942 - 4 September 2003) who was a great problem solver, and an equally good problem poser}

{\bf Abstract}: Given positive integers $r$ and $s$,  We  use {\it inclusion-exclusion}, {\it weighted-counting of tilings}, 
and {\it dynamical programming}, in order to enumerate, semi-efficiently, 
the classes of permutations mentioned in the title.
In the process we revisit beautiful previous work of Enrique Navarette, Robert Taurasu, David Robbins (to whose memory this article is dedicated),
and John Riordan.
We conclude with two proofs of John Riordan's recurrence (from 1965) for the enumerating sequence for permutations that 
adjacent entries can't have adjacent values (the $r=1,s=1$ case of the title in the sense of absolute value).
The first is {\it fully automatic} using the (continuous) Almkvist-Zeilberger algorithm, while the second is {\it purely human-generated} via
an elegant combinatorial argument.

{\bf Important: Maple Package and Output Files}

This article is accompanied by a Maple package {\tt ResPerms.txt} downloadable from

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/ResPerms.txt} \quad .

The front of this article 

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/perms.html}

contains many input and output files.


{\bf How it all Started}

A few months ago we came across a lovely paper by Manuel Kauers and Christoph Koutschan [KK] where they described
how to guess recurrences satisfied by `hard to compute sequences' where one can get very plausible conjectured
recurrences for sequences with far fewer "data points" than is needed for traditional guessing with
{\it undetermined coefficients}. As a very impressive {\it case study} they found a conjectured
linear recurrence with polynomial coefficients enumerating the number of
permutations $\pi$ of $\{1, \dots, n\}$ such that
$$
\pi_{i+2} - \pi_i \neq 2 \quad .
$$

This is sequence  A189281 in the OEIS ({\tt https://oeis.org/A189281}) [S22], that initially took a very long time to compute the first $35$ terms, hence it was labeled {\bf hard}, and there
was no a priori theoretical guarantee that it is {\it holonomic}, i.e. satisfies a linear recurrence equation with polynomial coefficients, surprisingly turned out to
most likely be one. The traditional {\it vanilla} method of  of guessing a recurrence of order $r$ and degree $d$ requires at least $(r+1)(d+1)+r+1$ data points,
and the number of terms given  in the OEIS at the time (computed, with lots of computer time and memory by Vaclav Kotesovec) did not work, one needed more data.
Using their ingenious new method of "guessing with little data" they conjectured a linear recurrence equation of order $8$ and degree $11$ (that would require
$(8+1)\cdot (11+1)+8+1=117$  data points. They only used $35$ terms! Assuming that conjecture is true one of us (DZ) found an equivalent recurrence of
order $13$ and degree $3$ that would necessitate $(13+1)\cdot(3+1)+13+1=70$ data points (still twice as many).



But even with the new method one needs efficient ways to generate as many terms as possible. We would like to efficiently count  the following two kinds of sequences,
for {\it any} positive integers $r$ and $s$
$$
a_{r,s}(n):= \# \{\pi \in S_n \, | \, \pi_{i+r}\,- \, \pi_r \neq \, s \,\, for \quad all \quad 1 \leq i \leq n-r\} \quad,
$$
and
$$
b_{r,s}(n):= \#\{\pi \in S_n \, | \, |\pi_{i+r}\,- \, \pi_r| \neq \, s \,\, for \quad all \quad 1 \leq i \leq n-r\} \quad .
$$

(For any finite set $S$, $\#S$ denotes its number of elements).

{\bf Past Work}

For the sequences $a_{1,s}$ for {\it any} $s$, Enrique Navarrete found a beautiful explicit formula, using a clever {\it inclusion-exclusion} argument

{\bf Theorem} (E. Navarrete [N]) for all $s \geq 1$ and $n \geq s$,
$$
a_{1,s}(n) \, = \,\sum_{j=0}^{n-s} (-1)^j {{n-s} \choose {j}} (n-j)! \quad .
$$

Using the {\bf Zeilberger algorithm}[Z1] we immediately get

{\bf Corollary} For $s \geq 1$ and for $n \geq 2$ we have
$$
a_{1,s}(n)=(n-1)\, a_{1,s}(n-1)+(n-s+1)\,a_{1,s}(n-2) 
$$

In the last section we will give a combinatorial proof.

The sequence $b_{1,1}(n)$ is famous! It is sequence A2464 [S11a] {\tt https://oeis.org/A002464}, called         
Hertzsprung's problem, and its description in the OEIS is:

{\it ways to arrange $n$ non-attacking kings on an $n \times n$ board, with $1$ in each row and column. Also number of permutations of length $n$ without rising or falling successions.}

The combinatorial giant, John Riordan [R]  proved a nice fourth-order recurrence
$$
b_{1,1}(n)\,= \,(n+1) \, b_{1,1}(n-1) \, - \, (n-2)\, b_{1,1}(n-2) \, - \, (n-5)\,b_{1,1}(n-3) \, + \, (n-3)\,b_{1,1}(n-4) \quad .
$$
We will later give two new proofs. The first using the continuous Almkvist-Zeilberger algorithm [AZ], and the second using an elegant combinatorial argument.

Our hero, Dave Robbins [R], used  a clever {\it inclusion-exclusion} argument to prove the following double sum
$$
b_{1,1}(n)=  \sum_{i=0}^{n-1} (-1)^i (n-i)! \, \sum_{c=1}^{i} {{i-1} \choose {i-c}} {{n-i} \choose {c}}2^c \quad .
$$

We will later use Dave Robbins' approach to study, and efficiently compute, the sequences $b_{1,s}(n)$ for $s>1$, none of which are (yet) in the OEIS.

To conclude this historical section let's mention which sequences are currently (Oct. 2022) in the OEIS:

$\bullet$ $a_{1s}(n)$ for $1 \leq s \leq 5$, see references [S11],[S12],[S13],[S14],[S15] respectively.

$\bullet$ $a_{rr}(n)$ for $1 \leq r \leq 6$, see references [S11],[S22],[S33],[S44],[S55],[S66] respectively.

$\bullet$ $b_{rr}(n)$ for $1 \leq r \leq 6$, see references [S11a],[S22a],[S33a],[S44a],[S55a],[S66a] respectively.


Mone of the  sequences $a_{rs}(n)$  and  $b_{rs}(n)$  with $r >1, s>1$ and $r \neq s$ are yet (Oct. 2022) in the OEIS.

In the  next section we will show how to compute many terms of these new sequences and compute {\it many more terms} for the
sequences $a_{rr}(n)$ and $b_{rr}(n)$, $2\leq r\leq 6$, that are already in the OEIS.

{\bf Semi-Efficient Computation of the sequences $a_{r,s}(n)$}

We will use the old workhorse of {\it inclusion-exclusion} but with a new {\it twist}, that would make it amenable for {\it symbolic computation}.

Fix $r \geq 1$ and $s \geq 1$. We want to count all the {\it good guys}, i.e. permutations of $\{1, \dots , n\}$ such that none of the following $n-r$ {\bf unfortunate events} are
committed
$$
\pi_{r+1} -\pi_1=s \quad, \quad \pi_{r+2} -\pi_2=s \quad, \quad \dots \quad, \pi_{n}-\pi_{n-r}=s \quad .
$$
As usual, instead of counting {\bf good guys}, we do a {\it signed} counting of {\bf all pairs}, 
$$
[guy, S] \quad,
$$
where {\it guy} is {\it any} permutation, and $S$ is a subset (possibly empty, possibly the the whole) of its set of unfortunate events. (See [Z3] for an engaging account).
Each such pair contributes $(-1){\#S}$ to the total sum. While this new signed sum has many more terms, and is extremely inefficient when applied to
specific sets, it isa great theoretical tool when used cleverly by humans (and computers!).

Looking at the structure of this possible {\it set of unfortunate events}, we see that the {\bf board} $\{1,2, \dots, n\}$ has a certain subsest of the set of pairs
$$
\{\{1,r+1\} \, , \, \{2,r+2\} \, , \quad \dots , \, \{n-r,n\} \}\quad,
$$
(right now we are ignoring entries of the permutation. Think of them as a collection of {\it arcs} $r$ apart). Each such configuration naturally forms into a disjoint
union of {\bf connected components}. All the entries that do not participate are really singleton tiles. So looking at the possible connected components,
we see a natural {\it tiling} of the `board'  $\{1,2, \dots, n\}$ into  horizontal shifts of tiles of the form
$$
\{1\} \, , \, \{1, 1+r \} \, , \, \{1, 1+r , 1+ 2r\} \, , \, \{1, 1+r , 1+ 2r, 1+3r\} \, , \,  \dots \quad .
$$

So let's introduce variables $x[1],x[2],x[3]\dots $ and declare that the weight of the tile $t$ is $x[\#t]$. In particular, the weight of a singleton is $x[1]$.
The weight of a {\it tiling} is the {\bf product} of the weights of all its constituent tiles.

Suppose that $r=2$  and $s=3$,  $n=9$ and the set of  marked unfortunate events happens to be:
$$
\{\pi_{3}-\pi_1=3 \quad, \quad \pi_{5}-\pi_3=3 \quad, \quad \pi_9-\pi_7=3 \} \quad .
$$
Since $\{1,3\}$ and $\{3,5\}$  form a {\bf connected component} $\{1,3,5\}$, and $\{7,9\}$ forms its own connected component, and
the integers not participating in these two connected components are all singletons, This gives the tiling
$$
\{ \{1,3,5\} \, , \, \{7,9\} , \{2\}, \{4\} , \{6\}, , \{8\} \} \quad .
$$



So let's define a polynomial in the (potentially infinite, but for any given $n$ finite) set of variables $x_1,x_2, x_3, \dots$
$$
f_{r,n}(x_1, x_2, x_3 \dots ) \, := \, \sum{T} weight(T) \quad,
$$
where the sum is taken over all the tilings of the board $\{1, 2, \dots, n\}$ by the tiles (i.e. horizontal shifts) of
$$
\{1\}, \{1,1+r\},  \{1,1+r, 1+2r\},  \dots.
$$

For example
$$
f_{3,5}(x_1,x_2,x_3)\, = \, x_{1}^{5}+2 x_{1}^{3} x_{2}+x_{1} x_{2}^{2} \quad,
$$
since 

$\bullet$ There is one tiling with all singletons (horizontal shifts of $\{1\}$:, namely
$$
\{\{1\}  , \{2\} , \{3\}  , \{4\}  , \{5\}  \}
$$
whose weight is ${x_1}^{5}$. 

$\bullet$ There are two tilings with $3$ singletons and one horizontal shifts of $\{1,3\}$, namely
$$
\{ \{1,4\}, \{2\} , \{3\}  , \{5\}  \}  \quad, \quad
\{  \{2,5\}, \{1\},  \{3\}, \{4\}  \}  \quad,
$$
each of whose weight is ${x_1}^{3}x_2$. 

$\bullet$ There is one tiling with $1$ singleton and two  horizontal shifts of $\{1,3\}$, namely
$$
\{ \{1,4\},  \{2,5\} , \{3\} \}\quad ,
$$
whose weight is $x_1 {x_2}^{2}$. 

Using {\it dynamical programming} (see [Z2]) it is very fast to compute these polynomials. Since these {\it weight-enumerators} of tilings are so {\it central} to our approach, we
invite our readers to convince themselves that
$$
f_{3,7}(x_1,x_2,x_3)\, = \,
x_{1}^{7}+4 x_{1}^{5} x_{2}+x_{1}^{4} x_{3}+5 x_{1}^{3} x_{2}^{2}+2 x_{1}^{2} x_{2} x_{3}+2 x_{1} x_{2}^{3}+x_{2}^{2} x_{3} \quad.
$$

{\eightrm This implemented in procedure {\tt fsn(r,n,x)} in our Maple package.}



But there is another tiling present. If you look at the {\bf values} of the violations, you have a natural tilings with tiles
$$
\{1\} \, ,\, \{1, 1+s \}, \, , \, \{1, 1+s , 1+ 2s\} \, , \, \{1, 1+s , 1+ 2s, 1+3s\} \quad,
$$

whose weight-enumerator is $f_{s,n}(x_1, x_2, \dots )$.

For example, look at the pair that comes up in trying to compute $a_{2,3}(9)$
$$
[326195487, \{ \pi_3-\pi_1=3, \pi_5-\pi_3=3, \pi_9-\pi_7=3 \}] \quad,
$$
looking at the {\bf values} we have the tiling
$$
\{ \{3,6,9\}, \{4,7\}, \{1\},\{2\},\{5\},\{6\} \}  \quad.
$$
whose weight is also $x_1^4 x_2 x_3$.


Now write
$$
f_{r,n}(x_1, \dots , x_n) \, = \, \sum C^{(n,r)}_{\alpha} x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \quad,
$$
where the sum ranges over all {\bf integer partitions} $1^{a_1} 2^{a_2} \dots n^{a_n}$, written in {\bf frequency notation}, so $1\cdot a_1 + 2 \cdot a_2 + \dots + n\cdot a_n=n$
(note that  if $r=1$ all partitions show up, but when $r>1$ then some never show up).


{\bf Finally} we are ready to state our `formula' for $a_{r,s}(n)$.
$$
a_{r,s}(n)= \sum C^{(n,s)}_{\alpha} \cdot C^{(n,r)}_{\alpha} \cdot (-1)^{ a_1+a_2+ \dots +a_n -n} a_1! a_2! \cdots a_n! \quad,
$$
where the sum ranges over all partitions of $n$ $\alpha=1^{a_1} 2^{a_2} \dots n^{a_n}$, written in frequency notation. 

Let's explain. Any set of unfortunate events gives rise to two tilings one with tiles $\{1\}, \{1,1+r\}. \{1,1+r,1+2r\}, \dots$ care by the $f_{r,n}$ and one with tiles
$\{1\}, \{1,1+s\}. \{1,1+s,1+2s\}, \dots$, taken care by the $f_{s,n}$. The cardinality of the set of resulting unfortunate events is
$$
a_1 \cdot (1-1)+ a_2 \cdot (2-1)+ a_3 \cdot (3-1) + \dots = n - (a_1+ \dots a_n) \quad,
$$
explaining the exponent of $-1$. Finally, one has to match the {\it `input tiles'} and the {\it `output tiles'}. Of course they have to be of the same size Any of the

$\bullet$ $a_1$ singletons tiles in the input domain can go to any of the $a_1$  singleton tiles of the output domain.

More generally

$\bullet$ Any of the $a_i$  tiles of size $i$ of the input domain can go to any of the $a_i$ tiles of the output domain.

The total number of possible {\it matches} is thus:

$$
a_1! a_2! \cdots a_n! \quad .
$$

So we explained all the ingredients in our `formula'.

A very small tweak gives the formula for $b_{r,s}(n)$.

$$
b_{r,s}(n)= \sum C^{(n,s)}_{\alpha} \cdot C^{(n,r)}_{\alpha} \cdot (-1)^{ a_1+a_2+ \dots +a_n -n} a_1! a_2! \cdots a_n! \cdot 2^{a_2+a_3+ \dots +a_n} \quad,
$$
where the sum ranges over all partitions of $n$ $1^{a_1} 2^{a_2} \dots n^{a_n}$, written in frequency notation. 


Since $b_{r,s}(n)$ counts the number of permutations of $\{1, \dots, n\}$ such that $|\pi_{i+r}-\pi_i| \neq s$, now in each component of the tiling that is not a singleton
can have {\bf two} different direction, `totally up' and `totally' down. This accounts for the extra factor  $2^{a_2+a_3+ \dots +a_n}$ in our formula for $b_{r,s}(n)$.

{\bf Did we answer the enumeration question?}

Well, not quite! According to Herb Wilf's classic essay [W] we need a {\bf polynomial time algorithm} and the number of terms in our `formulas' for $a_{r,s}(n)$ and $b_{r,s}(n)$ is the
number of partitions of $n$ (in fact slightly less, but not significantly less, asymptotically speaking). According to Hardy and Ramanujan they
are about $e^{\pi\sqrt{2n/3}}$ of them. Nevertheless our approach worked very well up to $n=60$ and enabled us to get many more terms
than they were previously in the OEIS, computed by FIDE International Problem Solving master Vaclav Kotesovec (btw these have a nice interpretation as "non-attacking" fairy-chess pieces).
For example to get the first $30$ terms of the sequence $a_{4,4}(n)$, that is {\tt https://oeis.org/A189283}, it took less than three seconds on our modest laptop. Here there are:
\parskip=2pt
\baselineskip=3pt
$$
1, 2, 6, 24, 114, 628, 4062, 30360, 255186, 2414292, 25350954, 292378968, 3673917102, 49928069188, 
$$ 
$$
729534877758, 11403682481112, 189862332575658, 3354017704180052, 62654508729565554, 1233924707891272728, 
$$
$$
25550498290562247438, 554913370184289495780, 12612648556263898345758, 299411750583810718488216, 
$$
$$
7409924986737790240296258, 190856850583975937020030228, 5108283222440036893650974970, 
$$
$$
141870112250977140975169694808, 4082973503947066134710463043374, 121616802487841972048586204012740 \quad .
$$
\baselineskip=14pt
For many terms of such sequences, including $a_{r,s}(n)$ and $b_{r,s}(n)$ with $r>1, s>1$ and $r \neq s$, none of which are yet in the OEIS see the numerous output files in the front of this article:

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/perms.html} \quad .


{\bf The beautiful work of Roberto Taurasu}

We should mention that the case of $b_{r,r}(n)$ for $r=2$ and (larger $r$) has been nicely handled by Roberto Taurasu [T]. We believe that his
approach bears some similarities to ours, but ours is more amenable to using symbolic computations efficiently.

In particular the sequence $b_{2,2}(n)$, currently has $35$ terms listed in {\tt https://oeis.org/A110128} . See our output file

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oResPerms22Va.txt} 

for $60$ terms!


{\bf Polynomial-Time Algorithms for computing $b_{1,s}(n)$ for all $s$}

As pointed out by Enrique Navarrete, the formula for $a_{1,s}(n)$  is very simple, and as we pointed out already implies a very simple
{\bf second-order} recurrence. Dave Robbins [R] (and before him John Riordan) explored the sequence $b_{1,1}(n)$ also using
{\bf inclusion-exclusion} but this time there are no more (potentially) {\it infinitely-many} tiles to keep track of, 
because the tiles in the `output' domain are very simple, they are just sets of the form $\{1\}, \{1,2\}. \{1,2,3\}, dots$, so
one only needs to find the weight-enumerator of tiles according to the weight $x^{TotalNumberOfTiles}$, without recording
the individuality of the tiles. {\bf But} one has to keep track of the {\it total length} of the non-singleton tiles
to one has to introduce another formal variable, let's call it $z$ that keeps track of that. Since each non-singleton tile
can have {\bf two directions}. The details can't be gleanded from the {\it Maple source code} of procedures {\tt Ker1s(s, x, z, K)}.
We believe that it can be proved that these Robbins-style weight-enumerators of tilings can be proved to
be always {\it rational functions}, and being {\it experimental mathematicians} we just guessed them, so {\it officially}
the output of the recurrences for these sequences for $b_{1,s}(n)$ for $s>1$ are only {\it semi-rigorous}. Thanks
to Dave Robbins, our proof of Riordan's recurrence is {\it fully rigorous}.

Since at the {\it end of the day} once you have the Robbins-weight-enumerator $K_s(x,z)$ for enumerating $b_{1,s}(n)$, that is a rational function, one
applies the {\it umbra} $z^n \rightarrow n!$, but this is just like multiplying by $e^{-z}$ and integrating from $0$ to $\infty$.

\vfill\eject

Hence we have

{\bf Semi-Rigorous Theorem}

For $s \geq 1$, there almost exists a rational function of $x$ and $z$ (that Maple can find), let's call it $K_{s}(x,z)$ such that
$$
\sum_{n=0}^{\infty} \, b_{1,s}(n) x^n \, = \, \int_0^{\infty} K_s(x,z) e^{-z} \, dz \quad .
$$
Using the {\bf Almkvist-Zeilberger} algorithm [AZ] one can find an (inhomogeneous)  {\bf differential equation} with {\bf polynomial coefficients},
that translates to a homogeneous linear recurrence with polynomial coefficients for the actual sequence $b_{1,s}(n)$.

See the output files

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oResPermsR1.txt}

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oResPermsR2.txt}

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oResPermsR3.txt}

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/oResPermsR4.txt}

for the sequence $b_{1,1}(n)$, $b_{1,2}(n)$, $b_{1,3}(n)$, $b_{1,4}(n)$, respectively.

{\bf  Combinatorial, Human-Generated, Proofs of the Linear Recurrences satisfied by $a_{1,s}(n)$ and $b_{1,1}(n)$}.

{\bf References}

[AZ] Gert Almkvist and Doron Zeilberger, {\it The Method of Differentiating Under The Integral Sign},
 J. Symbolic Computation {\bf 10} (1990), 571-591. \hfill\break
{\tt https://sites.math.rutgers.edu/\~{} zeilberg/mamarim/mamarimPDF/duis.pdf} \quad .

[KK] Manuel Kauers and Christoph Koutschan, {\it Guessing with little Data}, \hfill\break
{\tt https://arxiv.org/abs/2202.07966} \quad .

[N] Enrique Navarrete,  {\it Generalized K-Shift Forbidden Substrings in Permutations}, \hfill\break
{\tt https://arxiv.org/pdf/1610.06217.pdf}


[Ri] John Riordan, {\it A recurrence for permutations without rising or falling successions},
Ann. Math. Statist. {\bf 36} (1965), 708-710. 


[Ro] David P. Robbins, {\it The probability that neighbors remain neighbors after random rearrangements},
Amer. Math. Monthly {\bf 87} (1980), 122-124. \hfill\break
{\tt https://www.jstor.org/stable/2321990} \quad .

[S11] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A255,  \hfill\break
{\tt https://oeis.org/A000255}.

[S11a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A2464,  \hfill\break
{\tt https://oeis.org/A002464}.

[S12] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A55790, \hfill\break
{\tt  https://oeis.org/A055790}.

[S13] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence  A277609, \hfill\break
{\tt  https://oeis.org/A277609}.

[S14] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence  A277563, \hfill\break
{\tt https://oeis.org/A277563 }.

[S15] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence  A280425, \hfill\break
{\tt  https://oeis.org/A280425 }.

[S22] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189281, \hfill\break
{\tt https://oeis.org/A189281}.

[S22a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A110128, \hfill\break
{\tt https://oeis.org/A110128}.

[S33] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189282, \hfill\break
{\tt https://oeis.org/A189282}.

[S33a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A117574, \hfill\break
{\tt https://oeis.org/A117574}.

[S44] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189283, \hfill\break
{\tt  https://oeis.org/A189283}.

[S44a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189255, \hfill\break
https://oeis.org/A189255

[S55] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189284, \hfill\break
{\tt  https://oeis.org/A189284}.

[S55a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189256, \hfill\break
{\tt  https://oeis.org/A189256}.

[S66] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189285, \hfill\break
{\tt  https://oeis.org/A189285}.

[S66a] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, sequence A189271, \hfill\break
{\tt  https://oeis.org/A189271}.


[SZ] George Spahn and Doron Zeilberger, {\it  Automatic Counting of Generalized Latin Rectangles and Trapezoids},
{\it Enumerative Combinatorics and Applications} {\bf 2(1)} (2022), Article S2R8.\hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/ltrap.html} \quad .

[T] Roberto Taurasu, {\it The Dinner Table Problem: The Rectangular Case}, INTEGERS, {\bf 6} (2006), paper A11. \hfill\break
{\tt https://www.emis.de/journals/INTEGERS/papers/g11/g11.pdf} \quad.


[W] Herbert S. Wilf, {\it What is an answer?},  American Mathematical Monthly
{\bf 89} (1982),  289-292.

[Z1] Doron Zeilberger, {\it The method of cretive telescoping}, J. Symbolic Computation {\bf 11}(1991) 195-204.\hfill\break
{\tt http://sites.math.rutgers.edu/\~{}zeilberg/mamarimY/CreativeTelescoping.pdf}

[Z2]  Doron Zeilberger, {\it Automatic CounTilings}, Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Jan. 20, 2006. \hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/tilings.html} \quad .

[Z3] Doron Zeilberger, {\it Automatic Enumeration of Generalized M\'enage Numbers}, S\'eminaire Lotharingien de Combinatoire, {\bf 71} (2014), article B71a.  \hfill\break
{\tt https://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/menages.html} \quad .


\bigskip
\hrule
\bigskip
George Spahn and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt  gs828 at math dot rutgers dot edu} \quad, \quad {\tt DoronZeil] at gmail dot com}   \quad .


Written: {\bf Oct. 31, 2022}.

\end


