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
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
KEYWORD
nonn
AUTHOR
Washington Bomfim, Oct 31 2010
STATUS
approved