No hay que olvidar la Combinatoria. En las últimas entradas nos hemos dedicado más a propiedades numéricas, por lo que en esta, como cambio, estudiaremos un tema de base combinatoria que desembocará en un caso concreto de números de Lah.
Si deseamos construir una aplicación sobreyectiva de un
conjunto de n elementos sobre otro
de n-1, debemos buscar un origen
para cada elemento del segundo conjunto, pero siempre nos sobrará uno del primero,
que habrá que asignarlo a un elemento imagen ya elegido, con lo que este
poseerá dos orígenes.
Esta situación se entiende bien con el símil de cajas y
bolas. Deseamos meter n bolas en n-1 cajas, de forma que todas las cajas
tengan al menos una bola y que todas las bolas estén asignadas a alguna caja.
Esto nos obliga a meter dos bolas en una caja concreta.
En la imagen observamos una aplicación sobreyectiva de los
números {1, 2, 3, 4, 5} sobre las cajas {1, 2, 3, 4} En ella hemos tenido que
hacer convivir el 3 y el 5 en una misma caja.
¿Cuántas formas existen de construir este tipo de
aplicaciones? Con esta pregunta llegaremos a un caso particular de los llamados
números de Lah, cuando el parámetro k es igual a 2
(Imagen tomada de https://en.wikipedia.org/wiki/Lah_number)
Deducción
de la fórmula
Observemos lo que hemos hecho:
En primer lugar debemos llenar las cajas con una bola. Como
tenemos 5 bolas para 4 cajas, las posibles elecciones serán variaciones sin repetición de 5 sobre 4,
es decir, 5*4*3*2. Esas serían las formas de completar las cajas. Siempre nos
sobrará una bola, que podemos asignar a una de las 4 cajas posibles, luego
debemos multiplicar por 4 y quedaría 5*4*3*2*4. Si razonamos así, estaríamos
contando estos casos como dobles. Por ejemplo, en la imagen, repetiríamos el
razonamiento con el 3 y con el 5, con lo que habríamos contado 5*4*3*2*4=480,
en lugar de los 240 que efectivamente existen, es decir, 5*4*3*2*4/2=4*5!/2
Generalizando: El número de aplicaciones sobreyectivas de
{1,2…n} sobre {1, 2,…n-1} equivale a un caso concreto de números de Lah (cuando
k=2) dado por la expresión
Estos números están publicados en http://oeis.org/A001286
1, 6, 36, 240, 1800, 15120, 141120, 1451520, 16329600,
199584000, 2634508800, 37362124800, 566658892800, 9153720576000,
156920924160000, 2845499424768000, 54420176498688000, 1094805903679488000, …
Entre ellos figura el 240 que hemos deducido para n=5:
4*5!/2=2*120=240
Para el caso de n=3 el número de aplicaciones sería 6.
Representamos las cajas mediante paréntesis: (12)(3), (13)(2), (23)(1), (1)(23),
(2)(13), (3)(12)
Hay que advertir que dentro de cada paréntesis no influye el
orden.
La fórmula para Excel sería (N-1)*FACT(N)/2
Podemos deducir la fórmula con otro razonamiento: Se puede
decidir antes de nada qué dos bolas comparten caja. Esta elección se hace
mediante combinaciones sin repetición de
n elementos tomados de 2 en 2, es decir n(n-1)/2. Una vez elegido el par, hay que asignarle una caja, y
esto supone n-1 posibilidades, con
lo que quedaría un total de n(n-1)/2*(n-1)
casos. Así nos quedarán libres n-2
bolas y n-2 cajas. Entre ellas se
pueden formar (n-2)! aplicaciones
biyectivas, que completarían el proceso. En resumen, tendríamos n(n-1)/2*(n-1)*(n-2)!=(n-1)*n!/2, como
ya sabíamos.
Una
propiedad derivada
En el razonamiento anterior usamos la expresión n(n-1)/2 como número de combinaciones,
pero también es un número triangular de orden n-1, que equivale a la suma de
consecutivos 1+2+3+…+n-1, luego estos números también se pueden expresar como
Lo puedes ver en esta tabla de Excel:
La parte central coloreada representa el conjunto de términos del sumatorio. A la derecha figuran en negrita los números de Lah para k=2, suma de los anteriores, y a la izquierda los factoriales. De esta tabla se pueden extraer unas representaciones interesantes para los números de Lah que estamos estudiando. Te dejamos que lo deduzcas:
6=(1+2)*1*2
36=(1+2+3)*1*2*3
240=(1+2+3+4)*1*2*3*4
1800=(1+2+3+4+5)*1*2*3*4*5
15120=(1+2+3+4+5+6)*1*2*3*4*5*6
Queda atractivo.
Recurrencia
Finalizamos este estudio con una breve referencia a la generación
de cada número respecto al anterior y al número de orden. No hay que razonar
mucho para comprender que
Se puede reproducir esta generación escribiendo una columna de
índices y aplicar esta fórmula en una segunda columna a partir del 1:
No importa que el factor multiplicador no sea entero, porque se compensa con los factores del anterior número de Lah (sabemos que el resultado ha de ser entero).
No hay comentarios:
Publicar un comentario