login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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

%I

%S 6,56,553,5519,55183,551820,5518192,55181917,551819162,5518191618,

%T 55181916176,551819161758,5518191617572,55181916175717,

%U 551819161757164,5518191617571636,55181916175716349,551819161757163483

%N 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.

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

%C 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.

%C The probability P(n) approaches 1/e quite slowly as this sequence shows. See image clicking the first link.

%H Flajolet and Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>

%H Wikipedia, <a href="http://commons.wikimedia.org/wiki/File:Seq1.png">Graph of probabilities</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Derangement#Counting_derangements">Derangements</a>

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

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

%K nonn

%O 1,1

%A _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 November 21 06:00 EST 2019. Contains 329350 sequences. (Running on oeis4.)