20
$\begingroup$

I'm trying to solve hard combinatorics that involve complicated factorials with large values.

In a simple case such as $8Pr = 336$, find the value of $r$, it is easy to say it equals to this: $$\frac{8!}{(8-r)!} = 336.$$

Then $(8-r)! = 336$ and by inspection, clearly $8-r = 5$ and $r = 3$.

Now this is all and good and I know an inverse function to a factorial doesn't exist as there is for functions like sin, cos and tan etc. but how would you possibly solve an equation that involves very large values compared to the above problem without the tedious guess and checking for right values.

Edit: For e.g. if you wanted to calculate a problem like this (it's simple I know but a good starting out problem) Let's say 10 colored marbles are placed in a row, what is the minimum number of colors needed to guarantee at least $10000$ different patterns? WITHOUT GUESS AND CHECKING

Any method or explanation is appreciated!

$\endgroup$
  • 3
    $\begingroup$ Stirling approximation. $\endgroup$ – Simply Beautiful Art Jan 1 '17 at 1:30
  • 1
    $\begingroup$ "In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies. $\endgroup$ – David K Jan 1 '17 at 2:01
  • 1
    $\begingroup$ FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here. $\endgroup$ – PM 2Ring Jan 1 '17 at 3:11
  • 1
    $\begingroup$ @TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049\gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$. $\endgroup$ – Barry Cipra Jan 3 '17 at 1:48
  • 1
    $\begingroup$ @TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble. $\endgroup$ – Barry Cipra Jan 3 '17 at 2:52
14
$\begingroup$

I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function: $$ n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{n!}{\sqrt{2\pi}}\right)\right)\right)-\frac12\tag{1} $$

$\endgroup$
  • 1
    $\begingroup$ And I just commented about it a few minutes ago ! Funny coïcidence ! $\endgroup$ – Claude Leibovici Jan 1 '17 at 6:13
  • 1
    $\begingroup$ Just to add a small detail, robjohn's solution is strictly exact if we use $$n=\left\lceil e^{W\left(\frac{\log \left(\frac{n!}{\sqrt{2 \pi }}\right)}{e}\right)+1}-\frac{1}{2}\right\rceil$$ $\endgroup$ – Claude Leibovici Jan 2 '17 at 4:51
  • 1
    $\begingroup$ @ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $\Gamma(n+1)$. $$n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{\Gamma(n)}{\sqrt{2\pi}}\right)\right)\right)+\frac12$$ is an approximate inverse for $\Gamma(n)$. $\endgroup$ – robjohn Jan 2 '17 at 6:58
  • $\begingroup$ It is so beautiful ! $\endgroup$ – Claude Leibovici Jan 2 '17 at 8:13
9
$\begingroup$

By Stirling's formula

$$n! \sim \sqrt{2\pi n} \left({\frac{n}{e}}\right)^n $$

So we can given a large $n!$ we can attempt to numerically solve,

$$n!=\sqrt{2\pi x} \left({\frac{x}{e}}\right)^x$$

For $x$ by Newton's method to get an approximate inverse.

The function $\mathbb{N} \to \mathbb{N}$ given by $f(n)=n!$ is increasing. Also,

$$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n} \leq n! \leq e n^{n+\frac{1}{2}}e^{-n}$$

So by numerically solving $n!=\sqrt{2\pi}x^{x+\frac{1}{2}}e^{-x}$ and $n!=ex^{x+\frac{1}{2}}e^{-x}$ we can find bounds for $n$.

$\endgroup$
6
$\begingroup$

For equations involving large factorials, I find the elementary inequalities $(n/e)^n < n! < (n/e)^{n+1}$ often useful.

Once these have been used, you can use Stirling's approximation.

These can be proved by induction from the elementary inequalities $(1+1/n)^n < e < (1+1/n)^{n+1}$.

$\endgroup$
  • 2
    $\begingroup$ So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns? $\endgroup$ – TripleA Jan 1 '17 at 1:36
3
$\begingroup$

Would you be fine with an algorithm instead of a mathematical function?

Solve $nPx = p$ for $x$:

x = 0
while p > 1:
    p /= n
    n--
    x++
return x

Solve $xPr = p$ for $x$:

x = r
while p > 1:
    x++
    p /= x
return x

Solve $x!=y$ for $x$:

x = 1
while y > 1:
    x++
    y /= x
return x

Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:

$$ x^{10}\ge10000\\ x\ge10000^{1/10}\approx2.512\\ x=3 $$

$\endgroup$
-1
$\begingroup$

The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$

Factoring $5040$ as a factorial $5040= 7\times 6\times 5\times 4\times 3\times 2\times 1$ , and $7$ is the largest number of that factorial $\implies x = 7$ In your problem $8!/336 = (8 – r)! , r = ?$

$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$

$120 = 5\times 4\times 3\times 2\times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) \implies r = 3.$

$\endgroup$
  • $\begingroup$ Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users. $\endgroup$ – James Dec 10 '18 at 13:12

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.