The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A096351 Number of meaningfully different ways to design a neutral single-elimination 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.
From Laura Monroe, Jun 11 2020: (Start)
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 single-elimination tournaments on n teams, where the binary operation is the pairwise game.
Another example is floating-point addition: a(n) is the number of computationally equivalent pairwise summations on n floating-point numbers, using the IEEE 754 standard for floating-point 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
Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387[cs.DM], 2020.
T. V. Narayana, and F. Agyepong, Contributions to the Theory of Tournaments IV. A Comparison of Tournaments Through Probabilistic Completion, Cahiers BURO, Paris, 32 (1979), p. 21-34.
D. T. Searls, On the Probability of Winning With Different Tournament Procedures, Journal of the American Statistical Association, Vol. 58 Issue 304, 1963; 1064-1081.
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!/((((n-1)/2)!*((n+1)/2)!)))*a((n+1)/2)*a((n-1)/2)) if n is odd and > 1.
If n = 2^k, then a(n) = n!/(2^(n-1)).
a(n) = n!/(2^A268289(n-1)). When the explicit form for A268289 is used, this is also an explicit form. - Laura Monroe, Jun 11 2020
EXAMPLE
From Laura Monroe, Jun 11 2020: (Start)
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!/((((n-1)/2)!*((n+1)/2)!))*a((n+1)/2)*a((n-1)/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((n-1)/2)+1, b(n/2) + b(n/2-1))); \\ A268289
a(n) = n!/(2^b(n-1)); \\ Michel Marcus, Jun 16 2020
CROSSREFS
Sequence in context: A124244 A351990 A151480 * A367890 A344934 A086667
KEYWORD
nonn
AUTHOR
Lowell Bruce Anderson (landerso(AT)ida.org), Jun 29 2004
EXTENSIONS
a(23) from Laura Monroe, Jun 14 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 19:36 EDT 2024. Contains 372666 sequences. (Running on oeis4.)