This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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)



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.


Table of n, a(n) for n=1..18.

Flajolet and Sedgewick, Analytic Combinatorics

Wikipedia, Graph of probabilities

Wikipedia, Derangements


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).


Cf. A000169, A000272, A068985, A000166, A181590.

Sequence in context: A183586 A166177 A183615 * A093142 A092655 A099140

Adjacent sequences:  A181586 A181587 A181588 * A181590 A181591 A181592




Washington Bomfim, Oct 31 2010



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 13:24 EDT 2019. Contains 328299 sequences. (Running on oeis4.)