

A181589


Least value of n such that P(n)  1/e < 10^(i), i=1,2,3... . P(n) = (n/(n+1))^(n1) the probability of a random forest on n be a tree.


1



6, 56, 553, 5519, 55183, 551820, 5518192, 55181917, 551819162, 5518191618, 55181916176, 551819161758, 5518191617572, 55181916175717, 551819161757164, 5518191617571636, 55181916175716349, 551819161757163483
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

The probability P(n) = A000169(n)/A000272(n+1). It is known that lim_{n>inf}p(n) = 1/e. (See Flajolet and Sedgewick link, pp 632, where we can find a function of the number of components k).
Both P(n) and the probability that a permutation on n objects be a derangement tend to 1/e when n rises to infinity. So the events a random forest be a tree and a random permutation be a derangement become equiprobable as n tends to infinity.
The probability P(n) approaches 1/e quite slowly as this sequence shows. See image clicking the first link.


LINKS

Table of n, a(n) for n=1..18.
Flajolet and Sedgewick, Analytic Combinatorics
Wikipedia, Graph of probabilities
Wikipedia, Derangements


EXAMPLE

a(1) = 6, a(2) = 56, so for n in the interval 6...55 if we use 1/e as the probability P, we make an error less than 10^(1). In general if n is in the interval a(i), ... , a(i+1)1, this error is less than 10^(i).


CROSSREFS

Cf. A000169, A000272, A068985, A000166, A181590.
Sequence in context: A183586 A166177 A183615 * A093142 A092655 A099140
Adjacent sequences: A181586 A181587 A181588 * A181590 A181591 A181592


KEYWORD

nonn


AUTHOR

Washington Bomfim, Oct 31 2010


STATUS

approved



