Multiconxunto

En matemáticas, un multiconxunto ou mset (en inglés: multiset) é unha modificación do concepto de conxunto que, a diferenza deste, permite múltiples instancias para cada un dos seus elementos. O número de aparicións de cada elemento denomínase a súa multiplicidade nese multiconxunto. En consecuencia, existe un número infinito de multiconxuntos que conteñen só os elementos $a$ e b, pero con diferentes multiplicidades. Por exemplo:

O multiconxunto ${a, b}$ contén só os elementos $a$ e b, cada un deles cunha multiplicidade de 1.
No multiconxunto ${a, a, b}$ , o elemento $a$ ten unha multiplicidade de 2, namentres a de $b$ é 1.
No multiconxunto ${a, a, a, b, b, b}$ , tanto $a$ como $b$ teñen unha multiplicidade igual a 3.

Malia ser tres multiconxuntos diferentes, de ser considerados como conxuntos serían exactamente o mesmo, posto que teñen os mesmos elementos, $a$ e $b$ . Porén, do mesmo xeito ca nos conxuntos, e en contraste coas tuplas, a orde dos elementos non é relevante. Xa que logo, ${a, a, b}$ e ${a, b, a}$ son dous xeitos diferentes de designar o mesmo multiconxunto. Para distinguir entre conxuntos e multiconxuntos, ás veces emprégase unha notación diferentes, con corchetes; é dicir, $[a, a, b]$ no canto de ${a, a, b}$ .^[1]

A cardinalidade ou "tamaño" dun multiconxunto é a suma das multiplicidades de todos os seus elementos. Por exemplo, a cardinalidade de ${a, a, b, b, b, c}$ é igual a 6, xa que os seus elementos $a$ , $b$ e $c$ teñen multiplicidades de 2, 3 e 1, respectivamente.

Historia

O matemático holandés Nicolaas Govert de Brujin cuñou o termo inglés multiset na década dos 70, segundo Donald Knuth.^[2] Porén, o concepto de multiconxunto precede en séculos a aparición desta palabra. O propio Knuth atribúe ao polímata indio Bhāskarāchārya o primeiro estudo coñecido dos multiconxuntos, xa que describiu as permutacións de multiconxuntos cara a 1150.

Exemplos

Un dos exemplos máis simples e naturais é o multiconxunto dos factores primos dun número natural $n$ . Aquí o conxunto de elementos subxacente é o conxunto de factores primos de $n$ . Por exemplo, o número 120 ten a descomposición en factores primos $120=2^{3}3^{1}5^{1},$ que dá o multiconxunto ${2, 2, 2, 3, 5}$ .

Un exemplo relacionado é o multiconxunto de solucións dunha ecuación alxébrica. Unha ecuación cuadrática, por exemplo, ten dúas solucións. No entanto, nalgúns casos ambas as dúas solucións son o mesmo número. Así, o multiconxunto de solucións da ecuación pode ser ${3, 5}$ , ou pode ser ${4, 4}$ . Neste último caso ten unha solución de multiplicidade 2. De xeito máis xeral, o teorema fundamental da álxebra afirma que as solucións complexas dunha ecuación polinómica de grao $d$ sempre forman un multiconxunto de cardinalidade $d$ .

Contando multiconxuntos

Véxase tamén: Método bóla trazo.

O número de multiconxuntos de cardinalidade $k$ , con elementos tomados dun conxunto finito de cardinalidade $n$ , ás veces chámase coeficiente multiconxunto ou número multiconxunto. Este número é escrito por algúns autores como $\textstyle \left(\!\!{n \choose k}\!\!\right)$ , unha notación que se quere parecer á dos coeficientes binomiais; utilízase, por exemplo, en (Stanley, 1997), e podería pronunciarse " $n$ sobre múltiple $k$ " para asemellarse a " $n$ sobre $k$ " para ${\tbinom {n}{k}}.$ Do mesmo xeito que na distribución binomial están implicados os coeficientes binomiais existe a distribución binomial negativa na que se producen os coeficientes multiconxunto.

Os coeficientes multiconxunto non deben confundirse cos coeficientes multinomiais que aparecen no teorema multinomial e non están relacionados.

O valor dos coeficientes multiconxunto pódese dar explícitamente como

\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},

onde a segunda expresión é un coeficiente binomial;^[a] de feito, moitos autores evitan a notación separada e simplemente escriben coeficientes binomiais.

Así, o número de eses multiconxuntos é o mesmo que o número de subconxuntos de cardinalidade $k$ dun conxunto de cardinalidade $n + k - 1$ .

A analoxía cos coeficientes binomiais pódese realzar escribindo o numerador na expresión anterior como factorial ascendente

\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},

e con iso temos unha expresión similar á dos coeficientes binomiais que usan un factorial descendente:

{n \choose k}={n^{\underline {k}} \over k!}.

Exemplos

Co conxunto ${1, 2}$ que ten cardinalidade 2 podemos formar 4 multiconxuntos de cardinalidade 3. Para comprobolo temos $(n=2,k=3$ ), e os conxuntos posíbeis son, ${1, 1, 1}$ , ${1, 1, 2}$ , ${1, 2, 2}$ , ${2, 2, 2}$ .

Botando contas co anterior

n+k-1=3+2-1=4

podemos comparar o resultado co coeficiente binomial. Serían os subconxuntos de 4 elementos tomados de 3 en 3, por exemplo para o conxunto

{1, 2, 3, 4}

temos

{1, 2, 3}

,

{1, 2, 4}

,

{1, 3, 4}

,

{2, 3, 4}

que tamén son 4 elementos.

Unha forma sinxela de probar a igualdade dos coeficientes multiconxuntos e dos coeficientes binomiais indicados anteriormente implica representar os multiconxuntos do seguinte xeito.

Primeiro, considere a notación para multiconxuntos que representarían

{a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d}

(6 as, 2 bes, 3 ces, 7 des) nesta forma (notación bóla trazo):

• • • • • • | • • | • • • | • • • • • • •

Este é un multiconxunto de

k = 18

elementos feito de elementos de 4 conxuntos

n = 4

. O número de caracteres que inclúe tanto puntos como liñas verticais usado nesta notación é

18 + 4 - 1

. O número de liñas verticais é 4 − 1. O número de multiconxuntos de cardinalidade 18 é entón o número de formas de organizar as liñas verticais

4 - 1

entre os 18 + 4 − 1 caracteres. De forma equivalente, é o número de formas de ordenar os 18 puntos entre os caracteres

18 + 4 - 1

. Isto é

{4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,

así podemos ver o valor do coeficiente multiconxunto e as súas equivalencias:

{\begin{aligned}\left(\!\!{4 \choose 18}\!\!\right)&={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3},\\[1ex]&={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},\\[1ex]&={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;1\cdot 2\cdot 3\quad } }},\\[1ex]&={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.\end{aligned}}

Da relación entre coeficientes binomiais e coeficientes multiconxuntos, despréndese que o número de multiconxuntos de cardinalidade $k$ nun conxunto de cardinalidade $n$ pódese escribir

\left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.

e tamén,

\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).

Relación de recorrencia

Unha relación de recorrencia para os coeficientes multiconxunto pódese dar como $\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{para }}n,k>0$ con $\left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{e}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.$

Xeneralización e conexión coa serie binomial negativa

A fórmula multiplicativa permite ampliar a definición de coeficientes multiconxuntos substituíndo $n$ por un número arbitrario $α$ (negativo, real ou complexo):

\left(\!\!{\alpha  \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{para }}k\in \mathbb {N} ,\alpha {\text{ arbitrario}}.

Con esta definición temos unha xeneralización da fórmula binomial negativa (cunha das variábeis con valor 1), o que xustifica chamar aos coeficientes $\left(\!\!{\alpha \choose k}\!\!\right)$ coeficientes binomiais negativos:

(1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha  \choose k}\!\!\right)X^{k}.

Esta fórmula da serie de Taylor é válida para todos os números complexos $\alpha$ e $X$ con $| X | < 1$ . Tamén se pode interpretar como unha identidade de serie formal de potencias en $X$ , onde en realidade pode servir como definición de potencias arbitrarias de series cun coeficiente constante igual a 1.

A utilidade desta definición é que todas as identidades cumpren o que se espera para a exponenciación, en particular

(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}

,

((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )},

e fórmulas como estas pódense usar para probar identidades para o coeficiente multiconxuntos.

Se $α$ é un número enteiro non positivo $n$ , entón todos os termos con $k > - n$ son cero e a serie infinita convértese nunha suma finita. No entanto, para outros valores de $α$ , incluídos os enteiros positivos e os números racionais, a serie é infinita.

Notas

↑ Hein 2003, pp. 29-30.
↑ Knuth 1998.

↑ A fórmula ${\tbinom {n+k-1}{k}}$ non funciona para $n = 0$ (onde necesariamente tamén $k = 0$ )

Véxase tamén

Bibliografía

Hein, James L. (2003). Discrete Mathematics. Jones & Bartlett Publishers. ISBN 0-7637-2210-3. OCLC 45842590.
Knuth, Donald E. (1998). Seminumerical Algorithms: The Art of Computer Programming. Addison Wesley. ISBN 0-201-89684-2.

[FOOTNOTEHein200329-30-1] Hein 2003, pp. 29-30.

[FOOTNOTEKnuth1998-2] Knuth 1998.

[3] A fórmula ${\tbinom {n+k-1}{k}}$ non funciona para $n = 0$ (onde necesariamente tamén $k = 0$ )

[1]

[2]

[a]