A007747 -id:A007747 - cp's OEIS frontend

A047656 a(n) = 3^((n^2-n)/2).

1, 1, 3, 27, 729, 59049, 14348907, 10460353203, 22876792454961, 150094635296999121, 2954312706550833698643, 174449211009120179071170507, 30903154382632612361920641803529, 16423203268260658146231467800709255289, 26183890704263137277674192438430182020124347

Offset: 0

N. J. A. Sloane

The number of outcomes of a chess tournament with n players.
For n >= 1, a(n) is the size of the Sylow 3-subgroup of the Chevalley group A_n(3) (sequence A053290). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001
The number of binary relations on an n-element set that are both reflexive and antisymmetric. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
The sequence a(n+1) = [1,3,27,729,59049,14348907,...] is the Hankel transform (see A001906 for definition) of A047891 = 1, 3, 12, 57, 300, 1586, 9912, ... . - Philippe Deléham, Aug 29 2006
a(n) is the number of binary relations on a set with n elements that are total relations, i.e., for a relation on a set X it holds for all a and b in X that a~b or b~a (or both). E.g., a(2) = 3 because there are three total relations on a set with two elements: {(a,a),(a,b),(b,a),(b,b)}, {(a,a),(a,b),(b,b)}, and {(a,a),(b,a),(b,b)}. - Geoffrey Critzer, May 23 2008
The number of semicomplete digraphs (or weak tournaments) on n labeled nodes. - Rémy-Robert Joseph, Nov 12 2012
The number of n X n binary matrices A that have a(i,j)=0 whenever a(j,i)=1 for i!=j and zeros on the diagonal. We need only consider the (n^2-n)/2 non-diagonal entry pairs . Since each pair is of the form <0,0>, <0,1>, or <1,0>, a(n) = 3^((n^2-n)/2). - Dennis P. Walsh, Apr 03 2014
a(n) is the number of symmetric (-1,0,1)-matrices of dimension (n-1) X (n-1). - Eric W. Weisstein, Jan 03 2021

			The a(2)=3 binary 2 X 2 matrices are [0 0; 0 0], [0 1; 0 0], and [0 0; 1 0]. - _Dennis P. Walsh_, Apr 03 2014

P. A. MacMahon, Chess tournaments and the like treated by the calculus of symmetric functions, Coll. Papers I, MIT Press, 344-375.

Vincenzo Librandi, Table of n, a(n) for n = 0..65
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
T. R. Hoffman and J. P. Solazzo, Complex Two-Graphs via Equiangular Tight Frames, arXiv preprint arXiv:1408.0334 [math.CO], 2014.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Eric Weisstein's World of Mathematics, (-1,0,1)-Matrix
Eric Weisstein's World of Mathematics, Symmetric Matrix
Index entries for sequences related to tournaments

Cf. A007747.

seq(3^binomial(n, 2), n=0..12); # Zerinvary Lajos, Jun 16 2007
seq(3^((n^2-n)/2), n=0..14);

Table[3^((n^2 - n)/2), {n, 0, 14}] (* Eric W. Weisstein, Jan 03 2021 *)
3^Table[Binomial[n, 2], {n, 0, 14}] (* Eric W. Weisstein, Jan 03 2021 *)
3^Binomial[Range[0, 14], 2] (* Eric W. Weisstein, Jan 03 2021 *)
Table[Count[Tuples[{-1, 0, 1}, {n, n}], ?SymmetricMatrixQ], {n, 3}] (* _Eric W. Weisstein, Jan 03 2021 *)

a(n)=3^binomial(n+1,2) \\ Charles R Greathouse IV, Apr 17 2012

a(n+1) is the determinant of an n X n matrix M_(i, j) = C(3*i,j). - Benoit Cloitre, Aug 27 2003
Sequence is given by the Hankel transform (see A001906 for definition) of A007564 = {1, 1, 4, 19, 100, 562, 3304, ...}; example: det([1, 1, 4, 19; 1, 4, 19, 100; 4, 19, 100, 562; 19, 100, 562, 3304]) = 3^6 = 729. - Philippe Deléham, Aug 20 2005
The sequence a(n+1) = [1,3,27,729,59049,14348907,...] is the Hankel transform (see A001906 for definition) of A047891 = 1, 3, 12, 57, 300, 1586, 9912, ... . - Philippe Deléham, Aug 29 2006
a(n) = 3^binomial(n,2). - Zerinvary Lajos, Jun 16 2007
G.f. A(x) satisfies: A(x) = 1 + x * A(3*x). - Ilya Gutkovskiy, Jun 04 2020
a(n) = a(n-1)*3^(n-1), a(0) = 1. - Mehdi Naima, Mar 09 2022

A000571 Number of different score sequences that are possible in an n-team round-robin tournament.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, 158808, 531469, 1799659, 6157068, 21258104, 73996100, 259451116, 915695102, 3251073303, 11605141649, 41631194766, 150021775417, 542875459724, 1972050156181, 7189259574618, 26295934251565, 96478910768821, 354998461378719, 1309755903513481

Offset: 0

N. J. A. Sloane

A tournament is a complete graph with one arrow on each edge; the score of a node is its out-degree; a(n) is number of different score sequences when there are n nodes.
Also number of nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 1, p_i >= 0, i=1, ..., n.
Also number of score sequences of length n: weakly increasing sequences a[0,1,...,n-1] where sum(j=0..k, a[j]) >= k*(k+1)/2 and sum(j=0..n-1, a[j]) = (n+1)*n/2; see example. - Joerg Arndt, Mar 29 2014

			a(3)=2, since either one node dominates [ 2,1,0 ] or each node defeats the next [ 1,1,1 ].
G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...
where the logarithm begins:
log(A(x)) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 +...+ A145855(n)*x^n/n +...
From _Joerg Arndt_, Mar 29 2014: (Start)
The a(6) = 22 score sequences of length 6 are:
  01: [ 0 1 2 3 4 5 ]
  02: [ 0 1 2 4 4 4 ]
  03: [ 0 1 3 3 3 5 ]
  04: [ 0 1 3 3 4 4 ]
  05: [ 0 2 2 2 4 5 ]
  06: [ 0 2 2 3 3 5 ]
  07: [ 0 2 2 3 4 4 ]
  08: [ 0 2 3 3 3 4 ]
  09: [ 0 3 3 3 3 3 ]
  10: [ 1 1 1 3 4 5 ]
  11: [ 1 1 1 4 4 4 ]
  12: [ 1 1 2 2 4 5 ]
  13: [ 1 1 2 3 3 5 ]
  14: [ 1 1 2 3 4 4 ]
  15: [ 1 1 3 3 3 4 ]
  16: [ 1 2 2 2 3 5 ]
  17: [ 1 2 2 2 4 4 ]
  18: [ 1 2 2 3 3 4 ]
  19: [ 1 2 3 3 3 3 ]
  20: [ 2 2 2 2 2 5 ]
  21: [ 2 2 2 2 3 4 ]
  22: [ 2 2 2 3 3 3 ]
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 21.
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 1-36. [Gives a(0)-a(8). - N. J. A. Sloane, Jun 11 2016] Reproduced in Percy Alexander MacMahon Collected Papers, Volume I, George E. Andrews, ed., MIT Press, 1978, 308-343.
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 68.
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).

Seiichi Manyama, Table of n, a(n) for n = 0..1675 (terms 0..100 from Sean A. Irvine)
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Dale H. Bent, Score problems of round-robin tournaments, Master's dissertation, Univ. Alberta, 1964. See Table 5 on page 52.
David E. Brown, Eric Culver, Bryce Frederickson, Sidney Tate, and Brent J. Thomas, Entropy of Tournament Digraphs, arXiv:1812.09458 [math.CO], 2018.
Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, Counting tournament score sequences, arXiv:2209.03925 [math.CO], 2022.
Sebrina Ruth Cropper, Ranking Score Vectors of Tournaments (2011). All Graduate Reports and Creative Projects. Paper 91. Utah State University, School of Graduate Studies.
Serte Donderwinkel and Brett Kolesnik, Tournaments and random walks, arXiv:2403.12940 [math.PR], 2024. See index, p. 34.
Jeong Han Kim and Boris Pittel, Confirming the Kleitman-Winston Conjecture on the Largest Coefficient in a q-Catalan Number, J. Comb. Theory Series A 92 (2000), 197-206.
P. A. MacMahon, An American tournament treated by the calculus of symmetric functions, Quart. J. Pure Appl. Math., 49 (1920), 1-36. Gives a(1) to a(9). [Annotated scanned copy, scanned at 300 dpi. Do not replace with a smaller file as the print is very tiny and hard to read.]
Yaakov Malinovsky and John W. Moon, On Round-Robin Tournaments with a Unique Maximum Score and Some Related Results, arXiv:2208.14932 [math.CO], 2022.
John W. Moon, Topics on tournaments, Holt, Rinehard and Winston (1968), see page 88.
T. V. Narayana and D. H. Bent, Computation of the number of score sequences in round-robin tournaments, Canad. Math. Bull., 7 (1964), 133-136 (but table contains errors).
D. Recoskie and J. Sawada, The Taming of Two Alley CATs, 2012.
J. Riordan, The number of score sequences in tournaments, J. Combin. Theory, 5 (1968), 87-89. [The main result of this paper seems to be wrong - see A210726.] See also John Riordan, Erratum, J. Comb. Theory 6 (1969), 226.
Paul K. Stockmeyer, Counting Various Classes of Tournament Score Sequences, J. Integer Seq. 26 (2023), Article 23.5.2.
Eric Weisstein's World of Mathematics, Score Sequence.
K. Winston, Letter to N. J. A. Sloane, Aug 05 1978
Kenneth J. Winston and Daniel J. Kleitman, On the Asymptotic Number of Tournament Score Sequences, J. Comb. Theory Series A 35 (1983) 208-230.
Index entries for sequences related to tournaments

Cf. A007747, A210726, A145855.

See A274098 for the most likely score sequence.

max = 40; (* b = A145855 *) b[0] = 1; b[n_] := DivisorSum[n, (-1)^(n+#)* EulerPhi[n/#]*Binomial[2*#, #]/(2*n)&]; s = Exp[Sum[b[m]*x^m/m, {m, 1, max}]] + O[x]^max; CoefficientList[s, x] (* Jean-François Alcover, Dec 06 2015, adapted from PARI *)

{A145855(n)=sumdiv(n,d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d,d)/(2*n))}
{a(n)=polcoeff(exp(sum(m=1,n,A145855(m)*x^m/m)+x*O(x^n)),n)} \\ Paul D. Hanna, Jul 17 2013

Let f_1(T, E)=1 if T=E>=0, =0 else; f_n(T, E)=0 if T-E= 2.
Riordan seems to claim that a(n) = 2*a(n-1)-a(n-2) + A046919(n), but this is not true. - N. J. A. Sloane, May 06 2012
Logarithmic derivative yields A145855, the number of n-member subsets of 1..2n-1 whose elements sum to a multiple of n. - Paul D. Hanna, Jul 17 2013
a(n) = (1/n) * Sum_{k=1..n} A145855(k) * a(n-k) for n>0 with a(0)=1. - Paul D. Hanna, Jul 17 2013
Comment from Paul K. Stockmeyer, Feb 18 2022 (Start)
There are constants c1, c2 such that
  c_1*4^n/n^(5/2) < a(n) < c_2*4^n/n^(5/2).
Most of the proof appears in Winston-Kleitman (1983). The final step was completed by Kim-Pittel (2000). (End)
a(n) ~ c * 4^n / n^(5/2), where c = 0.3924780842992932228521178909875268946304664137141043398966808144665388... - Vaclav Kotesovec, Feb 21 2022

a(11) corrected by Kenneth Winston, Aug 05 1978
More terms from David W. Wilson
Thanks to Paul K. Stockmeyer for comments. - N. J. A. Sloane, Feb 18 2022

A019589 Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n.

Original entry on oeis.org

1, 1, 2, 5, 16, 59, 246, 1105, 5270, 26231, 135036, 713898, 3857113, 21220020, 118547774, 671074583

Offset: 0

Alex Postnikov (apost(AT)math.mit.edu)

Also, number of nondecreasing sequences that are sums of two permutations of order n. If nondecreasing requirement is dropped, the sequence becomes A175176. - Max Alekseyev, Jun 19 2023
From Olivier Gérard, Sep 18 2007: (Start)
Number of classes of permutations arrays giving the same partition by the following transformation (equivalent in this case to X-rays but more general): on the matrix representation of a permutation of order n, the sum (i.e., here, number of ones) in the i-th antidiagonal is the number of copies of i in the partition.
This gives an injection of permutations of n into partitions with parts at most 2n-1. The first or the last antidiagonal can be omitted, reducing the size of parts to 2n-2 without changing the number of classes.
This sequence is called Lambda_{n,1} in Louck's paper and appears explicitly on p. 758. Terms up to 10 were computed by Myron Stein (arXiv).
This is similar to the number of Schur functions studied by Di Francesco et al. (A007747) related to the powers of the Vandermonde determinant. Also number of classes of straight (monotonic) crossing bi-permutations. (End)
Also number of monomials in expansion of permanent of an n X n Hankel matrix [t(i+j)] in terms of its entries (cf. A019448). - Vaclav Kotesovec, Mar 29 2019

Olivier Gérard and Karol Penson, Set partitions, multiset permutations and bi-permutations, in preparation.

C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
David A. Corneth, Nondecreasing sequences for a(n) where n = 0..8.
J.-P. Davalan, Permutations et tomographie - X-rays.
James D. Louck, Power of a determinant with two physical applications, Internat. J. Math. & Math. Sci., Vol. 22, No 4(1999) pp. 745-759 - S 0161-1712(99)22745-7

Cf. A007747, A019447, A019448, A086647, A175176, A290052, A289971, A362967.

with(LinearAlgebra): f:=n->nops([coeffs(Permanent(Matrix(n, (i, j) -> a[i+j])))]): [seq(f(n), n=1..10)]; # Vaclav Kotesovec, Mar 29 2019

a[n_] := Table[b[i+j], {i, n}, {j, n}] // Permanent // Expand // Length;
Array[a, 10, 0] (* Jean-François Alcover, May 29 2019, after Vaclav Kotesovec *)

a(n) = my(l=List(), v=[1..n]);for(i=0, n!-1, listput(l, vecsort(v-numtoperm(n,i)))); listsort(l, 1); #l

import itertools
def a019589(n):
    s = set()
    for p in itertools.permutations(range(n)):
        s.add(tuple(sorted([k - p[k] for k in range(n)])))
    return len(s)
print([a019589(n) for n in range(10)])
# Bert Dobbelaere, Jan 19 2019

a(n) <= A007747(n) <= A362967(n). - Max Alekseyev, Jun 19 2023

More terms from Olivier Gérard, Sep 18 2007
Two more terms from Vladeta Jovovic, Oct 04 2007
a(0)=1 prepended by Alois P. Heinz, Jul 24 2017
a(13)-a(14) from Bert Dobbelaere, Jan 19 2019
a(15) from Max Alekseyev, Jun 28 2023

A047730 Number of score sequences in tournament with n players, when 4 points are awarded in each game.

Original entry on oeis.org

1, 3, 13, 76, 521, 3996, 32923, 286202, 2590347, 24203935, 232050202, 2272449745, 22653570386, 229274897514, 2350933487206, 24381053759852, 255382755251622, 2698732882975782, 28743579211912338

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus o symmetric functions, Coll. Papers I, MIT Press, 344-375.

Cf. A000571, A007747, A047729, A064626, A064422.

Nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 4, p_i >= 0, i=1, ..., n.

A047729 Number of score sequences in tournament with n players, when 3 points are awarded in each game.

Original entry on oeis.org

1, 2, 8, 37, 198, 1178, 7548, 50944, 357855, 2595250, 19313372, 146815503, 1136158495, 8927025989, 71065654235, 572215412354, 4653746621835, 38184724333615, 315792633485360, 2630183440412617, 22046522161472304

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus of symmetric functions, Coll. Papers I, MIT Press, 344-375.

Qihao Ye, Table of n, a(n) for n = 1..1032
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Index entries for sequences related to tournaments

Cf. A000571, A007747.

Nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 3, p_i >= 0, i=1, ..., n.

A064626 Football tournament numbers: the number of possible point series for a tournament of n teams playing each other once where 3 points are awarded to the winning team and 1 to each in the case of a tie.

Original entry on oeis.org

1, 2, 7, 40, 355, 3678, 37263, 361058, 3403613, 31653377, 292547199, 2696619716

Offset: 1

Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 30 2001

This sequence reflects the now common 3-point rule of international football where the sum of total points awarded depends on the outcome of each match. The classical 2-point rule is equivalent to that for chess tournaments (A007747).

			For 2 teams there are 2 possible outcomes: [0, 3] and [1, 1], so a(2) = 2.
For 3 teams the outcomes are [0, 3, 6], [1, 3, 4], [3, 3, 3], [1, 1, 6], [1, 2, 4], [0, 4, 4] and [2, 2, 2], so a(3) is 7. Note that the outcome [3, 3, 3] can be obtained in two ways: (A beats B, B beats C, C beats A) or (B beats A, A beats C, C beats B).

A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012) 260-288. - From _N. J. A. Sloane_, Feb 15 2013
Wikipedia, Three points for a win

Cf. A007747, A047730, A064422, A152789.

a(8) and a(9) from Jon E. Schoenfield, May 05 2007
a(10) from Ming Li (dawnli(AT)ustc.edu), Jun 20 2008
a(11) from Jon E. Schoenfield, Sep 04 2008
a(12) from Jon E. Schoenfield, Dec 12 2008

A047731 Number of score sequences in tournament with n players, when 5 points are awarded in each game.

Original entry on oeis.org

1, 3, 18, 131, 1111, 10461, 105819, 1127413, 12499673, 143021541, 1678718575, 20123155604, 245521479531, 3041006378312, 38157059717410, 484209044329613, 6205758830280388, 80235572611152385

Offset: 1

David W. Wilson

nonn

P. A. MacMahon, Chess tournaments and the like treated by the calculus o symmetric functions, Coll. Papers I, MIT Press, 344-375.

Cf. A000571, A007747, A047729, A047730.

A362968 Number of integral points in 2 * permutohedron of order n.

Original entry on oeis.org

1, 3, 19, 201, 3081, 62683, 1598955, 49180113, 1773405649, 73410669171, 3432267261699, 178922825114905, 10291053760222041, 647436905815864011, 44229766376059342171, 3260749830852693615777, 258039101519624535653025

Offset: 1

Max Alekseyev, Jun 17 2023

nonn

Every vectorial sum of two permutations represents an integral point in 2*permutohedron, however the converse does not hold. Hence, a(n) >= A175176(n) for all n, where the equality holds only for n <= 5.

Number of points up to their components order is given by A007747.

C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini. On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Wikipedia, Permutohedron.

Cf. A007747, A138464, A175176, A362967.

w := LambertW(-2*x): egf := exp(-w * (2 + w) / 4): ser := series(egf, x, 20):
seq(n! * coeff(ser, x, n), n = 1..17); # Peter Luschny, Jun 19 2023

a362968(n) = my(x=y+O(y^(n+1))); n! * polcoef( exp(-lambertw(-2*x)/2 - lambertw(-2*x)^2/4), n );

a(n) = Sum_{k=0..n-1} A138464(n,k) * 2^k, which is the value of the Ehrhart polynomial of permutohedron at t = 2.

E.g.f.: exp(-W(-2*x)/2 - W(-2*x)^2/4), where W() is the Lambert function.

cp's OEIS Frontend

A047656 a(n) = 3^((n^2-n)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A000571 Number of different score sequences that are possible in an n-team round-robin tournament.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A019589 Number of nondecreasing sequences that are differences of two permutations of 1,2,...,n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A047730 Number of score sequences in tournament with n players, when 4 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A047729 Number of score sequences in tournament with n players, when 3 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A064626 Football tournament numbers: the number of possible point series for a tournament of n teams playing each other once where 3 points are awarded to the winning team and 1 to each in the case of a tie.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A047731 Number of score sequences in tournament with n players, when 5 points are awarded in each game.

Views

Author

Keywords

References

Links

Crossrefs

A362968 Number of integral points in 2 * permutohedron of order n.

Views

Author

Keywords