multiconjunto

Um multiconjunto, também chamado multiset, é uma generalização de conjunto que permite várias ocorrências do mesmo elemento. Dados um conjunto base X, um multiconjunto M sobre X é uma função m: X -> N0 que atribui a cada elemento x de X a multiplicidade m(x), o número de vezes que x ocorre. O suporte de M é { x em X : m(x) > 0 }, e o cardinal de M é |M| = soma de m(x) sobre todos os x em X. Quando o apoio é finito, diz-se que M é finito.

Pode-se representar M de várias formas: pela função de multiplicidades m, por uma lista com repetições (por exemplo, a, a, b representa M(a)=2, M(b)=1), ou por notação de expoentes, como x^m(x).

Operações comuns. Submulticonjunto: N é submulticonjunto de M se m_N(x) ≤ m_M(x) para todo x. Adição: (M + N)(x) = m_M(x) + m_N(x). Subtração: (M - N)(x) = max(m_M(x) - m_N(x), 0). Interseção: (M ∩ N)(x) = min(m_M(x), m_N(x)). União: (M ∪ N)(x) = max(m_M(x), m_N(x)). Escalar: (k · M)(x) = k · m_M(x) para k em N. Em particular, se todas as multiplicidades são 0 ou 1, M reduz-se a um conjunto.

Aplicações e contexto. Multissetes aparecem na combinatória para contagem de cenários, em bancos de dados com semântica de bag, em inventários e na teoria de grafos. Formalmente, são frequentemente modelados como funções de X para N ou como polinômios geradores, facilitando a contagem de diversas configurações.