¿Variaciones o combinaciones?

En el mes de julio pasado descubrí que el número 1716 equivale a un número de variaciones sin repetición y también de combinaciones sin repetición, ambas con el mismo índice superior. En efecto, 1716 = 13*12*11 = V(13,3), pero también equivale a C(13,6) o C(13,7), ya que

Se ha producido la feliz casualidad de que 13*12*11 = 6*5*4*3*2*1, y por eso se ha podido simplificar.

En esta propiedad el verdadero protagonista, a efectos de construcción de algoritmos, es el número 13, que es el que participa en ambas fórmulas, de combinaciones y variaciones. No existen muchos índices que cumplan esto. Los primeros son 8, 13, 27, 124, 725 y 5046, si imponemos la condición razonable de que el índice inferior sea mayor que 1, para evitar trivialidades.

Búsqueda “ingenua”

Para encontrar estos índices superiores podemos acudir a la definición que hemos insinuado: “Números n para los que existen dos índices k y h tales que V(n,k) = C(n,h)”. Si disponemos de las funciones C y V, basta recorrer índices para cada candidato y parar cuando se dé una coincidencia. Podemos acotar la búsqueda eligiendo para h el intervalo (2, n/2), por cuestión de simetría en los números combinatorios. Por otra parte, es claro que k ha de ser menor que h, para que tenga lugar la igualdad. En Basic de hojas de cálculo podía usarse algo así:

Public Function vari(n, k)
Dim v, i
v = 1
For i = 0 To k - 1: v = v * (n - i): Next i
vari = v
End Function

Public Function combi(n, k)
Dim v, w, i
v = 1: w = 1
For i = 0 To k - 1: v = v * (n - i): w = w * (i + 1): Next i
combi = v / w
End Function

Código para cada valor de n (aquí representado por la variable i):
a = 0 ‘variable para parar la búsqueda
k = 2
While k <= i / 2 And a = 0 ‘ se recorren los valores de k
b = combi(i, k) ‘ se encuentra el número de combinaciones b
h = 2
While h < k And a = 0 ‘se recorren los valores de h
c = vari(i, h) ‘ se encuentra el número de variaciones c
If b = c Then a = 1: m = k: n = h ‘en caso de igualdad, se para y toma nota
h = h + 1
Wend
k = k + 1
Wend

La salida será el valor m del índice k y el n del índice h. En forma de tabla estos serían los primeros valores:

Los comprobamos (salvo el 13 que ya se ha visto):

V(8,2)=8*7 = 56, C(8,3)=(8*7*6)/(3*2*1)=56

V(27,3)=27*26*25=17550, C(27,4)=(27*26*25*24)/(4*3*2*1) =27*26*25=17550

V(124,4)=124*123*122*121=225150024 = C(124,5)

Algoritmo con recursividad

En este primer intento estamos realizando más operaciones de lo debido. No es necesario calcular C(n,k) y V(n,h) en cada paso. Es mejor generar cada intento recursivamente a partir del anterior:

a = 0
k = 2
b = i
While k <= i / 2 And a = 0
b = b * (i - k + 1) / k ‘recursividad para combinaciones
h = 2
c = i
While h < k And a = 0
c = c * (i - h + 1) ‘recursividad para variaciones
If b = c Then a = 1: m = k: n = h
h = h + 1
Wend
k = k + 1
Wend

Con hoja de cálculo se llega pronto al desbordamiento de decimales. Deberemos cambiar a PARI:

for(i=3,1000,a=0;j=2;m=i;while(j<=i/2+1&&a==0,m=m*(i-j+1)/j;k=2;n=i;while(k<j&&a==0&&n<=m,n*=i-k+1;if(m==n,a=1);k+=1);j+=1);if(a==1,print(i,", ",j,", ",k,", ",m)))

Es poco legible. Contiene las mismas ideas desarrolladas con VBA, pero escritas de forma excesivamente compacta.

El resultado te será familiar, y aparece un nuevo índice, el 725:

Para seguir avanzando se requiere ya mucha paciencia, porque los cálculos se van haciendo lentos y complejos. El siguiente índice superior en aparecer es el 5046:

El valor de V(5046,7) = C(5046,8) da idea de cómo se va complicando esto. Sin embargo, nos conduce al hecho de que en

V(5046,7)=5046*5045*5044*5043*5042*5041*5040,

el último factor es el factorial de 7, lo que permite la simplificación que da lugar a la igualdad entre variaciones y combinaciones.

Casos particulares

El último ejemplo nos da una idea de la naturaleza de algunos de los índices superiores con la propiedad buscada. Es fácil entender que todo índice del tipo n!+(n-1) da lugar a un número m en el que el número de variaciones de n-1 elementos coincide con el de combinaciones de n elementos. Así ha ocurrido con muchas de las soluciones presentadas. En la siguiente tabla se han destacado en rojo las que ya conocíamos. Nos hemos detenido en el último factorial que Excel puede expresar de forma entera:

Por tanto, el número de índices adecuados es infinito, y crece a ritmo de factorial.
Los casos que faltan, como el 13, provienen de la casualidad de que un producto de números consecutivos equivalga a un factorial, que es lo que ocurre con 10*9*8 = 6! ¿Existirán más casos? Mediante una búsqueda manual descubrimos: 6*5*4=5!, lo que nos da de nuevo el candidato 8, pero esta vez con la expresión C(8,5) y la solución 56 ya vista. De ella podemos extraer la coincidencia 10*9*8*7=7!, que nos llevaría al índice 13.

Este estudio es un ejemplo más de una forma clásica de abordar problemas:

•  Usar un algoritmo sencillo, que no hace uso de propiedades especiales. Es un buen método para comenzar, pero suele ser largo y poco interesante. Así ha sido nuestro procedimiento “ingenuo”.
•  Perfeccionar el algoritmo a fin de conseguir mayor velocidad de búsqueda. En este caso se ha logrado con la recursividad.
•  Acudir a la teoría o el razonamiento. Hemos descubierto así que existen infinitos casos con la fórmula n!+n-1, más unos cuantos casos aislados. Así le hemos quitado el misterio a la cuestión planteada.