A000568 -id:A000568 - cp's OEIS frontend

A350912 Triangle read by rows: T(n,k) is the number of oriented graphs on n unlabeled nodes whose underlying graph is k-regular, k = 0..n-1.

1, 1, 1, 1, 0, 2, 1, 1, 4, 4, 1, 0, 4, 0, 12, 1, 1, 12, 62, 112, 56, 1, 0, 18, 0, 1602, 0, 456, 1, 1, 40, 2062, 32263, 92980, 46791, 6880, 1, 0, 68, 0, 748576, 0, 11210264, 0, 191536, 1, 1, 140, 103827, 19349672, 616991524, 3319462470, 2729098064, 292115960, 9733056

Offset: 1

Andrew Howroyd, Jan 29 2022

The sum of the in-degree and out-degree at each node is k.

a(2*n,2*n-2) is the number of orientations (up to isomorphism) of the n-cocktail party graph. - Pontus von Brömssen, Apr 03 2022

			Triangle begins:
  1;
  1, 1;
  1, 0,  2;
  1, 1,  4,  4;
  1, 0,  4,  0,   12;
  1, 1, 12, 62,  112, 56;
  1, 0, 18,  0, 1602,  0, 456;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..253 (rows 1..22)

Row sums are A350913.
Main diagonal is A000568.
The labeled version is A351263.
Cf. A051031 (graphs), A350910 (digraphs).

A051337 Number of strongly connected tournaments on n nodes.

Original entry on oeis.org

1, 1, 0, 1, 1, 6, 35, 353, 6008, 178133, 9355949, 884464590, 152310149735, 48234782263293, 28304491788158056, 30964247546702883729, 63468402142317299907481, 244785748571033855024746438, 1782909084196274276970660380187, 24602074618353524534591008760307017

Offset: 0

Vladeta Jovovic

A tournament is strongly connected (or strong) if there is a directed path between any pair of points.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 127, Eq. (5.2.4);
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 523.

Andrew Howroyd, Table of n, a(n) for n = 0..50
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968)
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.)
Raphael Yuster, Vector clique decompositions, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), 1221-1238.

Cf. A000568, A054946.

m = 20;
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);
b[n_] := b[n] = (s = 0; Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; s/n!);
B[x_] = Sum[b[k] x^k, {k, 0, m}];
A[x_] = 2 - 1/B[x];
A[x] + O[x]^m // CoefficientList[#, x]& (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A000568 *)

G.f.: = 2 - 1/B(x) where B(x) = g.f. for A000568.

a(0)=1 prepended and a(18)-a(19) from Andrew Howroyd, Sep 10 2018

A259105 Number of nonisomorphic tournaments on n nodes that are not multiples of a nontrivial transitive tournament.

Original entry on oeis.org

1, 0, 1, 3, 11, 54, 455, 6876, 191534, 9733044, 903753247, 154108311109, 48542114686911, 28401423719121848, 31021002160355166835, 63530415842308265093408, 244912778438520759443245823, 1783398846284777975419600095642, 24605641171260376770598003978281471

Offset: 1

N. J. A. Sloane, Jun 23 2015

nonn

Pontus von Brömssen, Table of n, a(n) for n = 1..76
M. Goldberg and J. W. Moon, On the composition of two tournaments, Duke Math. J. 37 (1970), 323-332. The sequence is denoted there as r(n).
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]

Cf. A000568.

Moebius transform of A000568.

More terms from Pontus von Brömssen, Oct 04 2020

A000198 Largest order of automorphism group of a tournament with n nodes.

Original entry on oeis.org

1, 1, 3, 3, 5, 9, 21, 21, 81, 81, 81, 243, 243, 441, 1215, 1701, 1701, 6561, 6561, 6561, 45927, 45927, 45927, 137781, 137781, 229635, 1594323, 1594323, 1594323, 4782969, 4782969, 7971615, 14348907, 33480783, 33480783, 129140163, 129140163, 129140163

Offset: 1

N. J. A. Sloane

J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 81.
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).

Joseph Myers, Table of n, a(n) for n = 1..1000
B. Alspach, A combinatorial proof of a conjecture of Goldberg and Moon, Canad. Math. Bull. 11 (1968), 655-661.
B. Alspach, On point-symmetric tournaments, Canad. Math. Bull., 13 (1970), 317-323. [Annotated copy] See g(n) as defined on page 317 (NOT on page 322).
B. Alspach and J. L. Berggren, On the determination of the maximum order of the group of a tournament, Canad. Math. Bull 16 (1973), 11-14.
J. D. Dixon, The maximum order of the group of a tournament, Canad. Math. Bull. 10 (1967), 503-505.
Index entries for sequences related to tournaments

Cf. A000568, A374164.

a:= proc(n) local t, r; t:= irem(n, 9);
   `if`(3^ilog[3](n)=n, 3^((3^ilog[3](n)-1)/2),
   `if`(irem(n, 5, 'r')=0 and 3^ilog[3](r)=r, 5*3^((5*3^ilog[3](r)-5)/2),
   `if`(irem(n, 7, 'r')=0 and 3^ilog[3](r)=r, 7*3^((7*3^ilog[3](r)-5)/2),
   `if`(irem(n, 3, 'r')=0, 3^r*a(r),
   `if`(t in {1, 2, 4}, a(n-1),
   `if`(t = 8, max(a(n-1), a(5)*a(n-5)),
   `if`(t = 5, max(a(2)*a(n-2), a(5)*a(n-5), a(7)*a(n-7)),
        a(7)*a(n-7) )))))))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Jun 29 2012

a[n_] := a[n] = With[{t = Mod[n, 9]}, Which[ IntegerQ[Log[3, n]], 3^((1/2)*(n-1)),{q, r} = QuotientRemainder[n, 5]; r == 0 && IntegerQ[Log[3, q]], 5*3^((1/2)*(n-5)),{q, r} = QuotientRemainder[n, 7];r == 0 && IntegerQ[Log[3, q]], 7*3^((1/2)*(n-5)), {q, r} = QuotientRemainder[n, 3]; r == 0, 3^q*a[q],MemberQ[{1, 2, 4}, t], a[n-1],t == 8, Max[a[n-1], a[5]*a[n-5]], t == 5, Max[a[2]*a[n-2],a[5]*a[n-5], a[7]*a[n-7]],True, a[7]*a[n-7]]]; Table[a[n], {n, 1, 38}] (* Jean-François Alcover, Nov 12 2012, after Alois P. Heinz *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A000198(n):
    if n <= 7: return (1, 1, 3, 3, 5, 9, 21)[n-1]
    if (r:=n%9) in {0,3,6}:
        return 3**(m:=n//3)*A000198(m)
    elif r in {1,2,4}:
        return A000198(n-1)
    elif r == 5:
        return max(A000198(n-2),5*A000198(n-5),21*A000198(n-7))
    elif r == 7:
        return 21*A000198(n-7)
    elif r == 8:
        return max(A000198(n-1),5*A000198(n-5)) # Chai Wah Wu, Jul 01 2024

a(3^k) = 3^((3^k - 1)/2), a(5*3^k) = 5*3^((5*3^k - 5)/2), a(7*3^k) = 7*3^((7*3^k - 5)/2), and, for all other n, a(n) = max(a(i)a(n-i)) where the maximum is taken over 1 <= i <= n-1 (from Alspach and Berggren (1973) Theorem 4).

a(3r) = (3^r)a(r), a(n) = a(n-1) for n = 1, 2 or 4 mod 9, a(9k+8) = max(a(9k+7), a(5)a(9k+3)), a(9k+5) = max(a(2)a(9k+3), a(5)a(9k), a(7)a(9k-2)), a(9k+7) = a(7)a(9k) (from Alspach and Berggren (1973) Theorem 5).

Edited and extended by Joseph Myers, Jun 28 2012

A002638 a(n) = (number of nonisomorphic nontransitive prime tournaments on n nodes) - Moebius(n).

Original entry on oeis.org

-1, 1, 2, 3, 12, 52, 456, 6873, 191532, 9733032, 903753248, 154108311046, 48542114686912, 28401423719121392, 31021002160355166800, 63530415842308265086523, 244912778438520759443245824, 1783398846284777975419599903948, 24605641171260376770598003978281472

Offset: 1

N. J. A. Sloane

sign

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

Pontus von Brömssen, Table of n, a(n) for n = 1..76
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]
Index entries for sequences related to tournaments

Cf. A000568, A008683, A259106.

a(1) = -1, a(n) = A000568(n) - Sum_{d|n, d!=1, d!=n} a(d) * A000568(n / d). - Sean A. Irvine, Oct 19 2015

a(n) = A259106(n) - A008683(n). - Pontus von Brömssen, Oct 03 2020

Definition clarified by N. J. A. Sloane, Jun 23 2015
More terms from Sean A. Irvine, Oct 19 2015
a(19) from Pontus von Brömssen, Oct 03 2020

A093934 Number of equivalence classes of unlabeled tournaments with n signed nodes.

Original entry on oeis.org

1, 2, 4, 12, 48, 296, 3040, 54256, 1716608, 97213472, 9937755904, 1849103423168, 631027551238656, 397616229914793600, 465313769910614218240, 1016485858155549165160192, 4163516302794478683289989120, 32101177200132015985353543496192, 467507173926886632279989196725442560

Offset: 0

Nadia Heninger and N. J. A. Sloane, Jul 21 2009

nonn

Similar to unlabeled tournaments (A000568), with the additional feature that each node carries either a plus sign or a minus sign.

Equivalence is defined with respect to the action of S_n on the nodes (and the induced action on the edges).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms n = 0..30 from N. J. A. Sloane)

Cf. A000568.

with(combinat); with(numtheory);
for n from 1 to 30 do
p:=partition(n); s:=0:
for k from 1 to nops(p) do
# get next partition of n
ex:=1:
# discard if there is an even part
for i from 1 to nops(p[k]) do if p[k][i] mod 2=0 then ex:=0:break:fi: od:
# analyze an odd partition
if ex=1 then
# convert partition to list of sizes of parts
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:
# get number of parts
nump := add(a(i),i=1..n);
# get multiplicity
c:=1: for i from 1 to n do c:=c*a(i)!*i^a(i): od:
# get exponent t(j)
tj:=0;
for i from 1 to n do for j from 1 to n do
if a(i)>0 and a(j)>0 then tj:=tj+a(i)*a(j)*gcd(i,j); fi;
od: od:
s:=s + (1/c)*2^((tj+nump)/2);
fi:
od;
A[n]:=s;
od:
[seq(A[n],n=1..30)];

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_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];
a[n_] := Module[{s = 0}, Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]* 2^Length[p]], {p, IntegerPartitions[n]}]; s/n!];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 07 2021, 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^(#p+edges(p)))); s/n!} \\ Andrew Howroyd, Feb 29 2020

from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A093934(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

a(n) = Sum_{j} (1/(Product (r^(j_r) (j_r)!))) * 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 ].

A259106 Number of nonisomorphic nontransitive prime tournaments on n nodes.

Original entry on oeis.org

0, 0, 1, 3, 11, 53, 455, 6873, 191532, 9733033, 903753247, 154108311046, 48542114686911, 28401423719121393, 31021002160355166801, 63530415842308265086523, 244912778438520759443245823, 1783398846284777975419599903948, 24605641171260376770598003978281471

Offset: 1

N. J. A. Sloane, Jun 23 2015

nonn

Pontus von Brömssen, Table of n, a(n) for n = 1..76
M. Goldberg and J. W. Moon, On the composition of two tournaments, Duke Math. J. 37 (1970), 323-332. The sequence is denoted there as p(n).
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]

Cf. A000568, A002638, A259105, A008683.

a(n) = A002638(n) + mu(n) = A002638(n) + A008683(n). [Corrected by Georg Fischer, Jun 05 2024]

For n>1, a(n) = A259105(n) - Sum_{divisors d of n, 1A000568(n/d). - Pontus von Brömssen, Oct 04 2020

More terms from Pontus von Brömssen, Oct 04 2020

A007150 2-part of number of tournaments on n nodes.

Original entry on oeis.org

0, 0, 1, 2, 2, 3, 3, 5, 4, 6, 5, 7, 6, 7, 7, 10, 8, 9, 9, 12, 10, 11, 11, 14, 12, 14, 13, 15, 14, 17, 15, 19, 16, 20, 17, 19, 18, 19, 19, 26, 20, 22, 21, 23, 22, 23, 23, 30, 24, 26, 25, 28, 26, 27, 27, 30, 28, 30, 29, 33, 30, 31, 31, 35, 32, 34, 33, 38, 34, 37, 35, 38, 36, 38, 37, 39

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Chai Wah Wu, Table of n, a(n) for n = 1..141
Steven C. Cater and Robert W. Robinson, Exponents of 2 in the numbers of unlabeled graphs and tournaments, Congressus Numerantium, 82 (1991), pp. 139-155.
Steven C. Cater and Robert W. Robinson, Exponents of 2 in the numbers of unlabeled graphs and tournaments, Preprint. (Annotated scanned copy)
Index entries for sequences related to tournaments

Power of 2 dividing A000568(n). Cf. A007814.

A000568 = Cases[Import["https://oeis.org/A000568/b000568.txt", "Table"], {, }][[All, 2]];
IntegerExponent[#, 2]& /@ A000568 // Rest (* Jean-François Alcover, Jan 06 2020 *)

from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A007150(n): return (~(m:=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)))) & m-1).bit_length() # Chai Wah Wu, Jul 01 2024

a(n) = A007814(A000568(n)). - Michel Marcus, Jan 06 2020

More terms from A000568 by Jean-François Alcover, Jan 06 2020

A059735 Number of complementary pairs of tournaments on n nodes.

Original entry on oeis.org

1, 1, 2, 3, 10, 34, 272, 3528, 97144, 4870920, 452016608, 77054901728, 24271105072736, 14200712295904928, 15510501136026729216, 31765207922047709885696, 122456389219489134370435456, 891699423142395494501906828160, 12302820585630191716774996205431296

Offset: 1

N. J. A. Sloane, Feb 09 2001

Andrew Howroyd, Table of n, a(n) for n = 1..50
Nevena Francetić, Sarada Herke, Ian M. Wanless, Parity of Sets of Mutually Orthogonal Latin Squares, arXiv:1703.04764 [math.CO], 2017. See Section 4.1.
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000568, A002785.

A000568 = Cases[Import["https://oeis.org/A000568/b000568.txt", "Table"], {, }][[All, 2]];
A002785 = Cases[Import["https://oeis.org/A002785/b002785.txt", "Table"], {, }][[All, 2]];
a[n_] := (A000568[[n + 1]] + A002785[[n]])/2;
Array[a, 19] (* Jean-François Alcover, Aug 27 2019 *)

Average of A000568 and A002785.

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005

Terms a(18) and beyond from Andrew Howroyd, Sep 17 2018

A374164 Number of unlabeled n-vertex tournaments with the maximum number (A000198(n)) of automorphisms.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 4

Offset: 1

Pontus von Brömssen, Jun 29 2024

Index entries for sequences related to tournaments.

Cf. A000198, A000568.

cp's OEIS Frontend

A350912 Triangle read by rows: T(n,k) is the number of oriented graphs on n unlabeled nodes whose underlying graph is k-regular, k = 0..n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A051337 Number of strongly connected tournaments on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A259105 Number of nonisomorphic tournaments on n nodes that are not multiples of a nontrivial transitive tournament.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A000198 Largest order of automorphism group of a tournament with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A002638 a(n) = (number of nonisomorphic nontransitive prime tournaments on n nodes) - Moebius(n).

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A093934 Number of equivalence classes of unlabeled tournaments with n signed nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A259106 Number of nonisomorphic nontransitive prime tournaments on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A007150 2-part of number of tournaments on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs