A123903 -id:A123903 - cp's OEIS frontend

A125031 Total number of highest scorers in all 2^(n(n-1)/2) tournaments with n players.

1, 2, 12, 104, 1560, 53184, 3422384, 430790144, 111823251840, 56741417927680, 57729973360342272, 118195918779085344768, 479770203506298422135808, 3914602958361039682677710848, 63809077054456699374663196416000, 2076906726499655025703507210668998656

Offset: 1

Martin Fuller, Nov 16 2006

nonn

All highest scorers are also king chickens, A123553.

			With 4 players there are 32 tournaments with 1 highest scorer, 24 tournaments with 2 highest scorers and 8 tournaments with 3 highest scorers. Therefore a(4)=32*1+24*2+8*3=104.

Andrew Howroyd, Table of n, a(n) for n = 1..20
Index entries for sequences related to tournaments

Cf. A006125, A013976, A123553, A125032, A123903.

\\ Requires Winners from A013976.
a(n)={my(M=Winners(n)); sum(i=1, matsize(M)[1], pollead(M[i, 1])*M[i, 2])} \\ Andrew Howroyd, Feb 29 2020

a(5)-a(10) also computed by Gordon Royle, Nov 16 2006

Terms a(12) and beyond from Andrew Howroyd, Feb 28 2020

A123553 A "king chicken" in a tournament graph (a directed labeled graph on n nodes with a single arc between every pair of nodes) is a player A who for any other player B either beats B directly or beats someone who beats B. Sequence gives total number of king chickens in all 2^(n(n-1)/2) tournaments.

Original entry on oeis.org

1, 2, 12, 128, 2680, 109824, 8791552, 1376518144, 422360211456, 254460936847360, 301592785058791424, 704473043710859280384, 3248469673423387574140928, 29616255381502146777580568576, 534589619577015738514639410954240, 19128875195554152154920492396852543488

Offset: 1

N. J. A. Sloane, Nov 14 2006

nonn

H. G. Landau showed in 1951 that there may be several king chickens in a tournament and that a player is a king chicken if he has the highest score. The converse is not true and there can be more king chickens than highest scorers. The smallest example has 4 players: A beats B and C, B beats C and D, C beats D, D beats A; D is a king chicken despite having fewer points than A and B. Maurer showed in 1980 that there is one king chicken if one player beats all others and otherwise there are at least three.

			For n = 3 there are 8 tournaments: six of the form A beats B and C and B beats C, with one king chicken (A) and two of the form A beats B beats C beats A, with three king chickens each (A or B or C), for a total of 6*1 + 2*3 = 12.

Christian Sievers, Table of n, a(n) for n = 1..81
S. B. Maurer, The king chicken theorems, Math. Mag., 53 (1980), 67-80.
Index entries for sequences related to tournaments

Cf. A006125, A013976, A125032, A125031 (highest scorers), A123903 (Emperors).

a(n)=n*sum(k=0,n-1,binomial(n-1,k)*2^(binomial(k,2)+binomial(n-1-k,2))*(2^k-1)^(n-1-k)) \\ Christian Sievers, Nov 01 2023

a(n) >= A006125(n)*3 - A006125(n-1)*n*2 with equality for n<=4.

a(n) = n * Sum_{k=0..n-1} C(n-1,k) * 2^(C(k,2)+C(n-1-k,2)) * (2^k-1)^(n-1-k) where C(n,k) is the binomial coefficient. - Christian Sievers, Nov 01 2023

Corrected and edited by Martin Fuller, Nov 16 2006

a(7) and beyond from Christian Sievers, Nov 01 2023

A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 1, 6, 3, 4, 32, 12, 16, 38, 320, 80, 80, 190, 728, 6144, 960, 640, 1140, 4368, 26704, 229376, 21504, 8960, 10640, 30576, 186928, 1866256, 16777216, 917504, 229376, 170240, 326144, 1495424, 14930048, 251548592, 2415919104, 75497472, 11010048, 4902912, 5870592, 17945088, 134370432, 2263937328, 66296291072

Offset: 1

Geoffrey Critzer, Mar 28 2013

			Triangle T(n,k) begins:
       1;
       2,     1;
       6,     3,    4;
      32,    12,   16,    38;
     320,    80,   80,   190,   728;
    6144,   960,  640,  1140,  4368,  26704;
  229376, 21504, 8960, 10640, 30576, 186928, 1866256;
  ...

Alois P. Heinz, Rows n = 1..45, flattened

Cf. A001187, A006125, A123903 (column 1), A125207 (row sums), A182166 (column 2).

function b(n) // b = A001187
  if n eq 0 then return 1;
  else return 2^Binomial(n,2) - (&+[Binomial(n-1,j-1)*2^Binomial(n-j,2)*b(j): j in [0..n-1]]);
  end if; return b;
end function;
A223894:= func< n,k | Binomial(n,k)*2^Binomial(n-k,2)*b(k) >;
[A223894(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Oct 03 2022

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
    end:
T:= (n, k)-> binomial(n, k)*b(k)*2^((n-k)*(n-k-1)/2):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 26 2013

nn = 9; f[list_] := Select[list, # > 0 &]; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; a = Drop[Range[0, nn]! CoefficientList[Series[Log[g] + 1, {x, 0, nn}], x], 1]; Map[f, Drop[Transpose[Table[Range[0, nn]! CoefficientList[Series[a[[n]] x^n/n! g, {x, 0, nn}], x], {n, 1, nn}]], 1]] // Grid

@CachedFunction
def b(n): # b = A001187
    if (n==0): return 1
    else: return 2^binomial(n,2) - sum(binomial(n-1,j-1)*2^binomial(n-j,2)*b(j) for j in range(n))
def A223894(n,k): return binomial(n,k)*2^binomial(n-k,2)*b(k)
flatten([[A223894(n,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Oct 03 2022

E.g.f. for column k: A001187(n)*x^n/n!*A(x) where A(x) is the e.g.f. for A006125.
Sum_{k=0..n} T(n, k) = A125207(n).
T(n, 1) = A123903(n).
T(n, 2) = A182166(n).
T(n, n) = A001187(n). - G. C. Greubel, Oct 03 2022

A217652 Number of isolated nodes over all labeled directed graphs on n nodes.

Original entry on oeis.org

0, 1, 2, 12, 256, 20480, 6291456, 7516192768, 35184372088832, 648518346341351424, 47223664828696452136960, 13617340432139183023890366464, 15576890575604482885591488987660288, 70778732319555200400381918345807787982848

Offset: 0

Geoffrey Critzer, Oct 09 2012

nonn

a(n) = Sum_{k=1..n} A217580(n,k) * k.

a(n) is also the number of labeled directed graphs on n nodes with an "Emperor". - Rémy-Robert Joseph, Nov 12 2012

Alois P. Heinz, Table of n, a(n) for n = 0..40

See also A123903 (case of tournaments) and A219116 (case of semicomplete digraphs) Rémy-Robert Joseph, Nov 12 2012

a:= n-> 2^(n^2-3*n+2)*n:
seq (a(n), n=0..15);  # Alois P. Heinz, Oct 09 2012

nn=15; s=Sum[2^(n^2-n)x^n/n!,{n,0,nn}]; Range[0,nn]! CoefficientList[Series[x s, {x,0,nn}], x]

A217652(n):=2^(n^2-3*n+2)*n$ makelist(A217652(n),n,0,10); /* Martin Ettl, Nov 13 2012 */

E.g.f.: x * A(x) where A(x) is the e.g.f. for A053763.

a(n) = 2^(n^2-3*n+2)*n. - Alois P. Heinz, Oct 09 2012

A219116 Number of semicomplete digraphs on n nodes with an "Emperor".

Original entry on oeis.org

0, 1, 2, 9, 108, 3645, 354294, 100442349, 83682825624, 205891132094649, 1500946352969991210, 32497439772059170685073, 2093390532109442148854046084, 401741006974223960704968343445877, 229924845755649214047240549209929574046

Offset: 0

Rémy-Robert Joseph, Nov 12 2012

nonn

a(n) is also the number of asymmetric digraphs on n nodes with an "Emperor".

See also A123903 for tournaments and A217652 for digraphs.

A219116(n):=n*3^((n^2-3*n+2)/2)$ makelist(A219116(n),n,0,14); /* Martin Ettl, Nov 13 2012 */

a(n) = n*3^((n^2 - 3*n + 2)/2).

A228315 Triangular array read by rows: T(n,k) is the number of rooted labeled simple graphs on {1,2,...,n} such that the root is in a component of size k; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 2, 6, 6, 12, 32, 24, 48, 152, 320, 160, 240, 760, 3640, 6144, 1920, 1920, 4560, 21840, 160224, 229376, 43008, 26880, 42560, 152880, 1121568, 13063792, 16777216, 1835008, 688128, 680960, 1630720, 8972544, 104510336, 2012388736

Offset: 1

Geoffrey Critzer, Aug 26 2013

Row sums = A095340.
Column 1 = A123903.
T(n,k)   = A223894(n,k)*k.
Diagonal = A053549.

			1;
2,    2;
6,    6,    12;
32,   24,   48,    152;
320,  160,  240,   760,    3640;

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 7.

Alois P. Heinz, Rows n = 1..45, flattened
Index entries for sequences related to graphs

Cf. A070166.

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
    end:
T:= (n, k)-> binomial(n, k)*k*b(k)*2^((n-k)*(n-k-1)/2):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 26 2013

nn = 10; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; a =
Drop[Range[0, nn]! CoefficientList[Series[Log[g], {x, 0, nn}], x],
  1]; Table[
  Table[Binomial[n, k] k a[[k]] 2^Binomial[n - k, 2], {k, 1, n}], {n,
   1, 7}] // Grid

T(n,k) = binomial(n,k)*k*A001187(k)*A006125(n-k).

A245235 Repeat 2^(n*(n+1)/2) n+1 times.

Original entry on oeis.org

1, 2, 2, 8, 8, 8, 64, 64, 64, 64, 1024, 1024, 1024, 1024, 1024, 32768, 32768, 32768, 32768, 32768, 32768, 2097152, 2097152, 2097152, 2097152, 2097152, 2097152, 2097152, 268435456, 268435456, 268435456, 268435456, 268435456, 268435456, 268435456, 268435456

Offset: 0

Paul Curtz, Jul 14 2014

For a(n), the successive exponents of 2 are 0, 1, 1, 3, 3, 3,... = A057944(n).

			n+1 times repeated 2^(n*(n+1)/2)= 1, 2, 8, 64, 1024,... = A139685(n).
By the formula: a(0)=1/1=1, a(1)=2/1=2, a(2)=4/2=2, a(3)=8/1=8, a(4)=16/2=8,...
As triangle:
   1,
   2,    2,
   8,    8,    8,
  64,   64,   64,   64,
1024, 1024, 1024, 1024, 1024,
etc.
Row sums: 1, 4, 24, 256,... = A095340.

Cf. A000079, A006125, A057944, A059268, A095340, A123903, A139685.

Table[2^(n*(n+1)/2), {n, 0, 7}, {n+1}] // Flatten (* Jean-François Alcover, Jul 15 2014 *)

from math import isqrt
def A245235(n): return 1<<((m:=isqrt(n+1<<3)-1>>1)*(m+1)>>1) # Chai Wah Wu, Dec 17 2024

a(n) = 2^n/A059268(n).

T(n, k) = 2^(n*(n+1)/2), 0 <= k <= n. - Michel Marcus, Jul 17 2014

A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 4, 0, 8, 6, 12, 38, 0, 64, 32, 48, 152, 728, 0, 1024, 320, 320, 760, 3640, 26704, 0, 32768, 6144, 3840, 6080, 21840, 160224, 1866256, 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592

Offset: 0

Peter Luschny, Feb 20 2023

			Triangle T(n, k) starts:
[0] 1;
[1] 0,       1;
[2] 0,       1,      1;
[3] 0,       2,      2,     4;
[4] 0,       8,      6,    12,    38;
[5] 0,      64,     32,    48,   152,    728;
[6] 0,    1024,    320,   320,   760,   3640,   26704;
[7] 0,   32768,   6144,  3840,  6080,  21840,  160224,  1866256;
[8] 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Algorithms for Competitive Programming, Counting labeled graphs, cp-algorithms.
Albert Nijenhuis and Herbert S Wilf, The enumeration of connected graphs and linked diagrams, Journal of Combinatorial Theory, Vol. 27(3), 1979, Pages 356-359.
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Labeled Graph.

Cf. A006125 Graphs on n labeled nodes, T(n+1, 1) and Sum_{k=0..n} T(n, k).
Cf. A054592 Disconnected labeled graphs with n nodes, Sum_{k=0..n-1} T(n, k).
Cf. A001187 Connected labeled graphs with n nodes, T(n, n).
Cf. A123903 Isolated nodes in all simple labeled graphs on n nodes, T(n+2, 2).
Cf. A053549 Labeled rooted connected graphs, T(n+1, n).
Cf. A275462 Leaves in all simple labeled connected graphs on n nodes T(n+2, n).
Cf. A060818 gcd_{k=0..n} T(n, k) = gcd(n!, 2^n).
Cf. A143543 Labeled graphs on n nodes with k connected components.
Cf. A095340 Total number of nodes in all labeled graphs on n nodes.
Cf. A360604, A360860 (accumulation triangle).

T := (n, k) -> 2^binomial(n-k, 2)*binomial(n-1, k-1)*A001187(k):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Based on the recursion:
Trow := proc(n) option remember; if n = 0 then return [1] fi;
seq(2^binomial(n-k, 2) * binomial(n-1, k-1) * Trow(k)[k+1], k = 1..n-1);
2^(n*(n-1)/2) - add(j, j = [%]); [0, %%, %] end:
seq(print(Trow(n)), n = 0..8);

A001187[n_] := A001187[n] = 2^((n - 1)*n/2) - Sum[Binomial[n - 1, k]*2^((k - n + 1)*(k - n + 2)/2)*A001187[k + 1], {k, 0, n - 2}];
T[n_, k_] := 2^Binomial[n - k, 2]*Binomial[n - 1, k - 1]*A001187[k];
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 02 2023, after Peter Luschny in A001187 *)

from math import comb as binomial
from functools import cache
@cache
def A360603Row(n: int) -> list[int]:
    if n == 0: return [1]
    s = [2 ** (((k - n + 1) * (k - n)) // 2) * binomial(n - 1, k - 1) * A360603Row(k)[k] for k in range(1, n)]
    b = 2 ** (((n - 1) * n) // 2) - sum(s)
    return [0] + s + [b]

T(n, k) = 2^binomial(n-k, 2)*binomial(n-1, k-1) * A001187(k).
Recursion over the rows of the triangle: Set row(0) = [1] where [.] denotes a 0-based list. Assume now all rows(j) for j < n computed, next compute r = [2^binomial(n-k, 2) * binomial(n-1, k-1) * row(k)[k] for k = 1..n-1] and s = 2^(n*(n-1)/2) - Sum(r). Then row(n) = [0] & r & [s], where '&' denotes the concatenation of lists. (See the Python program for an implementation.)
T(n, n) = A001187(n) (connected labeled graphs).
T(n-1, n) = A053549(n-1) for n >= 1 (labeled rooted connected graphs).
T(n, 1) = Sum_{k>=0} T(n-1, k) = A006125(n-1) for n >= 1 (all labeled graphs).
Sum_{k=0..n-1} T(n, k) = A054592(n) for n >= 1 (disconnected labeled graphs).
See additional formulas in the cross-references.

A285529 Triangle read by rows: T(n,k) is the number of nodes of degree k counted over all simple labeled graphs on n nodes, n>=1, 0<=k<=n-1.

Original entry on oeis.org

1, 2, 2, 6, 12, 6, 32, 96, 96, 32, 320, 1280, 1920, 1280, 320, 6144, 30720, 61440, 61440, 30720, 6144, 229376, 1376256, 3440640, 4587520, 3440640, 1376256, 229376, 16777216, 117440512, 352321536, 587202560, 587202560, 352321536, 117440512, 16777216

Offset: 1

Geoffrey Critzer, Apr 20 2017

			1,
2,   2,
6,   12,   6,
32,  96,   96,   32,
320, 1280, 1920, 1280, 320,
...

Row sums give A095340.

Columns for k=0-3: A123903, A095338, A038094, A038096.

nn = 9; Map[Select[#, # > 0 &] &,
  Drop[Transpose[Table[A[z_] := Sum[Binomial[n, k] 2^Binomial[n, 2] z^n/n!, {n, 0, nn}];Range[0, nn]! CoefficientList[Series[z A[z], {z, 0, nn}], z], {k,0, nn - 1}]], 1]] // Grid

E.g.f. for column k: x * Sum_{n>=0} binomial(n,k)*2^binomial(n,2)*x^n/n!.
Sum_{k=1..n-1} T(n,k)*k/2 = A095351(n).
T(n,k) = n*binomial(n-1,k)*2^binomial(n-1,2). - Alois P. Heinz, Apr 21 2017

cp's OEIS Frontend

A125031 Total number of highest scorers in all 2^(n(n-1)/2) tournaments with n players.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A223894 Triangular array read by rows: T(n,k) is the number of connected components with size k summed over all simple labeled graphs on n nodes; n>=1, 1<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A217652 Number of isolated nodes over all labeled directed graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A219116 Number of semicomplete digraphs on n nodes with an "Emperor".

Views

Author

Keywords

Comments

Crossrefs

Programs

Maxima

Formula

A228315 Triangular array read by rows: T(n,k) is the number of rooted labeled simple graphs on {1,2,...,n} such that the root is in a component of size k; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A245235 Repeat 2^(n*(n+1)/2) n+1 times.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python