# Asymptotic expression for $j$ which satisfies $\binom{n}{j}/j! \sim k$ as $n\to\infty$

Suppose $k>0$ is some fixed constant, and $n$ is a positive integer tending to infinity. Find $j\equiv j(n,k)$ such that $$\frac{\binom{n}{j}}{j!} \sim k.$$

The asymptotic expression for $(n!)^{-1}$ (https://stackoverflow.com/questions/3084937/how-to-calculate-the-inverse-factorial-of-a-real-number) was initially helpful, but upon rearranging we have equivalently to solve for $j$ in $$k\ j!^2 = n(n-1)\cdots(n-j+1),$$ and in this expression both sides depend on $j$.

I've tried Stirling's approximation, and assuming I did the calculations correct, $e \sqrt{n}$ is interesting since $j \ge e \sqrt{n}$ implies $\binom{n}{j}/j! \to 0$ whereas $j < e \sqrt{n}$ implies $\binom{n}{j}/j! \to \infty$.

In de Bruijn's book there are implicit methods, but I wasn't able to successfully apply any of the approaches.

• Note that in the range $j\approx e\sqrt n$, passing from $j$ to $j+1$ reduces the value by a factor of $\approx e^2$. Thus, you cannot hope to get closer to $k$ than within a multiplicative factor of roughly $e$. – Emil Jeřábek Sep 3 '15 at 13:45

(CORRECTED EDITION) By mucking around with expansions like Igor suggested, I found $$j \approx J(n,k)= en^{1/2} - \tfrac14\ln(n) -\tfrac12\ln(2\pi k)-\tfrac14 e^2-\tfrac12.$$

It seems good when $k$ is small but not extremally small. For example, $\binom{100}{22}/22!\approx 6.523187$ and $J(100,6.523187)\approx 21.82764$. Similarly, $\binom{1000}{82}/82!\approx 0.1454767$ and $J(1000,0.1454767)\approx 81.93$. Probably it wouldn't be immensely difficult to give error terms.

Note that the function $\binom{n}{j}/j!$ is bell-shaped with a maximum near $j=n^{1/2}$, so actually there are two solutions for many $k$. The above approximates one of them, apparently the larger one. Finding an approximation for the smaller solution should be similar.

ADDED: Of course the smaller solution for fixed $k$ is between $j=0$ and $j=1$ as soon as $n\gt k$, so probably it isn't interesting.

• The expression does not look correct, it should have the form $e\sqrt n-\frac14\log n-\frac12\log k+O(1)$. In particular, around $j\approx e\sqrt n$, passing from $j$ to $j+1$ reduces the result by a factor roughly $e^2$, hence the dependence of $j$ on $k$ should have a $-\frac12\log k$ term, not $\frac14$. – Emil Jeřábek Sep 3 '15 at 13:49
• Oops, the numerical values I give don't match either. I copied it from my screen incorrectly and will change it now. Thanks. – Brendan McKay Sep 3 '15 at 13:58

This is not quite an answer to the question (Brendan McKay already gave quite a satisfactory one), but it's worth adding that

1. $\binom{n}{j}/j!$ has an interesting probabilistic interpretation, namely it is the expected number of increasing subsequences of length $j$ in a (uniformly) random permutation of order $n$, and

2. the fact noted by the OP that this quantity goes to $0$ when $n\to\infty$ with $j>(e+\epsilon)\sqrt{n}$ can be used to give an easy proof that the expected length of a longest increasing subsequence in a random permutation of order $n$ is bounded from above by $(e+o(1))\sqrt{n}$. (And semi-conversely, the fact that $\binom{n}{j}/j!\to\infty$ for $j<(e-\epsilon)\sqrt{n}$ implies that this is the best bound that can be proved using this method. This bound is not sharp however, the correct answer for the expected length of a longest increasing subsequent is $(2+o(1))\sqrt{n}$.) See page 9 of this book.

If you take logs of both sides, and expand the left hand side in a power series around infinity (to first order), you get: $$\frac{\frac{j}{2}-\frac{j^2}{2}}{n}+j \left(-2 \log (j)-\log \left(\frac{1}{n}\right)+2\right)-\frac{1}{6 j}+\log \left(\frac{1}{j}\right)+\log \left(\frac{1}{2 \pi }\right) \approx \log k.$$ Since for any fixed $k,$ $j$ should diverge to infinity, you can throw away $j/(2n)$ and $1/(6j),$ then solve for $j.$ If you want more terms, get more terms of the asymptotic expansion of the lhs.