Inverso de un factorial

Question

Estoy tratando de resolver combinatorias difíciles que involucran factoriales complicados con valores grandes.

En un caso simple como $8Pr = 336$, encontrar el valor de $r$, es fácil decir que es igual a esto: $$\frac{8!}{(8-r)!} = 336.$$

Luego $(8-r)! = 336$ y haciendo inspección, claramente $8-r = 5$ y $r = 3$.

Ahora esto está todo bien y sé que una función inversa para un factorial no existe como sí existe para funciones como seno, coseno y tangente, etc. pero ¿cómo podrías posiblemente resolver una ecuación que involucra valores muy grandes en comparación con el problema anterior sin tener que adivinar y comprobar los valores correctos de manera tediosa?

Edición: Por ejemplo, si quisieras calcular un problema como este (sé que es simple pero un buen problema para empezar): Imaginemos que hay 10 canicas de colores colocadas en una fila, ¿cuál es el número mínimo de colores necesarios para garantizar al menos $10000$ patrones diferentes? SIN ADIVINANZAS Y COMPROBACIONES

Cualquier método o explicación es apreciada!

Answer 1

Acabo de escribir esta respuesta a una pregunta antigua. Usando $a=1$, obtenemos un inverso cercano para la función factorial: $$ n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{n!}{\sqrt{2\pi}}\right)\right)\right)-\frac12\tag{1} $$

Answer 2

Por la fórmula de Stirling

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

Entonces, dado un gran valor de $n!$ podemos intentar resolverlo numéricamente,

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

Para $x$ usando el método de Newton para obtener una aproximación inversa.

La función $\mathbb{N} \to \mathbb{N}$ dada por $f(n)=n!$ es creciente. Además,

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

Así que al resolver numéricamente $n!=\sqrt{2\pi}x^{x+\frac{1}{2}}e^{-x}$ y $n!=ex^{x+\frac{1}{2}}e^{-x}$ podemos encontrar límites para $n$.

Answer 3

Para ecuaciones que involucran factoriales grandes, encuentro que las desigualdades elementales $(n/e)^n < n! < (n/e)^{n+1}$ a menudo son útiles.

Una vez que estas han sido utilizadas, puedes usar la aproximación de Stirling.

Estas pueden ser demostradas por inducción a partir de las desigualdades elementales $(1+1/n)^n < e < (1+1/n)^{n+1}$.

Answer 4

¿Estarías bien con un algoritmo en lugar de una función matemática?

Resolver $nPx = p$ para $x$:

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

Resolver $xPr = p$ para $x$:

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

Resolver $x!=y$ para $x$:

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

Tu problema de ejemplo puede ser modelado sin la función factorial bastante fácilmente. Estoy asumiendo que dos canicas del mismo color son indistinguibles, que tenemos al menos 10 canicas de cada color, y que el orden de las canicas importa:

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

Answer 5

La función inversa de $y = x!$ significa obtener x en términos de $y$, es decir $x =$ el número más grande en la factorización de y como un factorial. (Donde factorizar como un factorial significa dividir $y$ por $2$, luego $3$ y así sucesivamente. Te detienes cuando obtienes $1$). Por ejemplo, vamos a tomar $5040 = x! , x = ?$

Factorizando $5040$ como un factorial $5040= 7\times 6\times 5\times 4\times 3\times 2\times 1$ , y $7$ es el número más grande de ese factorial $\implies x = 7$ En tu problema $8!/336 = (8 – r)! , r = ?$

$8!/336 = 120$ , vamos a tomar $(8 – r) = x$ , por lo tanto $120 = x! , x = ?$

$120 = 5\times 4\times 3\times 2\times 1$, y el número más grande de ese factorial $ = x = 5 = (8 – r) \implies r = 3.$