3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Question: when we are solving for $k$, is $n$ fixed? $\endgroup$ – Eevee Trainer Mar 27 at 7:52
  • $\begingroup$ Yes, @Eevee Trainer, when solving for k, you can assume n is fixed/known. $\endgroup$ – Brian Kennedy Mar 27 at 15:15
  • $\begingroup$ I think you misunderstood the algorithm you linked; it is not solving for just $n$, it solving for $k$ and $n$ simultaneously. So the code given there takes care of your first problem. $\endgroup$ – Mike Earnest Mar 28 at 16:29
  • $\begingroup$ Also your last problem; given the value $X$ in $X=\binom{n+k-1}{k}$, apply the $C$-inverse algorithm to find $m,k$ so $X=\binom{m}{k}$, then let $n=m-k+1$. $\endgroup$ – Mike Earnest Mar 28 at 16:33
  • 1
    $\begingroup$ Reversing $C(n,k)$ We know that $C(n,k)=\frac{n(n-1)\dots(n-k+1)}{1.2.3\dots k}$ To compute $k$ in $k$ steps, let $$ X_0=X \\ X_1=\frac{X_0}{n}\\ X_2=\frac{2X_1}{n-1}\\ X_3=\frac{3X_2}{n-2}\\ \vdots $$ If $X_i>1$, compute $X_{i+1}$. When $X_i=1$, we know that $k=i$ and $k=n-i$ are the desired solutions. Reversing RC(n,k) This time, $RC(n,k)=\frac{n(n+1)\dots (n+k-1)}{1.2.3\dots k}$. Let $$ X_0=X \\ X_1=\frac{X_0}{n}\\ X_2=\frac{2X_1}{n+1}\\ X_3=\frac{3X_2}{n+2}\\ \vdots $$ If $X_i>1$, compute $X_{i+1}$. When $X_i=1$, $k=i$ is the desired solution. $\endgroup$ – Angela Richardson May 19 at 7:01
3
+50
$\begingroup$

enter image description here

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.

enter image description here

This curve looks like a quadratic, so I tried to fit a quadratic of the form $y=x(n-x)$.

enter image description here

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

enter image description here

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

enter image description here

enter image description here

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

$\endgroup$
  • $\begingroup$ This is an amazing post... getting to watch the formulation of one of those approximations where it seems "magic happens here". I am implementing this now so that I can more thoroughly test its accuracy. Two questions for you, while I do that: (1) Can you use this same approximation to solve for 'n' such that I can avoid the binary search within the bounds that I am having to do now? (2) Can you create a similar formulation for Combinations with Repetitions? I'll be attacking those questions myself once I prove out this much. In any case, thanks so much!!! $\endgroup$ – Brian Kennedy May 23 at 18:32
  • $\begingroup$ So far the answer to both those questions is ‘No,’ but I will work on them both. $\endgroup$ – tomi May 23 at 22:00
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for working out those bounds... it'll take me a bit to work through that math to verify, but this definitely appears to be a workable solution. Thanks so much! $\endgroup$ – Brian Kennedy May 23 at 18:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, Claude. I'm hoping I'll be able to avoid Newton iterations; but yes, that is a workable solution. Greatly appreciated. $\endgroup$ – Brian Kennedy May 23 at 18:41
  • $\begingroup$ @BrianKennedy. You are very welcome ! I think that Newton would be the easiest way (because of the availability of lngamma(x) function) $\endgroup$ – Claude Leibovici May 24 at 2:50

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.