|
| |
|
|
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.
|
|
|
REFERENCES
| S. B. Maurer, The king chicken theorems, Math. Mag., 53 (1980), 67-80.
|
|
|
LINKS
| 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: A097629 A014235 A098628 * A079199 A185751 A090361
Adjacent sequences: A123550 A123551 A123552 * A123554 A123555 A123556
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Nov 14 2006
|
|
|
EXTENSIONS
| Corrected and edited by Martin Fuller (martin_n_fuller(AT)btinternet.com), Nov 16 2006
|
| |
|
|
