A372066 Array read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of reduced connected row convex (RCRC) constraints between an m-element set and an n-element set.

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

Offset

1,5

Comments

See the Knuth "Notes" link for much more information about these sequences. The present sequence is called "table0" in Part 1 of the Notes.

References

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

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

Links

Table of n, a(n) for n=1..55.

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

Formula

Knuth gives a formula expressing the array A372367 in terms of the current array. He also reports that there is strong experimental evidence that the n-th term of row m in the current array is a polynomial of degree 2*m-2 in n.

Example

The initial antidiagonals are:
   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,
   ...
The array begins:
   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, ...
   ...

Crossrefs

Cf. A100754, A372067, A372068.

Sequence in context: A082110 A275526 A141597 * A176561 A176284 A154233

Adjacent sequences: A372063 A372064 A372065 * A372067 A372068 A372069

Keyword

nonn,tabl

Author

N. J. A. Sloane, May 12 2024, based on emails from Don Knuth, May 06 2024 and May 08 2024

Status

approved