cp's OEIS Frontend

A096351 Number of meaningfully different ways to design a neutral single-elimination tournament with n teams.

%I A096351 #68 Jun 22 2020 18:13:32
%S A096351 1,1,3,3,30,90,315,315,11340,113400,1247400,3742200,48648600,
%T A096351 170270100,638512875,638512875,86837751000,3126159036000,
%U A096351 118794043368000,1187940433680000,49893498214560000,548828480360160000,6311527524141840000
%N A096351 Number of meaningfully different ways to design a neutral single-elimination tournament with n teams.
%C A096351 The result for tournaments is well known (see the references). The recursive formula for general n is new.
%C A096351 From _Laura Monroe_, Jun 11 2020: (Start)
%C A096351 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.
%C A096351 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.
%C A096351 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)
%D A096351 David, H. A. (1988). The Method of Paired Comparisons, 2nd Ed., New York: Oxford University Press. Page 123.
%H A096351 Michel Marcus, <a href="/A096351/b096351.txt">Table of n, a(n) for n = 1..400</a>
%H A096351 Laura Monroe and Vanessa Job, <a href="https://arxiv.org/abs/2005.05387">Computationally Inequivalent Summations and Their Parenthetic Forms</a>, arXiv:2005.05387[cs.DM], 2020.
%H A096351 T. V. Narayana, and F. Agyepong, <a href="http://www.numdam.org/item?id=BURO_1979__32__21_0">Contributions to the Theory of Tournaments IV. A Comparison of Tournaments Through Probabilistic Completion</a>, Cahiers BURO, Paris, 32 (1979), p. 21-34.
%H A096351 D. T. Searls, <a href="http://dx.doi.org/10.1080/01621459.1963.10480688">On the Probability of Winning With Different Tournament Procedures</a>, Journal of the American Statistical Association, Vol. 58 Issue 304, 1963; 1064-1081.
%F A096351 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.
%F A096351 If n = 2^k, then a(n) = n!/(2^(n-1)).
%F A096351 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
%e A096351 From _Laura Monroe_, Jun 11 2020: (Start)
%e A096351 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).
%e A096351 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)).
%e A096351 (End)
%o A096351 (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
%o A096351 (PARI) b(n) = if (n==0, 0, if (n%2, 2*b((n-1)/2)+1, b(n/2) + b(n/2-1))); \\ A268289
%o A096351 a(n) = n!/(2^b(n-1)); \\ _Michel Marcus_, Jun 16 2020
%Y A096351 Cf. A000142, A268289.
%K A096351 nonn
%O A096351 1,3
%A A096351 Lowell Bruce Anderson (landerso(AT)ida.org), Jun 29 2004
%E A096351 a(23) from _Laura Monroe_, Jun 14 2020