Multiconjunto

Matematicamente, um multiconjunto é a generalização de um conjunto, de tal forma que permite a repetição de elementos.

Por exemplo, M = {a, b, c, c, d, e, e} é um multiconjunto distinto de X = {a, b, c, d, e}, mas se M e X fossem conjuntos, teríamos M=X.

Definição formal

Um multiconjunto é definido como um par $(A, m)$, onde $A$ é um conjunto qualquer, e $m: A \rightarrow \mathbb{N}$ a função que associa a cada elemento de A um número natural, onde consideramos a definição de números naturais que não contêm o zero, ou seja $\mathbb{N} = \{1,2,3, ... \}$.

A multiplicidade de um elemento a é definido como $m(a)$.

Representamos um multiconjunto com a mesma notação que usamos para conjuntos, mas citamos $m(i)$ vezes um elemento i do multiconjunto.

Por exemplo, o multiconjunto M com o par (A, m), tal que $A = \{a,b,c,d,e\}$ e m(a)=1, m(b)=1, m(c)=2, m(d)=1, m(e)=2, é representado por $M = \{a,b,c,c,d,e,e\}$. A ordem dos elementos, assim como nos conjuntos, não importa.

Como os multiconjuntos são uma generalização de conjuntos, um multiconjunto B é um conjunto quando $m(i) = 1$ para todo $i \in B$.

Exemplos

Multiconjuntos aparecem naturalmente em vários contextos:

• Na fatoração: a forma natural de se expressar a fatoração de um número natural ou um polinômio é através de multiconjuntos. Por exemplo, os fatores primos de 12 são {2, 2, 3}, e os fatores primos de 18 são {2, 3, 3}.
• A solução de uma equação polinomial é um multiconjunto, já que é importante indicar a multiplicidade de cada raiz.

Cardinalidade de um multiconjunto

A cardinalidade de um multiconjunto $M = (A, m)$ é definida como:

$\sum_{i \in A} m(i)$ .

Seleção com repetição

Em análise combinatória, multiconjunto é uma seleção com repetição. Em uma seleção em combinatória, a ordem não é importante.

Para calcular o número de multiconjuntos com k elementos escolhendo entre n tipos de elementos.

$\left\langle \begin{matrix}n \\ k \end{matrix}\right\rangle =CR^{k}_{n} = C^{k}_{n+k-1} = {n + k -1 \choose k} =\frac{(n+k-1)!}{k!(n-1)!}={n+k-1 \choose n-1}$

Exemplos

1-Quantos tipos de dominós existem com números de 0 a 7?
É só selecionar dois dos 8 números possíveis. Neste caso os espaços nos dominós são iguais.

$\left\langle \begin{matrix}8 \\ 2 \end{matrix}\right\rangle = {8 + 2 -1 \choose 2} =\frac{(8+2-1)!}{2!(8-1)!}=\frac{9!}{2!(7)!}=36$

2-De quantas formas podemos distribuir 18 bolas iguais em 4 caixas diferentes?
Podemos considerar a seqüência seguinte:

$\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet$

Que é o mesmo que achar o número de soluções para a equação:

$X4+X3+X2+X1=18$, $Xi=$número de bolas da i-ésima caixa

Equivale a escolher 18 caixas entre 4, já que pode repetir. Então

$\left\langle \begin{matrix}4 \\ 18 \end{matrix}\right\rangle = {18+4-1 \choose 18} = \frac{(21)!}{18!(21-18))!}=\frac{(21)!}{3!(18)!}=1330$

Você também pode utilizar a técnica dos *'s (asteriscos) e | (palitos), sendo neste caso: $X4+X3+X2+X1=18$ : 18 asteríscos e 3 palitos: Assim, temos a combinação direta de asteríscos e palitos::$\frac{(* + |)!}{*!(|!)}=1330$

Outra forma de resolver esse problema é observando a figura acima. Há 18 bolas e 3 barras verticais indicando quatro caixas, cada uma em uma posição. Podemos permutar os termos que no total são 18+4-1 (18 bolas e 3 barras) e descontar as repetições já que as bolas são iguais e as barras também. Fazendo permutação de elementos iguais.

$\frac{(21)!}{3!(18)!}=1330$