Intereting Posts

GRE problem involving LCD, prime factorization, and sets.
Expressing the integral $\int_{0}^{1}\frac{\mathrm{d}x}{\sqrt{\left(1-x^3\right)\left(1-a^6x^3\right)}}$ in terms of elliptic integrals
General proof of limit composition theorem on continuous function
Finding $\int_0^{\frac{\pi}{2}}\arctan\left(\sin x\right)dx$
Proving $2,3,1+\sqrt{-5}$ and $1-\sqrt{-5}$ are irreducible in $\mathbb{Z}$
The expectation of absolute value of random variables
Number of real roots of $\frac{a_1}{a_1-x}+\frac{a_2}{a_2-x}+…+\frac{a_n}{a_n-x}=2016$ for $0<a_1<…<a_n$?
Best way to integrate $ \int_0^\infty \frac{e^{-at} – e^{-bt}}{t} \text{d}t $
Measurability of supremum over measurable set
Dictionary order topology and subspace topology
Is $\int_{M_{n}(\mathbb{R})} e^{-A^{2}}d\mu$ a convergent integral?
How to approach solving $\int_0^{\pi/2} \ln(a^2 \cos^2 x +b^2 \sin^2 x ) dx$
Is $\lor$ definable in intuitionistic logic?
What is, exactly, a discrete group?
$R$ integral domain : $u\in R^*, a \text{ is prime} \iff au \text{ is prime}$

Is it true that $\frac1{n!} \int_0^\infty x^{n-k} (x-1)^k e^{-x}\,dx \approx e^{-k/n}$ when $k$ and $n$ are large integers with $k \le n$?

This quantity is the probability that a random permutation of $n$ elements does not fix any of the first $k$ elements.

- Find the limit of a recursive sequence
- Does there exist a sequence $\{a_n\}_{n\ge1}$ with $a_n < a_{n+1}+a_{n^2}$ such that $\sum_{n=1}^{\infty}a_n$ converges?
- equation involving the integral of the modular function of a topological group
- Limit of $\left(1-\frac{1}{n^2}\right)^n$
- Uniform continuity on $$ and $ $ $\implies$ uniform continuity on $$.
- Archimedean Property and Real Numbers

- Closed-form of the sequence ${_2F_1}\left(\begin{array}c\tfrac12,-n\\\tfrac32\end{array}\middle|\,\frac{1}{2}\right)$
- Darboux Theorem Proof
- Calculating $\lim_{x\to0} \left\lfloor\frac{x^2}{\sin x \tan x}\right\rfloor$
- Show that $\lim\limits_{n \to \infty} \sup\limits_{k \geq n} \left(\frac{1+a_{k+1}}{a_k}\right)^k \ge e$ for any positive sequence $\{a_n\}$
- Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?
- How do solve this integral $\int_{-1}^1\frac{1}{\sqrt{1-x^2}}\arctan\frac{11-6\,x}{4\,\sqrt{21}}\mathrm dx$?
- Solving a differential equation?
- Evaluate the $\lim_{x \to \ -\infty} (x + \sqrt{x^2 + 2x})$
- What is the derivative of $x^n$?
- Does $\sum a_n$ converge if $a_n = \sin( \sin (…( \sin(x))…)$

Here’s a heuristic idea, based on the strong law of large numbers (SLLN). A rigorous proof can be made using the central limit theorem (CLT), as in my new answer.

First write

$$

I = \frac{1}{{n!}}\int_0^\infty {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x} = \int_0^\infty {\bigg(1 – \frac{1}{x}} \bigg)^k \frac{{x^n e^{ – x} }}{{\Gamma (n + 1)}}\,{\rm d}x.

$$

Now, if $X_1,\ldots,X_{n+1}$ are i.i.d. exponential(1) random variables, then their sum $X_1 + \cdots + X_{n+1}$ has gamma density $x^n e^{-x} / \Gamma(n+1)$, $x > 0$. Hence,

$$

I = {\rm E} \bigg[ 1 – \frac{1}{{X_1 + \cdots + X_{n + 1} }}\bigg]^k = {\rm E}\bigg[1 – \frac{{n + 1}}{{X_1 + \cdots + X_{n + 1} }}\frac{1}{{n + 1}}\bigg]^k .

$$

By SLLN, $(n + 1)^{ – 1} \sum\nolimits_{i = 1}^{n + 1} {X_i }$ converges almost surely to ${\rm E}[X_1 ] = 1$ as $n \to \infty$. So this suggests the approximation

$$

I \approx \bigg(1 – \frac{1}{{n + 1}}\bigg)^k = \bigg(1 – \frac{1}{{n + 1}}\bigg)^{n(k/n)} \approx e^{ – k/n}.

$$

A rigorous proof can be made using the central limit theorem (CLT), as follows.

Since

$$

\frac{1}{{n!}}\int_0^1 {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x} \to 0

$$

as $n \to \infty$, it suffices to consider the integral from $1$ to $\infty$. Let $c>0$ be arbitrary but fixed, and let $X_i$ be as in my previous answer. Define $f_n {(x)} = x^n e^{-x} / \Gamma(n+1)$, $x>0$, and put $n'=n+1$. Then, since $f_n$ is the density of $\sum\nolimits_{i = 1}^{n'} {X_i }$,

$$

\frac{1}{{n!}}\int_1^{n' – c\sqrt {n'} } {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x} \leq \int_0^{n' – c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } – n'}}{{\sqrt {n'} }} \le – c \bigg).

$$

By the CLT, since the $X_i$ have unit mean and unit variance, the probability on the right-hand side tends to $\Phi(-c)$ as $n \to \infty$, where $\Phi$ denotes the distribution function of the standard normal distribution.

Similarly,

$$

\frac{1}{{n!}}\int_{n' + c\sqrt {n'} }^\infty {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x} \leq \int_{{n'} + c\sqrt {n'} }^\infty {f_n (x)\,{\rm d}x} = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^{n'} {X_i } – n'}}{{\sqrt {n'} }} > c \bigg),

$$

and, by the CLT, the probability on the right-hand side tends to $1 – \Phi(c)$ as $n \to \infty$.

Next, note that

$$

\bigg(1 – \frac{1}{{n' – c\sqrt {n'} }}\bigg)^k \int_{n' – c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} \leq

\frac{1}{{n!}}\int_{n' – c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x}

$$

and

$$

\frac{1}{{n!}}\int_{n' – c\sqrt {n'} }^{n' + c\sqrt {n'} } {x^{n – k} (x – 1)^k e^{ – x} \,{\rm d}x} \leq \bigg(1 – \frac{1}{{n' + c\sqrt {n'} }}\bigg)^k \int_{n' – c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x}.

$$

By the CLT,

$$

\int_{n' – c\sqrt {n'} }^{n' + c\sqrt {n'} } {f_n (x)\,{\rm d}x} = {\rm P}\bigg(-c \leq \frac{{\sum\nolimits_{i = 1}^{n'} {X_i } – n'}}{{\sqrt {n'} }} \leq c \bigg) \to 2 \Phi(c) -1

$$

as $n \to \infty$. Combining it all, and noting that

$$

\bigg(1 – \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^k = \bigg(1 – \frac{1}{{n' \pm c\sqrt {n'} }}\bigg)^{n(k/n)} \approx e^{ – k/n},

$$

the result follows by choosing $c$ sufficiently large. [Note that first we choose $c$ sufficiently large, then we let $n \to \infty$.]

Update: This argument only holds for some cases. See italicized additions below.

Let $S_{n,k}$ denote the number of permutations in which the first $k$ elements are not fixed. I published an expository paper on these numbers earlier this year. See “Deranged Exams,” (College Mathematics Journal, 41 (3): 197-202, 2010). Aravind’s formula is in the paper, as are several others involving $S_{n,k}$ and related numbers.

Theorem 7 (which I also mention in this recent math.SE question) is relevant to this question. It’s

$$S_{n+k,k} = \sum_{j=0}^n \binom{n}{j} D_{k+j},$$

where $D_n$ is the number of derangements on $n$ elements. See the paper for a simple combinatorial proof of this.

Since $D_n$ grows as $n!$ via $D_n = \frac{n!}{e} + O(1)$ (see Wikipedia’s page on the derangement numbers), and *if $k$ is much larger than $n$*,

the dominant terms in the probability

$\frac{S_{n+k,k}}{(n+k)!}$ are the $j = n$ and $j = n-1$ terms from the Theorem 7 expression. Thus we have

$$\frac{S_{n+k,k}}{(n+k)!} \approx \frac{D_{n+k} + n D_{n+k-1}}{(n+k)!} \approx \frac{1}{e}\left(1 + \frac{n}{n+k}\right) \approx e^{-1} e^{\frac{n}{n+k}} = e^\frac{-k}{n+k},$$

where the second-to-last step uses the first two terms in the Maclaurin series expansion for $e^x$.

*Again, this argument holds only for (in my notation) $k$ much larger than $n$.*

This is not an answer but an observation that the quantity is equal to $\sum_{i=0}^{k} \frac{{(-1)}^i}{n!}{k \choose i}(n-i)!$.

Continuing Aravind’s observation, write it like

$$

1 – \frac{k}{n} + \frac{1}{2!} \left( \frac{k}{n} \right)^2 \frac{1-1/k}{1-1/n}

– \frac{1}{3!} \left( \frac{k}{n} \right)^3 \frac{(1-1/k)(1-2/k)}{(1-1/n)(1-2/n)}

$$

$$+ \dots

+ (-1)^k \frac{1}{k!} \left( \frac{k}{n} \right)^k \frac{(1-1/k)(1-2/k)\dots (1-(k-1)/k)}{(1-1/n)(1-2/n) \dots (1-(k-1)/n)}.

$$

If $k$ and $n$ are large, this seems to be close to the $k$th degree Maclaurin polynomial

for $e^z$ evaluated at $z=-k/n$ (although I don’t have an estimate of the error).

- Show that product of primes, $\prod_{k=1}^{\pi(n)} p_k < 4^n$
- Are all the finite dimensional vector spaces with a metric isometric to $\mathbb R^n$
- Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$
- Seifert matrices and Arf invariant — Cinquefoil knot
- Tautological line bundle over $\mathbb{RP}^n$ isomorphic to normal bundle? Also “splitting” of transition functions
- I'm having trouble with a proof by induction
- Representing Elementary Functions in a CAS
- Calculate moment of inertia of Koch snowflake
- Outer measure is countably subadditive
- How is it possible for two random variables to have same distribution function but not same probability for every event?
- rank of the free group: $\mathrm{rank} F_X=|X|$
- Euler's Phi Function Worst Case
- Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?
- Factorial Moment of the Geometric Distribution
- “Closest pair of points” algorithm