|
| |
|
|
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.
|
|
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), 67-80.
Index entries for sequences related to tournaments
|
|
|
FORMULA
|
a(n) >= A006125(n)*3 - A006125(n-1)*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
|
| |
|
|
