

A096351


Number of meaningfully different ways to design a neutral singleelimination tournament with n teams.


3



1, 1, 3, 3, 30, 90, 315, 315, 11340, 113400, 1247400, 3742200, 48648600, 170270100, 638512875, 638512875, 86837751000, 3126159036000, 118794043368000, 1187940433680000, 49893498214560000, 548828480360160000, 6311527524141840000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

The result for tournaments is well known (see the references). The recursive formula for general n is new.
a(n) is the number of binary operations on n variables concatenated in a pairwise (or cascading) manner, where the operation is commutative, but not associative. This is proven in the Monroe et al. reference, Props. 13, 23, 24. The explicit formula given for general n is new.
One example of such an operation is given in the original sequence definition: the meaningfully different singleelimination tournaments on n teams, where the binary operation is the pairwise game.
Another example is floatingpoint addition: a(n) is the number of computationally equivalent pairwise summations on n floatingpoint numbers, using the IEEE 754 standard for floatingpoint arithmetic in very common use on digital systems in 2020. IEEE 754 guarantees pairwise commutativity of addition, but not associativity, and in fact can give different results for summations with the same summands having different groupings. (End)


REFERENCES

David, H. A. (1988). The Method of Paired Comparisons, 2nd Ed., New York: Oxford University Press. Page 123.


LINKS



FORMULA

a(n) = 1 if n = 1. a(n) = ((n!/((n/2)!*(n/2)!))*(a(n/2))^2)/2 if n is even. a(n) = ((n!/((((n1)/2)!*((n+1)/2)!)))*a((n+1)/2)*a((n1)/2)) if n is odd and > 1.
If n = 2^k, then a(n) = n!/(2^(n1)).
a(n) = n!/(2^A268289(n1)). When the explicit form for A268289 is used, this is also an explicit form.  Laura Monroe, Jun 11 2020


EXAMPLE

For n=3, the a(3)=3 computationally inequivalent pairwise summations on the 3 summands a,b,c are: ((a+b)+c), ((a+c)+b) and ((b+c)+a).
For n=4, the a(4)=3 computationally inequivalent pairwise summations on 4 summands a,b,c,d are: ((a+b)+(c+d)), ((a+c)+(b+d)), and ((a+d)+(b+c)).
(End)


PROG

(PARI) a(n) = if (n==1, 1, if (n%2, n!/((((n1)/2)!*((n+1)/2)!))*a((n+1)/2)*a((n1)/2), ((n!/((n/2)!*(n/2)!))*(a(n/2))^2)/2)); \\ Michel Marcus, Jun 15 2020
(PARI) b(n) = if (n==0, 0, if (n%2, 2*b((n1)/2)+1, b(n/2) + b(n/21))); \\ A268289


CROSSREFS



KEYWORD

nonn


AUTHOR

Lowell Bruce Anderson (landerso(AT)ida.org), Jun 29 2004


EXTENSIONS



STATUS

approved



