login
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.
3
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.
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
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