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]