The Answer May Surprise You

Probability Level 4

Let n n be a natural number. Let ( a k ) k = 1 n (a_k)_{k=1}^{n} be a permutation of the numbers { 1 , 2 , 3 , . . . n } \{1,2,3, ... n\} . Let p n p_n be the probability that a k ≠ k a_k \neq k for all 1 ≤ k ≤ n 1 \le k \le n .

Find lim ⁡ n → ∞ ln ⁡ ( p n ) \lim_{n \to \infty} \ln(p_n) .


The answer is -1.

Ariel Gershon by Ariel Gershon , 26, Canada

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Pi Han Goh
Mar 21, 2015

This is a simple case of derangement , so lim ⁡ n → ∞ p n = 1 e \displaystyle \lim_{n \to \infty} p_n = \frac {1}{e} , answer is ln ⁡ ( 1 e ) = − 1 \ln \left ( \frac 1 e \right) = \boxed{-1}

3 Helpful 0 Interesting 0 Brilliant 0 Confused

! n = [ n ! e ] !n=\left[ \frac { n! }{ e } \right] where [ . ] [.] is the nearest integer function.

Raghav Vaidyanathan - 6 years, 2 months ago
Richard Polak
Apr 3, 2015

There's an elementary explanation of why this is in this wikipedia article: http://en.wikipedia.org/wiki/Random permutation statistics#Number of permutations that are_derangements

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...