For an engineering application, I need the inverse functions of the computations of the number of combinations and permutations.
In the thread How to reverse the $n$ choose $k$ formula? it shows how to reverse/inverse the number of combinations function…
Given:
$X = C(n, k) = \binom{n}{k} = \frac{n! }{ k!(n-k)! }$
then you can limit n to:
$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$
And thus you at most need to check k+1 possible values of n (or with a binary search, just log(k+1) checks). Great!
But how do I solve for k instead of for n? (Given n and the number of combinations, how do I compute k?)
And given instead number of Permutations:
$X = P(n, k) = \frac{n! }{ (n-k)! }$
then I believe I am correct in assuming from above that:
$\sqrt[k]{X} + k \ge n \ge \sqrt[k]{X}$
And in this case, I actually can solve for k as well since k only appears once:
$k = n – InverseLnFactorial(ln(n!) – ln(X))$
And finally, given instead CR is Combinations with Repetitions:
$X = CR(n, k) = \binom{n+k-1}{k} = \binom{n+k-1}{n-1} = \frac{ (n+k-1)! }{ k!(n-1)! }$
then I believe I am correct in assuming from above that:
$\sqrt[k]{k! X} \ge n \ge \sqrt[k]{k! X} – k$
But again, how would I then solve for k instead of n? (Given n and the number of combinations with repetitions, how would I compute k?)
In both cases of Combinations (with and without repetitions), having k appear inside two different factorial terms makes it difficult for me to find an algebraic way to solve for k. Any help, or even clue, on how to do the algebra for those two cases would be greatly appreciated!
Best Answer
I started by considering the graph of $y=_nC_x$ - illustrated above.
I then looked at the natural logarithm - after all, Stirling's formula gives factorials as powers.
This curve looks like a quadratic, so I tried to fit a quadratic of the form $y=x(n-x)$.
You can see that this is not quite right. I therefore tried variations of the form $y=\left(x(n-x)\right)^p$ until I found a good fit with $p={3 \over 4}$
I don't know why this works, but it seems to. I'll now work on creating an inverse function, which should be quite easy.
We have the relationship $\ln(_nC_k) \approx ak^{3 \over 4}(n-k)^{3 \over 4}$
where $a=\frac{\ln\left(_nC_{n \over 2}\right)}{\left({n \over 2}\right)^{3 \over 4}\left({n \over 2}\right)^{3 \over 4}}$
$k^{3 \over 4}(n-k)^{3 \over 4}=\frac{\ln\left(_nC_k\right)}a $
$k(n-k)=\left(\frac{\ln\left(_nC_k\right)}a\right)^{4 \over 3} $
Let's call this $k(n-k)=b$, where $b=\left(\frac{\ln\left(_nC_k\right)}a\right)^{4 \over 3} $
Then $kn-k^2=b$ can be rewritten $k^2-kn+b=0$
$k_1=\frac{n-\sqrt{n^2-4b}}{2}$
$k_2=\frac{n+\sqrt{n^2-4b}}{2}$
I've tested this and the values it gives for $k$ are pretty close - probably only need to test integers one or two above and below the value of $k_1$.
I would really appreciate an explanation of why this works!
An explanation, why this works by Alex Ravsky.
By Stirling’s formula, for each natural $m$ there exists a number $0<\theta<1$ such that $$m!=\sqrt{2\pi m}\left(\frac me\right)^m e^{\frac \theta{12m}}.$$ Thus $$\ln(m!)=\tfrac12(\ln 2+\ln\pi+\ln m)+m(\ln m - 1)+O\left(\frac {1}{m}\right).$$
Let $k=\lambda n$ for $0<\lambda<1$. Then
$$\ln {n \choose k}=\ln \frac{n!}{k!(n-k)!}=$$ $$n(\ln n-1)- k(\ln k-1)-(n-k)(\ln (n-k)-1)+\frac 12(\ln n-\ln k-\ln (n-k))+O(1)=$$ $$n\ln n- k\ln k-(n-k)\ln (n-k)+\frac 12(\ln n-\ln k-\ln (n-k))+O(1)=$$ $$n\ln n- \lambda n (\ln\lambda+\ln n) -(1-\lambda)n(\ln(1-\lambda)+\ln n)+ \frac 12(\ln n-\ln\lambda-\ln n-\ln (1-\lambda)-\ln n)+O(1)=$$ $$ - \lambda n \ln\lambda -(1-\lambda)n\ln(1-\lambda)-\frac 12(\ln n+\ln\lambda+\ln (1-\lambda))+O(1)=$$ $$\left(n-\frac 12\right)f(\lambda)-\frac 12\ln n+O(1),$$
where $f(\lambda)=- \lambda \ln\lambda -(1-\lambda) \ln(1-\lambda) $.
The graphs below suggest that a function $g(\lambda)=2\sqrt{2}\ln (2)(\lambda(1-\lambda))^{3/4}$ is an extremely good approximation of $f(\lambda)$.
PS. Maybe we also can similarly obtain approximations of $\ln CR(n,k)$ and $\ln P(n,k)$ using some functions depending on $\lambda=k/n$. Remark that for $CR(n,k)$ case we allow $\lambda>1$.