Cada columna del Triángulo de Pascal está dada por un polinomio completamente diferente, por lo tanto, dado un valor para x y k en [matemáticas] x = \ binom {n} {k} [/ matemáticas], puede encontrar el polinomio para la columna k, establecer es igual a x y resuelve para n. Este polinomio tendrá k soluciones, pero la que desee será un número entero positivo, por lo que puede usar una herramienta de software para obtener las raíces, y luego elegir la que parece estar cerca de un número entero positivo.
Pero usar el teorema del calcetín navideño (identidad del stock de hockey) es probablemente más fácil, algorítmicamente hablando. Simplemente comience a sumar los términos de la columna [matemáticas] k-1 [/ matemáticas] hasta llegar a [matemáticas] x [/ matemáticas]. Para hacerlo, será necesario agregar exactamente términos [matemáticos] n-1 [/ matemáticos].
Alternativamente, si uno prefiere implementar un algoritmo para invertirlo, uno de los métodos más rápidos puede ser hacer una búsqueda binaria en la columna k, conectando cada candidato n en la fórmula del coeficiente binomial. Como cada columna del triángulo de Pascal es monotónica, la solución se puede encontrar en el tiempo [matemáticas] O (\ log ^ 3 (x) / k) [/ matemáticas] (suponiendo multiplicaciones de tiempo cuadráticas). Aquí hay un algoritmo de Python que lo hace (tan eficientemente como podría hacerlo) junto con algún código para demostrar que funciona:
def binom (n, k):
salida = 1
para j en el rango (1, k + 1):
salida = salida * (n-k + j) / j
salida de retorno
- Al escribir una cadena binaria de longitud 20 usando 10 1s y 10 0s, puede que nunca haya más 0s que 1s en un momento dado. ¿Cuántas cuerdas existen?
- Si hay N personas en una fila, y cada hora mata al azar a una persona con un índice impar, y los sobrevivientes vuelven a indexar, ¿quién tendrá más probabilidades de sobrevivir?
- Cómo entender por qué el algoritmo de Euclides para GCD es verdadero
- ¿Son los teoremas algo más que axiomas contorneados?
- ¿Es ‘n es par’ en una implicación ‘si n es par entonces n ^ 2 es par’ una declaración?
def binomialinverse (x, k):
a, b, t = 0,0,1
mientras que t <x: a = b + 1; b = 2 * a; t = binom (k + b, k)
mientras que a <byt! = x:
t = binom (k + (a + b) / 2, k)
si t> = x: b = (a + b) / 2
más: a = (a + b) / 2
devuelve k + b si t == x más Falso
importar al azar
para x en random.sample (xrange (1000,10000), 100):
y = random.randrange (x)
afirmar binomialinverse (binom (x, y), y) == x
¿Sin embargo, para escribir una fórmula en k y x que solo genera la n? Sospecho que no se puede hacer solo con las operaciones habituales a las que estás acostumbrado.