

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(n1)/2) tournaments.


4




OFFSET

1,2


COMMENTS

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.


LINKS

Table of n, a(n) for n=1..7.
S. B. Maurer, The king chicken theorems, Math. Mag., 53 (1980), 6780.
Index entries for sequences related to tournaments


FORMULA

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


EXAMPLE

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.


CROSSREFS

Cf. A006125, A013976, A123553, A125032, A125031 (highest scorers)w, A123903 (Emperors).
Sequence in context: A259267 A014235 A098628 * A354493 A079199 A303926
Adjacent sequences: A123550 A123551 A123552 * A123554 A123555 A123556


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane, Nov 14 2006


EXTENSIONS

Corrected and edited by Martin Fuller, Nov 16 2006


STATUS

approved



