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

6, 56, 553, 5519, 55183, 551820, 5518192, 55181917, 551819162, 5518191618, 55181916176, 551819161758, 5518191617572, 55181916175717, 551819161757164, 5518191617571636, 55181916175716349, 551819161757163483

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