|
Search: id:A123553
|
|
|
| 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. |
|
+0
4
|
| |
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 this_sequence A079199 A090361 A073551
Adjacent sequences: A123550 A123551 A123552 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
