Approximation of permutation

Question

I am stuck on an old exam problem where they ask to prove that a permutation of shape $\frac{L!}{(L-N)!}$ is roughly equal to $L^N$.

I know that to start, the equation has to be approximated using Stirling approximation $$\ln(N!)=N*\ln(N)-N)$$ resulting in $$L^L\cdot\exp(-N)*(L-N)^{(L-N)}.$$ We also know that $L>>N$. However, I don't see how this helps me get to the final result.

If somebody could give a hint, that would be appreciated.

Thanks in advance!

Answer 1

$$\frac{L!}{(L-N)!}=L(L-1)(L-2) \cdots (L-(N-1))=$$

$$=L.L(1-\tfrac1L).L(1-\tfrac2L). \cdots L(1-\tfrac{N-1}{L})=$$

$$=L^N(1-\tfrac1L)(1-\tfrac2L) \cdots (1-\tfrac{N-1}{L})=$$

$$\approx L^N$$

because all factors between parentheses are close to $1$ due to property $L >> N$.

Answer 2

Actually, $L ≫ N$ is not enough$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$ to guarantee that $\lfrac{L!}{(L-N)!} \sim L^N$ as $L,N → ∞$. In fact, $\lfrac{L!}{L^N·(L-N)!}$ does not tend to $1$ if $L \sim N^{3/2}$. There is an elementary way to bound the ratio you want, namely $C = \lfrac{L}{L}·\lfrac{L-1}{L}·\lfrac{L-2}{L}·\ldots·\lfrac{L-(N-1)}{L}$.

Firstly, $\Big(\lfrac{L}{L}·\lfrac{L-(N-1)}{L}\Big)^{N/2} ≤ C ≤ \Big(\lfrac{L-(N-1)/2}{L}\Big)^N$ since $(a-c)·(b+c) ≤ a·b$ for every $a,b,c∈ℝ_{≥0}$ such that $a ≤ b$. For convenience, let $r = \lfrac{N-1}{L} ≪ 1$. Then we have lower bound $C ≥ (1-r)^{N/2} ≥ \exp(\ln(1-r)·N/2) ≥ \exp((-r-r^2)·N/2)$ and upper bound $C ≤ (1-r/2)^N ≤ \exp(-r/2)^N = \exp(-r·N/2)$.

Now, $\exp(-r·N/2) = \exp\!\Big({-}\lfrac{(N-1)·N}{2L}\Big)$, so if $N^2 ≪ L$ then $C → 1$, but if $N^2 ≫ L$ then $C → 0$. At the boundary, namely if $\lfrac{N^2}{2L} → a ∈ ℝ$, then $C → \exp(a)$. All three cases are clearly possible as $L ≫ N → ∞$.

Answer 3

$$P=\frac{L!}{(L-N)!}\implies \log(P)=\log[L!]-\log[(L-N)!]$$ Using Stirling approximation twice $$\log(P)=N \log (L)-\frac{(N-1) N}{2 L}+O\left(\frac{1}{L^2}\right)$$ $$P=e^{\log(P)}=L^N\left(1-\frac{(N-1) N}{2 L}+O\left(\frac{1}{L^2}\right) \right)\sim L^N$$