A343245 Hyperplane-counting upper bound on the number of sorted orders of X+Y for two lists X and Y of length n.

1, 1, 16, 190051, 48563893286, 62416511444764621, 278991478506233367981237, 3489283612532675861618129664796, 104930321415012656258005668476458298401, 6780157485532072442175423032103032983044918034

Offset

0,3

Comments

Grows asymptotically as O(n^(8n)) (Fredman 1976).

Links

Table of n, a(n) for n=0..9.

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

Adjacent sequences: A343242 A343243 A343244 * A343246 A343247 A343248

Keyword

nonn

Author

David Eppstein, Apr 08 2021

Status

approved