|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
KEYWORD
|
nonn,frac
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
