|
%I #10 May 17 2024 15:26:03
%S 0,2,7,8,133,16,3221,3392,100391,20848,163287,7567072,10605587147,
%T 1551804656,1732332761353,252492267136,2313623814645529,
%U 261522788700176,69661896931499841923,2828470111061381408,23101294621895391907711,2128055943326564678576,3012597206020256660646816301
%N a(n) is the numerator of the expected depth of the tree representing the process of eliminating from n people a random group by tossing coins, and repeating this process recursively until a single loser is determined.
%C The depth of the tree corresponds to the number of rounds in which the members of the group, which initially consists of n people, have to toss coins until a loser is determined. The expected total number of coin flips is 2*n for n->oo.
%C See Prodinger (1993) and Knuth (1997) for the asymptotic behavior.
%D Donald E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 6.3 Digital Searching, Pages 505 and 509 (exercise 27). Addison-Wesley, Reading, MA, 1997.
%H Helmut Prodinger, <a href="https://doi.org/10.1016/0012-365X(93)90572-B">How to select a loser</a>, Discrete Mathematics, Volume 120, Issues 1-3, 12 September 1993, Pages 149-159.
%e a(n)/A372423(n): 0, 2, 7/3, 8/3, 133/45, 16/5, 3221/945, 3392/945, 100391/26775, 20848/5355, 163287/40579, 7567072/1826055, 10605587147/2492565075, ...
%e Approximately 0, 2.0, 2.3333, 2.6667, 2.9556, 3.2, 3.4085, 3.5894, 3.7494, 3.8932, 4.0239, 4.1439, 4.2549, 4.3580, 4.4543, ...
%o (PARI) a372422_3(n) = sum (k=1, n-1, binomial(n,k)*bernfrac(k)/(1-1/2^k));
%o a372422(n) = numerator(a372422_3(n))
%Y A372423 are the corresponding denominators.
%Y A372424/A372425 are the corresponding expected numbers of nodes of the tree.
%Y A372482/A372483 are the probabilities of terminating with a single loser.
%K nonn,frac
%O 1,2
%A _Hugo Pfoertner_, May 02 2024
|
