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.

1, 2, 12, 128, 2680, 109824, 8791552, 1376518144, 422360211456, 254460936847360, 301592785058791424, 704473043710859280384, 3248469673423387574140928, 29616255381502146777580568576, 534589619577015738514639410954240, 19128875195554152154920492396852543488

Offset: 1

Author

N. J. A. Sloane, Nov 14 2006

Keywords

• nonn

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.

Examples

			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.
		

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.
• Index entries for sequences related to tournaments

Crossrefs

Cf. A006125, A013976, A125032, A125031 (highest scorers), A123903 (Emperors).

Programs

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

Formula

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

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

Extensions

Corrected and edited by Martin Fuller, Nov 16 2006

a(7) and beyond from Christian Sievers, Nov 01 2023