A372067 Array read by antidiagonals: T(m,n) (m >= 0, n >= 0) = number of connected row convex (CRC) constraints between an m-element set and an n-element set.

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

Offset: 0

Author

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

Keywords

• nonn
• tabl

Comments

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

Examples

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

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

• 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

Crossrefs

Cf. A100754, A372066, A372068.

Formula

Knuth gives a formula expressing the current array in terms of the array A372066.