A051337 -id:A051337 - cp's OEIS frontend

A000568 Number of outcomes of unlabeled n-team round-robin tournaments.

1, 1, 1, 2, 4, 12, 56, 456, 6880, 191536, 9733056, 903753248, 154108311168, 48542114686912, 28401423719122304, 31021002160355166848, 63530415842308265100288, 244912778438520759443245824, 1783398846284777975419600287232, 24605641171260376770598003978281472

Offset: 0

N. J. A. Sloane

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]

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).

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.
Index entries for sequences related to tournaments

Cf. A006125 for the labeled analog, A051337.

Euler transform of A334335.

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

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 *)

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

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

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 ].

More terms from Vladeta Jovovic

A054946 Number of strongly connected labeled tournaments on n nodes.

Original entry on oeis.org

1, 0, 2, 24, 544, 22320, 1677488, 236522496, 64026088576, 33832910196480, 35262092417856512, 72926863133112198144, 300318571786159783496704, 2467430973323656141183549440, 40490606137578335674252914280448

Offset: 1

N. J. A. Sloane, May 24 2000

For n>=3, a(n) is equal to the number of minimal idempotent generating sets of the semigroup of all singular mappings on {1,2,...,n}. (In the reference below, Howie gave a correspondence between such generating sets and strongly connected labeled tournaments, but stated an incorrect formula for a(n).) - James East, Jan 08 2013

			For n=3, there are two minimal idempotent generating sets for the semigroup of singular mappings on {1,2,3}.  Writing (a,b,c) to indicate the map for which 1->a, etc, the relevant generating sets are: {(1,1,3),(1,2,2),(3,2,3)} and {(2,2,3),(1,3,3),(1,2,1)}.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

N. J. A. Sloane, Table of n, a(n) for n = 1..80 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]
James East and Robert D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014
J. M. Howie, Idempotent generators in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A, 81 (1978), no. 3-4, 317-323.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
Valery A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
Thierry Monteil and Khaydar Nurligareev, Asymptotic probability for connectedness, arXiv:2401.00818 [math.CO], 2024. See p. 12.
N. J. A. Sloane, Table of n, a(n) for n = 1..100
E. M. Wright, The number of irreducible tournaments, Glasgow Math. J., 11 (1970), 97-101.

Cf. A000568 (unlabeled tournaments), A051337 (strongly connected unlabeled tournaments).

with(powseries): powcreate(t(n)=2^(n*(n-1)/2)/n!): s := evalpow(1-1/t): a := tpsform(s, x, 21): for n from 0 to 20 do printf(`%d,`,n!*coeff(a,x,n)) od:
f:=array(0..500); F:=array(0..500); M:=100; f[1]:=1; F[1]:=1; lprint(1,f[1]); for n from 2 to M do F[n]:=2^(n*(n-1)/2); f[n]:=F[n]-add( binomial(n,s)*f[s]*F[n-s], s=1..n-1); lprint(n,f[n]); od:

F[n_] := 2^(n*(n - 1)/2);
a[1] = 1; a[n_] := a[n] = F[n] - Sum[Binomial[n, s]*a[s]*F[n-s], {s, 1, n-1 }];
Array[a, 15] (* Jean-François Alcover, Nov 13 2017, from first formula *)

seq(n)={my(a=vector(n)); for(n=1, n, a[n] = 2^(n*(n-1)/2) - sum(k=1, n-1, binomial(n,k)*2^((n-k)*(n-k-1)/2)*a[k])); a} \\ Andrew Howroyd, Jan 10 2022

Let F(n) = 2^(n*(n-1)/2). Then a(n) is defined by the recurrence a(1)=1, F(n) = a(n) + Sum_{s=1..n-1} binomial(n,s)*a(s)*F(n-s). [Wright]
E.g.f.: 1-1/(1+f(x)) where f(x) = Sum_{m>=1} 2^(m(m-1)/2) x^m / m!.
Wright also gives an asymptotic expansion for a(n).

cp's OEIS Frontend

A000568 Number of outcomes of unlabeled n-team round-robin tournaments.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions