multiconjuntos

Un multiconjunto es una generalización de un conjunto en la que los elementos pueden repetirse. A cada elemento x de un universo U se le asigna una multiplicidad m(x) ≥ 0, que indica cuántas veces x aparece en el multiconjunto. Esta estructura se puede representar como una función m: U → N∪{0} o como una lista de pares (x, m(x)).

La cardinalidad de un multiconjunto M es la suma de sus multiplicidades, |M| = ∑_x m(x). A diferencia de un conjunto, el número de elementos distintos puede ser menor que |M|. Un multiconjunto M puede contener o no ciertos elementos. Se dice que M es submulticonjunto de N si para todo x, m_M(x) ≤ m_N(x). Dos multiconjuntos son iguales cuando sus multiplicidades coinciden para cada elemento.

Operaciones: la unión M ∪ N se define por multiplicidades máximas (M ∪ N)(x) = max(m_M(x), m_N(x)); la intersección M ∩ N por multiplicidades mínimas (M ∩ N)(x) = min(m_M(x), m_N(x)); la suma M + N por la suma de multiplicidades (M + N)(x) = m_M(x) + m_N(x); y la diferencia M \ N por (M \ N)(x) = max{0, m_M(x) − m_N(x)}.

Propiedades y conteo: el número de submulticonjuntos de M es ∏_x (m_M(x) + 1). Si se eligen k elementos con repetición permitida de n tipos, el número de multiconjuntos de tamaño k es C(n + k − 1, k). En informática y combinatoria, los multiconjuntos modelan colecciones en las que el orden no importa pero las repeticiones sí, y aparecen en estructuras como contadores de elementos y en conteo de combinaciones con repetición.

Ejemplo: Considera M = {a:2, b:1} y N = {a:1, c:4}. Entonces M ∪ N = {a:2, b:1, c:4}, M ∩ N = {a:1} y M + N = {a:3, b:1, c:4}.