Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #20 Nov 09 2023 20:53:39
%S 1,2,12,128,2680,109824,8791552,1376518144,422360211456,
%T 254460936847360,301592785058791424,704473043710859280384,
%U 3248469673423387574140928,29616255381502146777580568576,534589619577015738514639410954240,19128875195554152154920492396852543488
%N 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.
%C 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.
%H Christian Sievers, <a href="/A123553/b123553.txt">Table of n, a(n) for n = 1..81</a>
%H S. B. Maurer, <a href="http://www.maa.org/programs/maa-awards/writing-awards/the-king-chicken-theorems">The king chicken theorems</a>, Math. Mag., 53 (1980), 67-80.
%H <a href="/index/To#tournament">Index entries for sequences related to tournaments</a>
%F a(n) >= A006125(n)*3 - A006125(n-1)*n*2 with equality for n<=4.
%F 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
%e 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.
%o (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
%Y Cf. A006125, A013976, A125032, A125031 (highest scorers), A123903 (Emperors).
%K nonn
%O 1,2
%A _N. J. A. Sloane_, Nov 14 2006
%E Corrected and edited by _Martin Fuller_, Nov 16 2006
%E a(7) and beyond from _Christian Sievers_, Nov 01 2023