Multiconjunto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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}, apesar de que, se M e X fossem conjuntos, teríamos M=X.

Definição formal[editar | editar código-fonte]

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\}, 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 para todo i \in B.

Exemplos[editar | editar código-fonte]

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[editar | editar código-fonte]

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

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

Seleção com repetição[editar | editar código-fonte]

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 \textstyle\left(\!\!{n\choose k}\!\!\right) [1] , uma notação parecida à usada para os coeficientes binomiais, \textstyle{n\choose k}.

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

\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.

\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:

\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(\!\!{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: X4+X3+X2+X1=18 : 18 asteriscos e 3 palitos: Assim, temos a combinação direta de asteriscos 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

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 maneiras, contudo levaria em conta apenas os sorvetes de sabores distintos! A resposta correta será a Combinação por Repetição:

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

Ver também[editar | editar código-fonte]


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
  1. Stanley, Richard P.. Enumerative Combinatorics. Vols. 1 and 2. ed. [S.l.]: Cambridge University Press, (1997, 1999). ISBN 0-521-55309-1, 0-521-56069-1.
  2. Weisstein, Eric W.. Multichoose MathWorld -- A Wolfram Web Resource. Visitado em 20 de novembro de 2014.
  3. Weisstein, Eric W.. Multinomial Coefficient MathWorld -- A Wolfram Web Resource. Visitado em 20 de novembro de 2014.