|
%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
| 