Multiconjunto

Em matemática, um multiconjunto (ou ainda multiset ou mset) é uma modificação do conceito de um conjunto que, diferentemente de um conjunto,^[1] permite várias instâncias para cada um de seus elementos. O número de instâncias fornecidas para cada elemento é chamado de multiplicidade.

A cardinalidade ou "tamanho" de um multiconjunto é a soma das multiplicidades de todos os seus elementos. Por exemplo, no multiset {a, a, b, b, b, c} as multiplicidades dos membros a, b e c são respectivamente 2, 3 e 1 e, portanto, a cardinalidade desse multiset é 6.

Um multiconjunto é definido como um par ( A , m ) {\displaystyle (A,m)} , onde A {\displaystyle A} é um conjunto qualquer, e m : A → N {\displaystyle 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 N = { 1 , 2 , 3 , . . . } {\displaystyle \mathbb {N} =\{1,2,3,...\}} .

A multiplicidade de um elemento a é denotada por m ( a ) {\displaystyle m(a)} .

Representamos um multiconjunto com a mesma notação que usamos para conjuntos, mas citamos m ( i ) {\displaystyle 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 } {\displaystyle 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 } {\displaystyle M=\{a,b,c,c,d,e,e\}} , melhor < 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 {\displaystyle m(i)=1} para todo i ∈ B {\displaystyle i\in B} .

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.

A cardinalidade de um multiconjunto M = ( A , m ) {\displaystyle M=(A,m)} é definida como:

∑ i ∈ A m ( i ) {\displaystyle \sum _{i\in A}m(i)} .

Em análise combinatória, um multiconjunto é o resultado de uma seleção com repetição, em que a ordem não é importante. O número de multiconjuntos de cardinalidade k, a partir de n elementos, pode ser representado por ( ( n k ) ) {\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)} ,^[2] uma notação parecida a usada para os coeficientes binomiais, ( n k ) {\displaystyle \textstyle {n \choose k}} .

Este número é dado pela fórmula seguinte^[3][4]:

( ( n k ) ) = n + k − 1 C k = ( n + k − 1 k ) = ( n + k − 1 ) ! k ! ( n − 1 ) ! = ( n + k − 1 n − 1 ) {\displaystyle \left(\!\!{n \choose k}\!\!\right)=^{n+k-1}C_{k}={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.

( ( 8 2 ) ) = ( 8 + 2 − 1 2 ) = ( 8 + 2 − 1 ) ! 2 ! ( 8 − 1 ) ! = 9 ! 2 ! ( 7 ) ! = 36 {\displaystyle \left(\!\!{8 \choose 2}\!\!\right)={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:

∙ ∙ ∙ ∙ ∙ ∙ ∣ ∙ ∙ ∣ ∙ ∙ ∙ ∣ ∙ ∙ ∙ ∙ ∙ ∙ ∙ {\displaystyle \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:

X 4 + X 3 + X 2 + X 1 = 18 {\displaystyle X4+X3+X2+X1=18} , X i = {\displaystyle Xi=} número de bolas da i-ésima caixa

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

( ( 4 18 ) ) = ( 18 + 4 − 1 18 ) = ( 21 ) ! 18 ! ( 21 − 18 ) ) ! = ( 21 ) ! 3 ! ( 18 ) ! = 1330 {\displaystyle \left(\!\!{4 \choose 18}\!\!\right)={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: X 4 + X 3 + X 2 + X 1 = 18 {\displaystyle X4+X3+X2+X1=18}  : 18 asteriscos e 3 palitos: Assim, temos a combinação direta de asteriscos e palitos:: ( ∗ + | ) ! ∗ ! | ! = 1330 {\displaystyle {\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.

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

3-De quantos modos podemos comprar 3 sorvetes onde há 6 sabores distintos disponíveis?
A Combinação Simples nos daria 6 C 3 = 20 {\displaystyle ^{6}C_{3}=20} maneiras, contudo levaria em conta apenas os sorvetes de sabores distintos! A resposta correta será a Combinação por Repetição:

( ( 6 3 ) ) = ( 6 + 3 − 1 3 ) = ( 8 3 ) = 56 {\displaystyle \left(\!\!{6 \choose 3}\!\!\right)={6+3-1 \choose 3}={8 \choose 3}=56} maneiras.

• Conjunto

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e