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,5

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.

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=0..65.

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 current array in terms of the array A372066.

Example

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, ...
   ...

Crossrefs

Cf. A100754, A372066, A372068.

Sequence in context: A099594 A255256 A328887 * A299906 A117401 A144324

Adjacent sequences: A372064 A372065 A372066 * A372068 A372069 A372070

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