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

Author

David Eppstein, Apr 08 2021

Keywords

• nonn

Comments

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

Examples

			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.
		

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