login
A372422
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.
10
0, 2, 7, 8, 133, 16, 3221, 3392, 100391, 20848, 163287, 7567072, 10605587147, 1551804656, 1732332761353, 252492267136, 2313623814645529, 261522788700176, 69661896931499841923, 2828470111061381408, 23101294621895391907711, 2128055943326564678576, 3012597206020256660646816301
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.
A372424/A372425 are the corresponding expected numbers of nodes of the tree.
A372482/A372483 are the probabilities of terminating with a single loser.
Sequence in context: A000637 A250715 A198322 * A371331 A222134 A011355
KEYWORD
nonn,frac
AUTHOR
Hugo Pfoertner, May 02 2024
STATUS
approved