5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica Sep 3 '15 at 13:45
5
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica Sep 3 '15 at 13:49
  • $\begingroup$ Oops, the numerical values I give don't match either. I copied it from my screen incorrectly and will change it now. Thanks. $\endgroup$ – Brendan McKay Sep 3 '15 at 13:58
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.