jueves, 18 de febrero de 2021

Sobreyecciones de {1, 2,…,n} sobre {1, 2,…n-1} – Unos números de Lah

 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: