|
|
A000568
|
|
Number of outcomes of unlabeled n-team round-robin tournaments.
(Formerly M1262 N0484)
|
|
23
|
|
|
1, 1, 1, 2, 4, 12, 56, 456, 6880, 191536, 9733056, 903753248, 154108311168, 48542114686912, 28401423719122304, 31021002160355166848, 63530415842308265100288, 244912778438520759443245824, 1783398846284777975419600287232, 24605641171260376770598003978281472
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Harary and Palmer give incorrect values for a(24) and a(25); the correct values are a(24) = 195692027657521876084316842660833482785173437775365039898624 and a(25) = 131326696677895002131450257709457767457170027052967027982788816896. - Vladeta Jovovic, Apr 08 2001
|
|
REFERENCES
|
R. L. Davis, Structure of dominance relations, Bull. Math. Biophys., 16 (1954), 131-140.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 157 and 523.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 126 and 245.
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 87.
K. B. Reid and L. W. Beineke "Tournaments", pp. 169-204 in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Vladimír Müller, Jaroslav Nešetřil, and Jan Pelant, Either tournaments or algebras?, Discrete Math. 11 (1975), 37-66. [Annotated copy] See table 1 on page 65.
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
|
|
FORMULA
|
Davis's formula: a(n) = Sum_{j} (1/(Product (k^(j_k) (j_k)!))) * 2^{t_j},
where j runs through all partitions of n into odd parts, say with j_1 parts of size 1, j_3 parts of size 3, etc.,
and t_j = (1/2)*[ Sum_{r=1..n, s=1..n} j_r j_s gcd(r,s) - Sum_{r} j_r ].
|
|
MAPLE
|
with(combinat):with(numtheory): for n from 1 to 30 do p:=partition(n): s:=0:for k from 1 to nops(p) do ex:=1:for i from 1 to nops(p[k]) do if p[k][i] mod 2=0 then ex:=0:break:fi:od:
if ex=1 then q:=convert(p[k], multiset): for i from 1 to n do a(i):=0:od:for i from 1 to nops(q) do a(q[i][1]):=q[i][2]:od:
c:=1:ord:=1:for i from 1 to n do c:=c*a(i)!*i^a(i): if a(i)<>0 then ord:=lcm(ord, i):fi:od: g:=0:for d from 1 to ord do if ord mod d=0 then g1:=0:for del from 1 to n do if d mod del=0 then g1:=g1+del*a(del):fi:od:g:=g+phi(ord/d)*g1*(g1-1):fi:od: s:=s+2^(g/ord/2)/c:fi:
|
|
MATHEMATICA
|
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2], {i, 1, Length[v]}];
oddp[v_] := (For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1);
a[n_] := a[n] = (s = 0; Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; s/n!);
|
|
PROG
|
(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
a(n) = {my(s=0); forpart(p=n, if(oddp(p), s+=permcount(p)*2^edges(p))); s/n!} \\ Andrew Howroyd, Oct 22 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|