Submulticonjuntos (2)

 Representación numérica de un multiconjunto

Con lo visto hasta ahora en la anterior entrada, lo esencial en un multiconjunto lo constituyen las multiplicidades. La naturaleza de los elementos no influye apenas en los conteos. Es un fenómeno similar a la descomposición en factores primos, que muchas funciones dependen tan solo de los exponentes. Esto nos permite representar un multiconjunto como un número, de forma unívoca. De las posibilidades existentes (hay variantes en la tarea de representar un multiconjunto mediante un número, como, por ejemplo, los números de Heinz), elegiremos aquí las siguientes:

·      Ordenamos las multiplicidades de mayor a menor (para que el número resultante sea lo más pequeño posible)

·      A cada multiplicidad correspondiente a un elemento dado le asignamos un número primo repetido, siguiendo el orden natural (algunos autores comienzan con el 1). En caso de empate, no hay problema, porque resulta el mismo número.

·   Si multiplicamos todos esos primos, resultará un número que poseerá una relación biunívoca con el conjunto.

Por ejemplo, en la palabra ZARAGOZA ordenamos las multiplicidades vistas en la entrada anterior: 3 de A, 2 de Z y 1 del resto de caracteres, R, G y O.

Sustituimos cada multiplicidad por números primos repetidos y ordenados:

2*2*2*3*3*5*7*11=27720.

Este número identifica, de forma unívoca, a todos los multiconjuntos con la serie de multiplicidades 3, 2, 1, 1, 1. Cada submulticonjunto de ellos se relacionará con un divisor de 27720, por el criterio general de divisibilidad, en el que los factores primos de los divisores son subconjuntos de los correspondientes en 27720.

Pedimos los divisores de 27720 con bigomega=3 (tres factores primos) en cualquier buscador, o con la función siguiente:

Function dosfact$(n, k)

Dim i

s = ""

For i = 2 To n

If n / i = n \ i Then

If bigomega(i) = k Then

s = s + ajusta(i) + "  "

End If

End If

Next i

dosfact = s

End Function

La aplicamos a 27720 con k=3, por ejemplo, y resultan 19 divisores:

8  12  18  20  28  30  42  44  45  63  66  70  99  105  110  154  165  231  385 

Ahora usamos la técnica de las combinaciones acotadas que vimos en la entrada anterior, con Cartesius:

xtotal=3

xt=2,3,5,7,11

creciente

contar(2)<4

contar(3)<3

contar(5)<2

contar(7)<2

contar(11)<2

Coincide el número de submulticonjuntos de tres elementos:

Son también 19.

Cálculo directo

Usando la técnica combinatoria de eliminar combinaciones prohibidas resultaría:

Combinaciones con repetición:

COMBINAT(5+3-1;3) = COMBINAT(7;3 = 35

Hay que restarle uno por la combinación prohibida (3,3,3) y para el 5, 7 y 11, cinco cada uno para eliminar aquellos en los que están repetidos: (5,5,2), (5,5,3), …

En total: 35-1-5-5-5=19

Para casos más complicados habría que acudir a técnicas parecidas al Principio de Inclusión y exclusión, sumando y restando posibilidades. Para cálculos mediante fórmulas directas, las incluidas en https://arxiv.org/abs/2009.01233, m-submultisets and m-permutations of multisets elements

Para encontrar el número total de submulticonjuntos sustituiríamos XTOTAL=3 en Cartesius por XRANGO=8, que los abarca todos menos el conjunto vacío. Resultan 95.

Si contamos el conjunto vacío, serían 96, representado en los divisores de 27720 por el número 1.

Si ahora calculamos la función TAU (número de divisores) por su fórmula, usando las multiplicidades, resulta:

TAU(27720)=(1+3)(1+2)(1+1)(1+1)(1+1)=4*3*2*2*2=96

El paralelismo entre subconjuntos y divisores queda comprobado. Es interesante.

Submulticonjuntos (1)

Un multiconjunto (multiset en inglés) es un conjunto en el que se permite la repetición de algunos o todos sus elementos un número determinado de veces, llamado multiplicidad del elemento. Al conjunto de elementos tomados sin repetición se le llama conjunto subyacente,

Un ejemplo claro son los conjuntos de tiradas en Combinatoria, las extracciones de bolas con repetición o el conjunto de los factores primos de un número. En todos ellos se permite que algunos elementos estén repetidos, Otro ejemplo típico es el las letras de una palabra. Por ejemplo, las letras de la palabra ZARAGOZA. Aquí se permite que la Z se repita dos veces y la A tres. Su conjunto subyacente es ZARGO.

Formalmente, un multiconjunto es un conjunto de elementos que son pares del tipo (elemento, multiplicidad). Por ejemplo, las letras de ZARAGOZA forman el multiconjunto

{(A,3),(Z,2),(R,1),(G,1),(O,1)}

Un submulticonjunto de un multiconjunto es otro multiconjunto cuyos elementos pertenecen al multiconjunto inicial con multiplicidades no mayores que las del mismo.

Así, GOZAR es submulticonjunto de ZARAGOZA, pero no lo es ARROZ, porque la R tiene una multiplicidad mayor.

Combinaciones con repetición

En todas las cuestiones que siguen, la base son las combinaciones con repetición. Podremos usar la fórmula para m objetos tomados de n en n, fórmula elemental y conocida:

Tomemos como ejemplo el conjunto {2,3,4,5} Si deseamos construir todas las combinaciones con repetición de 3 en 3, según la fórmula, deberemos obtener en total, usando el lenguaje de las hojas de cálculo:

COMBINAT(4+3-1,3) = COMBINAT(6,3)=6*5*4/6=5*4=20

En efecto, con nuestra herramienta Cartesius se puede comprobar.

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Basta exigir estas tres condiciones:

xtotal=3

xt=2,3,4,5

creciente

Se pide crear tres columnas con contenido 2,3,4,5 y solo se exige que los arreglos sean crecientes, para que resulten combinaciones y no variaciones. El resultado es el esperado, 20 combinaciones con repetición.

 

Combinaciones con repetición acotadas

Si en lugar del conjunto {2,3,4,5} eligiéramos el multiconjunto {2,3,3,4,4,5} deberíamos tener en cuenta que sus subconjuntos no pueden presentar más frecuencias que las determinadas, un 2, dos 3, dos 4 y un 5.

En Cartesius tendríamos que acotar las frecuencias, para que resultaran subconjuntos. Podría ser así:

 

xtotal=3

xt=2,3,4,5

creciente

contar(2)<2

contar(3)<3

contar(4)<3

contar(5)<2

 

Se restringen las frecuencias, con lo que resultan submulticonjuntos:

El resultado sería:

Las combinaciones se han reducido a 10.

¿Cómo llegar a ese número sin usar Cartesius?

En nuestro caso, al número 20 habría que restarle las combinaciones en las que el 3 se repite más de dos veces, y también aquellas en las que ocurre lo mismo con el cuatro. Después eliminaríamos aquellas en las que el 2 o el 5 se repitieran más de una vez

Sería:

Combinaciones totales: CR(4,3)=COMBINAT(6,3)=20

Combinaciones no válidas con el 2: Hay que desechar aquellas combinaciones en las que el 2 se repita dos o tres veces, es decir, fijamos el 2 dos veces, y nos quedan combinaciones de cuatro elementos tomados de uno en, es decir:

CR(4,1)=COMBINAT(4,1)=4. Igual ocurre con el 5

Combinaciones no válidas para el 3: Siguiendo el mismo razonamiento, fijamos el 3 tres veces y queda CR(4,0)=1, e igual para el 4

Nos quedaría prohibir que dos elementos sobrepasaran la multiplicidad, pero eso no ocurre y hemos terminado:

Número de submulticonjuntos: 20-4-4-1-1=10

Así que la idea es, para eliminar combinaciones, fijar cada elemento en su multiplicidad y uno más, y desarrollar lo que queda:

CR(4,3)-CR(4,1)-CR(4,1)-CR(4,0)-CR(4,0)

Se comprende que con más elementos el cálculo se complica, pero este sería el camino correcto.

Números de pastel

Estos números constituyen una extensión natural de los traducidos como “Catering perezoso” (o también como “Cortador perezoso”), que ya se han estudiado en este blog. Si aquellos contaban el máximo de cortes rectilíneos sobre una tarta o pizza, considerados en dos dimensiones (todos frontales a la superficie mayor de la tarta), aquí se trata de cortar un cubo o una tarta mediante cortes planos que actúan sobre tres dimensiones. Buscaremos siempre el número máximo de partes, por lo que no se consideran planos paralelos, ni cortes paralelos, ni varios planos incidentes en el mismo punto.

Siguiendo las ideas de Peter C. Heinig en https://oeis.org/A000125, podemos contemplar tres escalas de complejidad en estos cortes:

Una dimensión, cortes sobre una recta. Es evidente que el número máximo de regiones para n cortes es

C₁(n)=binomial(n,0)+binomial(n,1)=1+n

En el caso de un plano, vimos, en la sucesión de catering perezoso, https://hojaynumeros.blogspot.com/2026/02/el-catering-perezoso.html, que el número era: n(n+1)/2+1, que también se puede escribir como

C₂(n)= binomial(n,0)+binomial(n,1)+binomial(n,2)

En nuestro caso actual, sobre tres dimensiones, es fácil razonar que su expresión es C(n+1,3)+n+1=(n+1)n(n-1)/6+n+1, lo que nos llevaría a

C₃(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3)

Lo vemos:

Una tarta, con el corte mediante un solo plano se divide en dos partes, y se cumple C(1)=0+1+1=2

Para dos cortes obtenemos cuatro partes como máximo, y se cumple:

C(2)=3*2*1/6+2+1=4

Aquí podemos seguir por inducción: Supongamos efectuados los n-1 cortes primeros. Al cortarlos con un nuevo plano, si ese número es máximo, se formarán en el nuevo plano el máximo de cortes posible, que sabemos que es C₂(n-1), y serían elementos de la sucesión del catering perezoso, luego C₃(n)= C₃(n-1)+C₂(n-1), y quedaría:

C₃(n)= C₃(n-1)+(n-1)n/2+1=n(n-1)(n-2)/6+n+(n-1)n/2+1

Mediante el programa wxMaxima comprobamos la identidad entre este resultado y el propuesto. En el recorte de pantalla observamos además que las expresiones se pueden simplificar bastante:

Por una parte, hemos obtenido una fórmula manejable:

Por otra, se ha comprobado en el razonamiento que C₃(n)= C₃(n-1)+C₂(n-1) y, por tanto, que es válida la sugerencia de:

C₃(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3)

Con esta comprobación se ha descubierto también que estos números son la suma de los cuatro primeros elementos de la fila n del triángulo de Pascal:

Esta propiedad nos permite identificar los números de pastel con el número de subconjuntos de un conjunto de n elementos cuyo cardinal no supere los tres elementos. Expresado de otra forma, la suma del número de combinaciones de n elementos tomados de 0, 1, 2 o 3 elementos.

Al igual que ocurría con la sucesión del catering perezoso, la existencia de una fórmula tan directa hace inútil la búsqueda de otro algoritmo o función. Basta organizar una tabla con esa fórmula:

Coinciden los valores extraídos del triángulo de Pascal y con los publicados en https://oeis.org/A000125,

 Recurrencia

Con la fórmula básica se puede llegar a números de orden grande, pero quizás se prefiera una recurrencia por la rapidez de cálculo. En la página de OEIS citada se propone la siguiente:

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).

Bastará, pues, crear una columna con los cuatro primeros en una hoja de cálculo y después aplicar la fórmula a esos cuatro y rellenar hacia abajo hasta el punto que deseemos.

Comienzo:

Escribimos los cuatro primeros, y al quinto le aplicamos la fórmula de recurrencia.

Segundo paso

Rellenamos hacia bajo la fórmula:

De esta forma, en segundos, llegamos al orden que deseemos:

Las recurrencias lineales son muy útiles para construir tablas de forma casi instantánea.

 

Triángulo trinomial

Al igual que construíamos el triángulo de Pascal para binomiales sumando cada dos consecutivos, podemos definir el triángulo trinomial si cada coeficiente es la suma de los tres situados en la fila anterior y sobre él. Los coeficientes de los extremos serán suma de dos o de uno, como si a izquierda y derecha del triángulo existieran ceros. Así quedaría con una hoja de cálculo.

 

A diferencia de los binomiales, estos coeficientes del triángulo forman filas de longitud impar, 2n+1, por lo que se puede hablar siempre de términos centrales, que en la imagen son 1, 1, 3, 7 y 19.

Este proceso equivale a la siguiente recurrencia:

Como curiosidad, John D. Cook relaciona estos números con los pasos del rey en el ajedrez para llegar a las distintas posiciones

 (ver https://www.johndcook.com/blog/2025/05/16/trinomial-coefficients-and-kings/)

Este triángulo posee diversas propiedades, tal como ocurría con el binomial. Por ejemplo, la primera diagonal de la izquierda contiene los números naturales, 1, 2, 3, 4, … y la segunda los triangulares, 1, 3, 6, 10, 15, …Igualmente, si en los binomiales la suma por filas era 2ⁿ, aquí es 3ⁿ. Por ejemplo, 1+3+6+7+6+3+1=27=3³

Estos números se pueden interpretar también como los coeficientes de la potencia (1+x+x²)ⁿ

Por ejemplo, para n=4 nos queda, en wxMaxima:

Los coeficientes coinciden con los de la fila 4 del triángulo.

Para distinguir estos coeficientes de los binomiales, se suele añadir un 2 a la derecha de su símbolo. El resto queda igual porque vemos que dependen de solo dos parámetros. Así que, a partir de ahora, los representaremos así:

En ese símbolo k es un entero que cumple -n ≤ k ≤ n, por lo que puede tomar valores negativos. Lo podemos interpretar como la diferencia entre el lugar central de la fila y el del término definido.

Cálculo directo

Según la Wikipedia, existe una fórmula para el cálculo directo:

Usa un sumatorio algo complicado, por lo que es más directo y formativo el seguir la recurrencia definida.

Por recurrencia

El esquema de recurrencia ya presentado se puede traducir a una función directa, en la que dados n y k nos devuelva el coeficiente correspondiente en el triángulo trinomial. Para ello, traducimos las filas de hoja de cálculo a dos vectores u(i) y v(i) que comiencen y terminen con ceros, y con ellos ir construyendo la recurrencia hasta llegar al coeficiente deseado:

Function trinomial2(n, k)

Dim u(50), v(50), i, j, h, t

 

 

For i = 1 To 2 * n + 3: u(i) = 0: v(i) = 0:  Next I ‘Se rellenan los vectores con ceros

u(n + 3) = 1 ‘Primer coeficiente

For i = 1 To n ‘Se trabaja hasta la fila n

For j = 3 To 2 * n + 3 ‘Longitud de la fila contando con ceros iniciales

v(j) = u(j - 1) + u(j) + u(j + 1) ‘Recurrencia

Next j

For h = 3 To 2 * n + 3: u(h) = v(h: Next h ‘Se copia v(i) en u(i)

For h = 1 To 2 * n + 1: v(h) = 0: Next h ‘Y se rellena con ceros

Next i

t = u(n + k + 3) ‘Se localiza el coeficiente pedido

trinomial2 = t

End Function

 

Aunque parece algo complejo, funciona con rapidez. En la imagen se recogen los coeficientes correspondientes a n=5 y n=6:

Coeficientes centrales

Los números centrales de cada fila poseen importancia propia. Por eso, en OEIS, se les dedican muchas referencias y descripciones de propiedades. Aquí sólo se darán algunos detalles, remitiendo para un estudio completo a la página https://oeis.org/A002426.

Su cálculo no es difícil. En la página mencionada se usa la definición como coeficientes de  (1+x+x²)ⁿ, pero eligiendo el coeficiente número n. Se propone este código PARI de fácil comprensión, extendido aquí con un bucle FOR:

a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n))

for(k=0,20,print1(a(k),", "))

Su resultado, en la página oficial de PARI es:

Coincide con lo publicado.

Con nuestra función trinomial2(n,k) basta dar a k el valor 0. Así se ha efectuado para crear esta columna de Excel:

Una interpretación interesante de estos números es la de David Callan, que los identifica con el número de sucesiones de n elementos tomados del conjunto (1, 2, 3, … n), crecientes en sentido amplio, en las que ningún elemento se repite más de dos veces. Propone como ejemplo si n = 3, las sucesiones son 112, 113, 122, 123, 133, 223, 233, es decir, son siete como indica su coeficiente central.

He añadido la condición FMAX a mi herramienta Cartesius (https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius) y, aunque aún no está publicada, la he usado para comprobar esta propiedad. He concretado las condiciones siguientes:

xtotal=5

xt=1..5

FMAX<3

Creciente

Con ellas se combinan en arreglos crecientes los números del 1 al 5, con la condición de que la frecuencia máxima sea 2, tal como plantea David Callan, y se han obtenido 51 posibilidades, como corresponde al coeficiente central de orden 5. Este recorte contiene los primeros y su total:

 

 

 

Coeficientes trinomiales

Los coeficientes trinomiales son una extensión de los binomiales, definidos estos como

Y que son los coeficientes del binomio de Newton:

De forma análoga se pueden definir los coeficientes trinomiales, propios de un trinomio similar al anterior.

En realidad, los binomiales se podrían expresar de otra forma:

A partir de aquí podemos explicar mejor la definición de coeficientes trinomiales:

También, al igual que con los binomiales, los podemos identificar con los coeficientes de la potencia de un trinomio:

Las demostraciones son similares a las del caso binomial.

Esta fórmula produce siempre resultados enteros positivos, debido al teorema de que un producto de k números consecutivos decrecientes es siempre múltiplo de los k primeros números enteros positivos. Es fácil recordar que coincide con el número de permutaciones con repetición en las que se fija el número de cada una.

Para entender esto mejor podemos descomponer la definición en tres bloques. Lo vemos con un ejemplo:

A la vista de este esquema de tres cocientes, observamos que el tercer número de la definición no influye en el resultado, luego podemos usar sólo n₁ y n₂. Incluso estos son intercambiables, los que nos lleva a que el coeficiente trinomial se puede expresar como

En nuestro ejemplo, usando la función COMBINAT de Excel y Calc, nos quedaría:

COMBINAT(8;2)*COMBINAT(6;3)=560

COMBINAT(8;3)*COMBINAT(5;2)=560

 

Cálculo de un coeficiente trinomial en la práctica

Si no se desea depender de la función COMBINAT, se puede calcular directamente. El problema con el cálculo práctico de un coeficiente de este tipo es que los factoriales alcanzan números muy grandes. Si usamos calculadora o bien hoja de cálculo, los resultados pasan a coma flotante y se pierde el carácter entero de estos coeficientes. Por ello, es conveniente usar el desarrollo del párrafo anterior: dividir los números consecutivos a partir de m entre el primer factorial, los siguientes entre el segundo, y parar el cálculo, porque el tercer factorial produce un uno. En VBasic y otros lenguajes se puede construir una función similar a la siguiente:

Function trinomial(m, x, y, z)

Dim t, k, v

If x + y + z <> m Then trinomial = 0: Exit Function’ Datos no válidos

t = m: k = x: v = 1

While k > 0

v = v * t / k: t = t - 1: k = k – 1 ‘Divide factores consecutivos entre el primer coeficiente. Es el primer combinatorio de la fórmula.

Wend

k = y

While k > 0

v = v * t / k: t = t - 1: k = k – 1’ Igual, en el segundo coeficiente para calcular el segundo combinatorio.

Wend

trinomial = v

End Function

Presenta un pequeño riesgo de redondeo inadecuado, pero suele funcionar bastante bien. Devuelve un cero si los coeficientes de abajo no suman el de arriba. No analiza si los datos son enteros.

Es muy sencillo el traslado a cualquier otro lenguaje de programación, por ejemplo, en PARI, con un rango de datos y resultados mucho mayor:

trinomial(m, x, y, z)=my(t=m,k=x,v=1);while(k>0,v=v*t/k;t-=1;k-=1);k=y;while(k>0,v=v*t/k;t-=1;k-=1);v*(x+y+z==m)

Tal como se esperaba, los valores de estos coeficientes pueden ser grandes. Aquí tenemos un ejemplo:

Al ser la primitiva definición simétrica respecto a los índices de abajo, el número total de posibles coeficientes trinomiales para un índice superior m dado, es el de particiones de m en tres conjuntos. Por ejemplo, para m=5 las particiones son (5,0,0), (4,1,0), (3,2,0), (3,1,1), (2,2,1), que se corresponden con los posibles valores de los coeficientes, que son 1, 5, 10, 20 y 30. Se comprende que, en el desarrollo de (a+b+c)⁵, se tendrán que repetir, como vemos en el siguiente desarrollo:

Con nuestra herramienta Cartesius se puede encontrar el número de estos coeficientes distintos.(Ver https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Por ejemplo, para m=7 plantearíamos:

xtotal=3

xt=0..7

creciente

suma=7

 

Se interpreta que deseamos encontrar todos los tipos de sumas con resultado 7 y sin tener en cuenta el orden (creciente)

Al resultado se le han añadido manualmente los valores de los coeficientes:

Estos resultados se corresponden con el desarrollo de una potencia séptima de un trinomio:

Como era de esperar, los coeficientes aparecen muy repetidos.

Tetraedro de Pascal

Con la expresión COMBINAT(m;n₁)*COMBINAT(m-n₁;n₂) se puede construir un triángulo de coeficientes para un m dado. En una hoja de cálculo se puede visualizar bien. En la imagen figuran los correspondientes a m=7, vistos anteriormente:

Observamos que los lados del triángulo son filas del triángulo de Pascal. Si ahora apilamos triángulos según los valores de m, nos resultará un tetraedro, al que también se le llama de Pascal. En la siguiente página de Wikipedia se explica el proceso:

https://en.wikipedia.org/wiki/Pascal%27s_pyramid

La siguiente imagen pertenece a dicha página:

(Fuente: Wikipedia https://en.wikipedia.org/wiki/Pascal%27s_pyramid)

Para quienes deseéis profundizar en el tema. La lectura de esta página es recomendable.

Recurrencia

Es fácil la comprobación de esta recurrencia para calcular coeficientes trinomiales:

En realidad, este es el fundamento del tetraedro de Pascal.