login
A343245
Hyperplane-counting upper bound on the number of sorted orders of X+Y for two lists X and Y of length n.
0
1, 1, 16, 190051, 48563893286, 62416511444764621, 278991478506233367981237, 3489283612532675861618129664796, 104930321415012656258005668476458298401, 6780157485532072442175423032103032983044918034
OFFSET
0,3
COMMENTS
Grows asymptotically as O(n^(8n)) (Fredman 1976).
LINKS
Michael L. Fredman (1976). "How good is the information theory bound in sorting?". Theoretical Computer Science. 1 (4): 355-361.
Wikipedia, X+Y sorting.
FORMULA
a(n) = Sum_{i=0..2*n} binomial(2*binomial(n,2)^2 + 2*binomial(n,2), i).
EXAMPLE
For n=2, 2*binomial(n,2)^2 + 2*binomial(n,2) = 4 and binomial(4,0) + ... + binomial(4,2*n) = 16, so a(2)=16.
CROSSREFS
Sequence in context: A364777 A332090 A333863 * A300197 A297386 A051675
KEYWORD
nonn
AUTHOR
David Eppstein, Apr 08 2021
STATUS
approved