Inverse of a factorial

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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