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