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
Christian Sievers, Table of n, a(n) for n = 1..81
S. B. Maurer, The king chicken theorems, Math. Mag., 53 (1980), 67-80.
FORMULA
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
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.
PROG
(PARI) 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
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Nov 14 2006
EXTENSIONS
Corrected and edited by Martin Fuller, Nov 16 2006
a(7) and beyond from Christian Sievers, Nov 01 2023
STATUS
approved