Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints
D. E. Knuth
May 6 2024


Part 1, the arrays "table0" (A372066) and "table" (A372067)
-----------------------------------------------------------

The first one, "table0" (now A372066), has entries T0[m,n] of "offset (1,1)";
that is, the first row is T0[1,n], the second is T0[2,n], and so on.

The second one, "table" (now A372067), has entries T[m,n] of "offset (0,0)";
that is, the first row is T[0,n], the second is T[1,n], and so on.

The second is obtained from the first by the identity
 \sum_{m,n\ge0} T[m,n] w^m/m! z^n/n!  =
          E^(w+z) (1 + \sum_{m,n\ge1} T0[m,n] w^m/m! z^n/n!.

What are these numbers? In the second table, T[m,n] is "the number
of CRC constraints between an m-element set and an n-element set",
where a CRC stands for "connected row convex". The class of binary
relations called CRC constraints was introduced in the paper

 Yves Deville, Olivier Barette, Pascal Van Hentenryck,
    "Constraint satisfaction over connected row-convex constraints."
   Artificial Intelligence 109 (1999), 243-271.

(They proved that a constraint satisfaction problem with only CRC
constraints can be efficiently solved.)

In the first table, T0[m,n] is "the number of RCRC constraints
between an m-element set and an n-element set", where an RCRC constraint
is a CRC constraint that has no all-zero rows or all-zero columns.
RCRC is an abbreviation for "reduced connected row convex".

An RCRC constraint is characterized by the following three rules:

 (1) No row or column is entirely zero.
 (2) The 1s in each row, and the 1s in each column, are consecutive.
 (3) The 1s are "kingwise connected": Between any two 1s, anywhere in the
     matrix, there's a path of 1s such that each step changes the coordinates
     of the cells by either $(0,\pm1)$  or $(\pm1,0)$ or $(\pm1,\pm1)$.

For example, the T0[3,3]=90 RCRC constraints of size 3x3 can be grouped
into 20 equivalence classes under the eight symmetries of a square:
>
>  100
>  010
>  001 (2)
>
>  110      110      100
>  010      001      011
>  001 (8)  001 (4)  010 (4)
>
>  111      111      110      110      110      110      010
>  010      001      110      011      011      010      111
>  010 (4)  001 (4)  001 (4)  010 (8)  001 (4)  011 (4)  010 (1)
>
>  111      111      110      100
>  110      110      111      111
>  100 (4)  010 (8)  010 (4)  011 (8)
>
>  111      111      011
>  111      111      111
>  100 (8)  010 (4)  110 (2)
>
>  111
>  111
>  110 (4)
>
>  111
>  111
>  111 (1)
>
These have been grouped according to the total number of 1s.

If we take any CRC constraint and delete its all-zero rows and
its all-zero columns, we get an RCRC constraint (typically having
fewer rows and/or columns). Figure 1 of the paper by Deville et al
shows all-zero rows and all-zero columns in gray. For instance, one
of the examples in their illustration is

> 011101           
> 001101          1111
> 000000          0111
> 000101     =>   0011
> 000100          0010
> 000100          0010

Deville et al. gave an interesting alternative characterization of RCRC
constraints in Theorem 25 of their paper: Given any matrix $M$ of 0s and 1s,
we can form four denser matrices $M^{NE}$, $M^{NW}$, $M^{SE}$, and $M^{SW}$
by changing 0 to 1 whenever the 0 lies respectively north-east, north-west,
south-east, and south-west of a 1 in $M$. Then $M$ is RCRC if and only if
$M = M^{NE} \cap M^{NW} \cap M^{SE} \cap M^{SW}$, the pointwise intersection
of all four of these matrices.

For instance, suppose we have

>     000110
>     000111
>     001000
> M = 111000 .
>     011000
>     001000

Then

>          111111            111111            000111            111110
>          111111            111111            000111            111111
>          111111            111000            001111            111111
> M^{NE} = 111111 ; M^{NW} = 111000 ; M^{SE} = 111111 ; M^{SW} = 111111 .
>          011111            111000            111111            111111
>          001111            111000            111111            111111

Each of the four matrices being intersected is like a Young tableau, or
a Ferrers graph, defined by one side of a corner-to-corner path, but
possibly rotated. In this case M is the intersection of those four;
hence M is RCRC.

Another nice characterization was stated without proof on page 262 of

 Peter Jeavons, David Cohen, Martin C. Cooper,
   "Constraints, consistency and closure".
  Artificial Intelligence 101 (1998), 251-265.

Namely, a binary relation R is CRC if and only if it has the following
property: x1 R y1 and x2 R y2 and x3 R y3 implies <x1 x2 x3> R <y1 y2 y3>,
where <x y z> is the ternary median operation.

The kingwise-connected feature means that this isn't quite like enumerating
a class of polyominoes. But every RCRC matrix is essentially obtained
by stringing together a chain of convex polyominoes that touch at
articulation points, which are corners of diagonally adjacent bounding boxes.

My experimental program found empirically that, for fixed $m$, T0[m,n] is
a polynomial of degree 2m-2 in n. For example, T0[2,n] = 2n^2-1, and 
 T0[3,n] = n^4 +2n^3/3-n^2/2-13n/6+2.

The leading coefficient of this polynomial can, of course, be determined 
from the (constant) value of the $(2n-2)$nd differences with respect to $n$; those constants are
1, 4, 24, 136, 720, 3624, 17584, for m=1, 2, 3, 4, 5, 6, 7.
Surprisingly, this is A153337 in the OEIS, which is related to zig-zag
paths from corner to corner of a square!

So far this property of table0 is merely a conjecture, but the evidence is overwhelming.

---------- cut here for the first two tables --------------------------------------
A372066:
table0={
{1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 7, 17, 31, 49, 71, 97, 127, 161},
{1, 17, 90, 284, 687, 1411, 2592, 4390, 6989},
{1, 31, 284, 1398, 4861, 13555, 32436, 69350, 135985},
{1, 49, 687, 4861, 23020, 83858, 253876, 669660, 1587491},
{1, 71, 1411, 13555, 83858, 386774, 1445748, 4613486, 13010537},
{1, 97, 2592, 32436, 253876, 1445748, 6539320, 24831150, 82162821},
{1, 127, 4390, 69350, 669660, 4613486, 24831150, 110639796, 424473531},
{1, 161, 6989, 135985, 1587491, 13010537, 82162821, 424473531, 1868934548}}

### When read by antidiagonals this is
### [1]
### [1, 1]
### [1, 7, 1]
### [1, 17, 17, 1]
### [1, 31, 90, 31, 1]
### [1, 49, 284, 284, 49, 1]
### [1, 71, 687, 1398, 687, 71, 1]
### [1, 97, 1411, 4861, 4861, 1411, 97, 1]
### [1, 127, 2592, 13555, 23020, 13555, 2592, 127, 1]
### [1, 161, 4390, 32436, 83858, 83858, 32436, 4390, 161, 1]



A372067:
table={
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512},
{1, 4, 16, 56, 176, 512, 1408, 3712, 9472, 23552},
{1, 8, 56, 289, 1231, 4623, 15887, 51103, 156159, 457983},
{1, 16, 176, 1231, 6655, 30553, 125197, 471581, 1664061, 5572733},
{1, 32, 512, 4623, 30553, 166186, 790250, 3402874, 13570090, 50887322},
{1, 64, 1408, 15887, 125197, 790250, 4283086, 20750168, 92177312, 382005370},
{1, 128, 3712, 51103, 471581, 3402874, 20750168, 111803585,  547505091, 2483709151},
{1, 256, 9472, 156159, 1664061, 13570090, 92177312, 547505091, 2932069965, 14453287777},
{1, 512, 23552, 457983, 5572733, 50887322, 382005370, 2483709151, 14453287777, 76964939964}}



### When read by antidiagonals this is
### [1]
### [1, 1]
### [1, 2, 1]
### [1, 4, 4, 1]
### [1, 8, 16, 8, 1]
### [1, 16, 56, 56, 16, 1]
### [1, 32, 176, 289, 176, 32, 1]
### [1, 64, 512, 1231, 1231, 512, 64, 1]
### [1, 128, 1408, 4623, 6655, 4623, 1408, 128, 1]
### [1, 256, 3712, 15887, 30553, 30553, 15887, 3712, 256, 1]
### [1, 512, 9472, 51103, 125197, 166186, 125197, 51103, 9472, 512, 1]



Part 2, the arrays "tab0" (A100754) and "tab" (A372068)
-------------------------------------------------------

The second two tables are analogous to the first two, but now, instead of CRC (and RCRC) relations, 
the relations are max-and-min-closed (and restricted max-and-min-closed). The latter kind of
relations are a subset of the former kind.

OEIS already contains the corresponding matrices for binary relations that
are simply max-closed: A099594 does max-closed (and also parades, etc.!)
as noted there, and A272644 covers the matrices of max-closed relations
that have no all-zero rows or columns.

OEIS also already has the third table, tab0 below, in A100754. But there it's called
a triangle read by rows, while in tab0 it's an array read by antidiagonals!
My tab0[m,n] is T[m+n,n] in A100754. So in that sequence one could
simply comment that T[m+n,n] is the number of reduced binary relations
between {1,...,m} and {1,...,n} that are both min-closed and max-closed.

The numbers in "tab" (now A372068) do, however, seem to be a worthwhile new sequence.
They are related to those of tab0 just as the first two tables were related, that is,

 \sum_{m,n\ge0} tab[m,n] w^m/m! z^n/n!  =
          E^(w+z) (1 + \sum_{m,n\ge1} tab0[m,n] w^m/m! z^n/n!.

As before, there is overwhelming evidence that tab0[m,n] for fixed m
is a polynomial of degree 2m-2 in n. And the coefficient of n^{2m-2} this
time arrears to be a Catalan number, divided by (2m-2)!. For example, tab0[4,n]
is equal to 5{n\choose6} + linear multiples of {n\choose5} thru {n\choose0};
tab0[5,n] is 14{n\choose8} + l.o.t.; tab0[8,n] is 42{n\choose10} + l.o.t.; etc.

In Part 1 there is a detailed explanation of why table0[3,3]=90. It might be
useful, for A100754, to explain why tab0[3,3]=29 ... which in the language
of that triangle, T[6,3]=29, because T[m+n,n] is the number of reduced
matrices for min-and-max-closed constraints. Those 29 matrices can be
grouped into 13 equivalence classes under the four relevant symmetries:

>
>  100
>  010
>  001 (1)
>
>  110      110   
>  010      001   
>  001 (4)  001 (2)
>
>  111      110      110      110   
>  001      110      011      010   
>  001 (2)  001 (2)  001 (2)  011 (2)
>
>  100      100
>  110      111
>  111 (2)  011 (4)
>
>  100      110   
>  111      111   
>  111 (4)  011 (1)
>
>  110
>  111
>  111 (2)
>
>  111
>  111
>  111 (1)

--------------- cut here for the second two tables ----------------------------
A100754:
tab0={
{1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 4, 8, 13, 19, 26, 34, 43, 53},
{1, 8, 29, 73, 151, 276, 463, 729, 1093},
{1, 13, 73, 266, 749, 1781, 3758, 7253, 13061},
{1, 19, 151, 749, 2762, 8321, 21659, 50471, 107833},
{1, 26, 276, 1781, 8321, 31004, 97754, 271125, 679355},
{1, 34, 463, 3758, 21659, 97754, 367285, 1196665, 3478915},
{1, 43, 729, 7253, 50471, 271125, 1196665, 4526470, 15118415},
{1, 53, 1093, 13061, 107833, 679355, 3478915, 15118415, 57500480}}


### When read by antidiagonals this is
### [1]
### [1, 1]
### [1, 4, 1]
### [1, 8, 8, 1]
### [1, 13, 29, 13, 1]
### [1, 19, 73, 73, 19, 1]
### [1, 26, 151, 266, 151, 26, 1]
### [1, 34, 276, 749, 749, 276, 34, 1]
### [1, 43, 463, 1781, 2762, 1781, 463, 43, 1]
### [1, 53, 729, 3758, 8321, 8321, 3758, 729, 53, 1]



A372068:
tab={
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512},
{1, 4, 13, 38, 104, 272, 688, 1696, 4096, 9728},
{1, 8, 38, 147, 506, 1612, 4856, 14016, 39104, 106112},
{1, 16, 104, 506, 2103, 7887, 27477, 90498, 285072, 865856},
{1, 32, 272, 1612, 7887, 34088, 134825, 498465, 1746830, 5859404},
{1, 64, 688, 4856, 27477, 134825, 597539, 2451038, 9455182, 34687916},
{1, 128, 1696, 14016, 90498, 498465, 2451038, 11055950, 46570858, 185484836},
{1, 256, 4096, 39104, 285072, 1746830, 9455182, 46570858, 212833803, 914854829},
{1, 512, 9728, 106112, 865856, 5859404, 34687916, 185484836, 914854829, 4223468802}}


### When read by antidiagonals this is
### [1]
### [1, 1]
### [1, 2, 1]
### [1, 4, 4, 1]
### [1, 8, 13, 8, 1]
### [1, 16, 38, 38, 16, 1]
### [1, 32, 104, 147, 104, 32, 1]
### [1, 64, 272, 506, 506, 272, 64, 1]
### [1, 128, 688, 1612, 2103, 1612, 688, 128, 1]
### [1, 256, 1696, 4856, 7887, 7887, 4856, 1696, 256, 1]
### [1, 512, 4096, 14016, 27477, 34088, 27477, 14016, 4096, 512, 1]