Cómo invertir la $n$ elija $k$ ¿fórmula?

Question

Si quiero encontrar cuántas formas posibles hay de elegir k entre n elementos, sé que se puede utilizar la sencilla fórmula que aparece a continuación:

$$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$

Pero, ¿y si quiero ir al revés?

Es decir, sé que quiero tener $X$ posibles combinaciones, y quiero encontrar todos los pares de $n$ y $k$ que me dará ese número de combinaciones.

Por ejemplo, si el número de combinaciones que quiero es $3$ Quiero una fórmula/método para encontrar que todos los pares que darán como resultado ese número de combinaciones son $(3,1)$ y $(3,2)$

Sé que podría probar todos los pares posibles, pero esto sería poco práctico para números grandes.

Pero, ¿quizás no haya una forma más fácil de hacerlo que el enfoque de la fuerza bruta?

Answer 1

Si $X$ es tan grande como $10^7$ entonces es sencillo hacerlo con ayuda del ordenador. Primero hay que tener en cuenta las desigualdades elementales $$\frac{n^k}{k!} \ge {n \choose k} \ge \frac{(n-k)^k}{k!}$$

que están cerca de ser ajustados cuando $k$ es pequeño. Si $X = {n \choose k}$ entonces se deduce que $$n \ge \sqrt[k]{k! X} \ge n-k$$

por lo que $$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$$

por lo que para los fijos $k$ sólo tiene que comprobar como máximo $k+1$ posibles valores de $n$ que es manejable cuando $k$ es pequeño. Se puede acelerar este proceso mediante la factorización de $X$ si quieres y aplicando Teorema de Kummer (el primer punto de esa sección del artículo), pero el cálculo de los coeficientes binomiales para $k$ pequeño es sencillo, por lo que probablemente no sea necesario.

Para los más grandes $k$ , tenga en cuenta que siempre puede asumir WLOG que $n \ge 2k$ desde ${n \choose k} = {n \choose n-k}$ por lo que se puede suponer que $$X = {n \choose k} \ge {2k \choose k} > \frac{4^k}{2k+1}$$

(ver La prueba de Erdős del postulado de Bertrand para conocer los detalles de esta última desigualdad). En consecuencia, sólo hay que comprobar un número logarítmico de valores de $k$ (en función de $X$ ). Por ejemplo, si $X \le 10^7$ sólo tiene que comprobar hasta $k = 14$ .

En total, aplicando el algoritmo anterior sólo hay que comprobar $O(\log(X)^2)$ pares $(n, k)$ y cada comprobación requiere en el peor de los casos $O(\log(X))$ multiplicaciones de números como máximo tan grandes como $X$ junto con, en el peor de los casos, una comparación de dos números de tamaño $O(X)$ . Así que el algoritmo anterior tarda un tiempo polinómico en $\log(X)$ .

Editar: Debería ser totalmente factible sólo el factor $X$ a los tamaños de los que hablas, pero si quieres aplicar la parte del teorema de Kummer del algoritmo a tamaños mayores $X$ En realidad, no hay que tener en cuenta completamente $X$ probablemente puedas hacer las comparaciones del teorema de Kummer sobre la marcha calculando la mayor potencia de $2$ que entra en $X$ entonces $3$ entonces $5$ etc., y almacenarlos según sea necesario. Como segundo paso, si no se $X$ ni el coeficiente binomial particular ${n_0 \choose k_0}$ que estás probando son divisibles por un primo pequeño dado $p$ se puede apelar al teorema de Lucas. Por supuesto, hay que decidir en algún momento cuándo dejar de probar los primos pequeños y limitarse a probar la igualdad real.

Answer 2

Aquí hay una implementación en código de la respuesta de Qiaochu. El algoritmo, para recapitular, es:

• Entrada $X$ . (Queremos encontrar todos los $(n, k)$ tal que $\binom{n}{k} = X$ .)

• Para cada $k \ge 1$ tal que $4^k/(2k + 1) < X$ ,

  • Dejemos que $m$ sea el menor número tal que $m^k \ge k!X$ .

  • Para cada $n$ de $\max(m, 2k)$ a $m + k$ (inclusive),

    • Si $\binom{n}{k} = X$ , rendimiento $(n, k)$ y $(n, n-k)$ .

Está escrito en Python (elegí este lenguaje por la legibilidad y los enteros grandes nativos, no por la velocidad). Tiene cuidado de usar sólo aritmética de enteros, para evitar cualquier error debido a la precisión de punto flotante.

La versión que aparece a continuación está optimizada para evitar volver a calcular $\binom{n+1}{k}$ desde cero después de haber calculado $\binom{n}{k}$ esto lo acelera de manera que, por ejemplo, para $\binom{1234}{567}$ (a $369$ -) tarda (en mi portátil) 0,4 segundos en lugar de los 50 segundos que tarda la versión no optimizada en el primera revisión de esta respuesta.

#!/usr/bin/env python
from __future__ import division
import math

def binom(n, k):
    """Returns n choose k, for nonnegative integer n and k"""
    assert k >= 0
    assert n >= 0
    assert k == int(k)
    assert n == int(n)
    k = min(k, n - k)
    ans = 1
    for i in range(k):
        ans *= n - i
        ans //= i + 1
    return ans

def first_over(k, c):
    """Binary search to find smallest value of n for which n^k >= c"""
    n = 1
    while n ** k < c:
        n *= 2
    # Invariant: lo**k < c <= hi**k
    lo = 1
    hi = n
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        if mid ** k < c:
            lo = mid
        else:
            hi = mid
    assert hi ** k >= c
    assert (hi - 1) ** k < c
    return hi

def find_n_k(x):
    """Given x, yields all n and k such that binom(n, k) = x."""
    assert x == int(x)
    assert x > 1
    k = 0
    while True:
        k += 1
        # https://math.stackexchange.com/a/103385/205
        if (2 * k + 1) * x <= 4**k:
            break
        nmin = first_over(k, math.factorial(k) * x)
        nmax = nmin + k + 1
        nmin = max(nmin, 2 * k)
        choose = binom(nmin, k)
        for n in range(nmin, nmax):
            if choose == x:
                yield (n, k)
                if k < n - k:
                    yield (n, n - k)
            choose *= (n + 1)
            choose //= (n + 1 - k)

if __name__ == '__main__':
    import sys
    if len(sys.argv) < 2:
        print('Pass X in the command to see (n, k) such that (n choose k) = X.')
        sys.exit(1)
    x = int(sys.argv[1])
    if x == 0:
        print('(n, k) for any n and any k > n, and (0, 0)')
        sys.exit(0)
    if x == 1:
        print('(n, 0) and (n, n) for any n, and (1, 1)')
        sys.exit(0)
    for (n, k) in find_n_k(x):
        print('%s %s' % (n, k))

Ejemplo de carreras:

~$ ./mse_103377_binom.py 2
2 1
~$ ./mse_103377_binom.py 3
3 1
3 2
~$ ./mse_103377_binom.py 6 
6 1
6 5
4 2
~$ ./mse_103377_binom.py 10
10 1
10 9
5 2
5 3
~$ ./mse_103377_binom.py 20
20 1
20 19
6 3
~$ ./mse_103377_binom.py 55
55 1
55 54
11 2
11 9
~$ ./mse_103377_binom.py 120
120 1
120 119
16 2
16 14
10 3
10 7
~$ ./mse_103377_binom.py 3003
3003 1
3003 3002
78 2
78 76
15 5
15 10
14 6
14 8
~$ ./mse_103377_binom.py 8966473191018617158916954970192684
8966473191018617158916954970192684 1
8966473191018617158916954970192684 8966473191018617158916954970192683
123 45
123 78
~$ ./mse_103377_binom.py 116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440
116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440 1
116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440 116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477439
1234 567
1234 667