Inverse/Reverse of Number of Permutations and of Number of Combinations with Repetitions?

Question

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!

Answer 1

We can find $k$ by a binary search as follows.

It is easy to check that when $n$ is sufficiently big and fixed and $k$ increases in its range, $X$ increases too. Namely, it holds uder the following assumptions.

• If $X=C(n,k)$, then we assume that $n\ge 1$, $k\ge 0$ and, since $C(n,k)=C(n,n-k)$, $k\le n/2$.
• If $X=P(n,k)$ then we assume that $n\ge 2$ and $0\le k\le n$.
• If $X=CR(n,k)$ then we assume that $n\ge 3$ and $k\ge 0$.

So we can look for $k$ first by an increasing binary search, trying $k=0,1,2,4,\dots$ until $C(n,k)>X$ and then by a decreasing binary search.

We can improve this algorithm by providing lower bounds for $k$.

Namely, if $X$ is $C(n,k)$ or $P(n,k)$ then $X\le n^k$, so $k\ge \ln X/\ln n$. A bit better bound can be obtained as follows. Since $\ln (1+x) \le x$ for any $x>-1$,

$$\ln X\le \ln\left(\prod_{i=0}^{k-1} n-i\right)=\sum_{i=0}^{k-1} \ln(n-i)=\sum_{i=0}^{k-1} \ln \left(n\left(1-\frac in\right)\right)=$$ $$ \sum_{i=0}^{k-1} \ln n +\ln \left(1-\frac in\right)\le k\ln n - \sum_{i=0}^{k-1} \frac in= k\ln n-\frac {k(k-1)}{2n}.$$

Thus $$k\ge n\ln n+\frac 12-\sqrt{\left(n\ln n+\frac 12\right)^2-2n\ln X}>\frac{\ln X}{\ln n+\tfrac 1{2n}} .$$

For $X=CR(n,k)$ we similarly obtain

$$\ln X\le \ln\left(\prod_{i=0}^{k-1} n+i\right)=\sum_{i=0}^{k-1} \ln(n+i)=\sum_{i=0}^{k-1} \ln \left(n\left(1+\frac in\right)\right)=$$ $$ \sum_{i=0}^{k-1} \ln n +\ln \left(1+\frac in\right)\le k\ln n + \sum_{i=0}^{k-1} \frac in= k\ln n+\frac {k(k-1)}{2n}.$$

Thus

$$k\ge -n\ln n+\frac 12+\sqrt{\left(n\ln n-\frac 12\right)^2+2n\ln X}.$$

Answer 2

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

Answer 3

Considering the three different cases $$X = \frac{n! }{ k!(n-k)! }=\frac{ n!}{\Gamma(k+1)\, \Gamma(n+1-k)}$$ $$ X =\frac{n! }{ (n-k)! } =\frac{ n!}{\Gamma(n+1-k)}$$ $$X= \frac{ (n+k-1)! }{ k!(n-1)! }=\frac{ \Gamma(n+k)}{\Gamma(k+1)\, n!}$$ I should look, in the real domain, for the zero of functions $$F(k)=\log (\Gamma (k+1))+\log (\Gamma (n+1-k))-\log \left(\frac{n!}{X}\right)\tag 1$$ $$G(k)=\log (\Gamma (n+1-k))-\log \left(\frac{n!}{X}\right) \tag 2$$ $$H(k)=\log (\Gamma (k+n)) -\log (\Gamma (k+1))-\log \left({n!}{X}\right)\tag 3$$since function lngamma(x) is available almost everywhere.

For $(2)$, there is a superb approximation given on this site by @robjohn(have a look here). This would provide you a very good estimate of $k$.

Since Alex Ravsky provided lower bounds, I should retain these as $k_0$ and start Newton iterations using numerical derivatives.