OFFSET
1,2
COMMENTS
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.
See Prodinger (1993) and Knuth (1997) for the asymptotic behavior.
REFERENCES
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.
LINKS
Helmut Prodinger, How to select a loser, Discrete Mathematics, Volume 120, Issues 1-3, 12 September 1993, Pages 149-159.
EXAMPLE
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, ...
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, ...
PROG
(PARI) a372422_3(n) = sum (k=1, n-1, binomial(n, k)*bernfrac(k)/(1-1/2^k));
a372422(n) = numerator(a372422_3(n))
CROSSREFS
A372423 are the corresponding denominators.
KEYWORD
nonn,frac
AUTHOR
Hugo Pfoertner, May 02 2024
STATUS
approved