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.
