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

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

References

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

Links

• 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

Crossrefs

Cf. A000568, A374164.

Programs

Maple

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

Mathematica

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

Python

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

Formula

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

Extensions

Edited and extended by Joseph Myers, Jun 28 2012