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
a(n) appears to be the number of even graphs with n vertices; see comment in A334335. - Pontus von Brömssen, May 05 2020 [This has been proved by Royle et al. 2023. - Pontus von Brömssen, Apr 06 2022]
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
Keith Briggs, Table of n, a(n) for n = 0..76
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Cropper, Sebrina Ruth, Ranking Score Vectors of Tournaments (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies.
R. L. Davis, Structure of dominance relations, Bull. Math. Biophys., 16 (1954), 131-140. [Annotated scanned copy]
D. S. Dummit, E. P. Dummit, and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Robert A. Laird and Brandon S. Schamp, Calculating Competitive Intransitivity: Computational Challenges, The American Naturalist (2018), Vol. 191, No. 4, 547-552.
Robert A. Laird and Brandon S. Schamp, Exploring the performance of intransitivity indices in predicting coexistence in multispecies systems, Journal of Ecology (2018) Vol. 106, Issue 3, 815-825.
Brendan McKay, Combinatorial Data.
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968), see page 115.
J. W. Moon and M. Goldberg, On the composition of two tournaments, Duke Mathematical Journal, vol.37, no.2 (1970), pp.323-332. (subscription required)
J. W. Moon and M. Goldberg, On the composition of two tournaments, Duke Mathematical Journal 37.2 (1970): 323-332. [Annotated scans of pages 331 and 332 only]
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.
Gordon F. Royle, Cheryl E. Praeger, S. P. Glasby, Saul D. Freedman, and Alice Devillers, Tournaments and even graphs are equinumerous, Journal of Algebraic Combinatorics 57 (2023), 515-524; arXiv version, arXiv:2204.01947 [math.CO], 2022.
N. J. A. Sloane, Annotated scan of John Moon's tables of tournaments on up to 6 nodes
N. J. A. Sloane, Illustration of first 5 terms
N. J. A. Sloane, A second Maple program for A000568
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.)
Eric Weisstein's World of Mathematics, Tournament
Raphael Yuster, On tournament inversion, arXiv:2312.01910 [math.CO], 2023.
Tianwei Zhang and Stefan Szeider, Searching for Smallest Universal Graphs and Tournaments with SAT, 29th Int'l Conf. Princ. Prac. Constraint Programming (CP 2023) Art. No. 39, 39:1-39:20.
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:
od: print(n, s); od: # Vladeta Jovovic
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!);
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 13 2017, after Andrew Howroyd *)
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
(Python)
from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000568(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r, s) for r, s in product(p.keys(), repeat=2))-sum(p.values())>>1), prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n) if all(q&1 for q in p))) # Chai Wah Wu, Jul 01 2024
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic
STATUS
approved