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.