Multiconxunto

En matemáticas, un multiconxunto ou mset (en Modelo:Lang-en) é 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 Modelo:Math e Modelo:Math, pero con diferentes multiplicidades. Por exemplo:

• O multiconxunto Modelo:Math contén só os elementos Modelo:Math e Modelo:Math, cada un deles cunha multiplicidade de 1.
• No multiconxunto Modelo:Math, o elemento Modelo:Math ten unha multiplicidade de 2, namentres a de Modelo:Math é 1.
• No multiconxunto Modelo:Math, tanto Modelo:Math como Modelo:Math 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, Modelo:Math e Modelo:Math. Porén, do mesmo xeito ca nos conxuntos, e en contraste coas tuplas, a orde dos elementos non é relevante. Xa que logo, Modelo:Math e Modelo:Math 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, Modelo:Math no canto de Modelo:Math.Modelo:Sfn

A cardinalidade ou "tamaño" dun multiconxunto é a suma das multiplicidades de todos os seus elementos. Por exemplo, a cardinalidade de Modelo:Math é igual a 6, xa que os seus elementos Modelo:Math, Modelo:Math e Modelo:Math 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.Modelo:Sfn 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 Modelo:Mvar. Aquí o conxunto de elementos subxacente é o conxunto de factores primos de Modelo:Mvar. Por exemplo, o número 120 ten a descomposición en factores primos $$120=2^3{3}^1{5}^1,$$ que dá o multiconxunto Modelo:Math.

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 Modelo:Math, ou pode ser Modelo:Math. 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 Modelo:Mvar sempre forman un multiconxunto de cardinalidade Modelo:Mvar.

Contando multiconxuntos

Bixección entre 3 subconxuntos dun conxunto de 7 (esquerda)
e 3 multiconxuntos con elementos dun conxunto de 5 (dereita)
Isto ilustra que $(\genfrac{}{}{0ex}{}{7}{3})=\left((\genfrac{}{}{0ex}{}{5}{3})\right).$

Modelo:Ver tamén O número de multiconxuntos de cardinalidade Modelo:Mvar, con elementos tomados dun conxunto finito de cardinalidade Modelo:Mvar, ás veces chámase coeficiente multiconxunto ou número multiconxunto. Este número é escrito por algúns autores como $\left((\genfrac{}{}{0ex}{}{n}{k})\right)$, unha notación que se quere parecer á dos coeficientes binomiais; utilízase, por exemplo, en (Stanley, 1997), e podería pronunciarse "Modelo:Mvar sobre múltiple Modelo:Mvar" para asemellarse a "Modelo:Mvar sobre Modelo:Mvar" para $(\genfrac{}{}{0ex}{}{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((\genfrac{}{}{0ex}{}{n}{k})\right)=(\genfrac{}{}{0ex}{}{n+k-1}{k})=\frac{(n+k-1)!}{k!(n-1)!}=\frac{n(n+1)(n+2)\cdots (n+k-1)}{k!},$

onde a segunda expresión é un coeficiente binomial;Modelo:Efn 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 Modelo:Mvar dun conxunto de cardinalidade Modelo:Math.

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

$\left((\genfrac{}{}{0ex}{}{n}{k})\right)=\frac{n^{\bar{k}}}{k!},$

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

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_}{k}}}{k!}.$

Exemplos

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

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 Modelo:Math temos Modelo:Math, Modelo:Math, Modelo:Math, Modelo:Math 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 Modelo:Math (6 as, 2 bes, 3 ces, 7 des) nesta forma (notación bóla trazo):

Modelo:Nowrap

Este é un multiconxunto de Modelo:Math elementos feito de elementos de 4 conxuntos Modelo:Math. O número de caracteres que inclúe tanto puntos como liñas verticais usado nesta notación é Modelo:Math. 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 Modelo:Math entre os 18 + 4 − 1 caracteres. De forma equivalente, é o número de formas de ordenar os 18 puntos entre os caracteres Modelo:Math. Isto é

$(\genfrac{}{}{0ex}{}{4+18-1}{4-1})=(\genfrac{}{}{0ex}{}{4+18-1}{18})=1330,$

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

$\begin{array}{cc}\left((\genfrac{}{}{0ex}{}{4}{18})\right)& =(\genfrac{}{}{0ex}{}{21}{18})=\frac{21!}{18!3!}=(\genfrac{}{}{0ex}{}{21}{3}),\\ & =\frac{4\mathfrak{\cdot }5\mathfrak{\cdot }6\mathfrak{\cdot }7\mathfrak{\cdot }8\mathfrak{\cdot }9\mathfrak{\cdot }10\mathfrak{\cdot }11\mathfrak{\cdot }12\mathfrak{\cdot }13\mathfrak{\cdot }14\mathfrak{\cdot }15\mathfrak{\cdot }16\mathfrak{\cdot }17\mathfrak{\cdot }18\cdot \mathrm{𝟏}\mathrm{𝟗}\mathbf{\cdot }\mathrm{𝟐}\mathrm{𝟎}\mathbf{\cdot }\mathrm{𝟐}\mathrm{𝟏}}{\mathrm{𝟏}\mathbf{\cdot }\mathrm{𝟐}\mathbf{\cdot }\mathrm{𝟑}\cdot 4\mathfrak{\cdot }5\mathfrak{\cdot }6\mathfrak{\cdot }7\mathfrak{\cdot }8\mathfrak{\cdot }9\mathfrak{\cdot }10\mathfrak{\cdot }11\mathfrak{\cdot }12\mathfrak{\cdot }13\mathfrak{\cdot }14\mathfrak{\cdot }15\mathfrak{\cdot }16\mathfrak{\cdot }17\mathfrak{\cdot }18},\\ & =\frac{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\mathbf{\cdot }\mathrm{𝟏}\mathrm{𝟗}\mathbf{\cdot }\mathrm{𝟐}\mathrm{𝟎}\mathbf{\cdot }\mathrm{𝟐}\mathrm{𝟏}}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\mathbf{\cdot }\mathrm{𝟏}\mathbf{\cdot }\mathrm{𝟐}\mathbf{\cdot }\mathrm{𝟑}},\\ & =\frac{19\cdot 20\cdot 21}{1\cdot 2\cdot 3}.\end{array}$

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

$\left((\genfrac{}{}{0ex}{}{n}{k})\right)=(-1{)}^k(\genfrac{}{}{0ex}{}{-n}{k}).$

e tamén,

$\left((\genfrac{}{}{0ex}{}{n}{k})\right)=\left((\genfrac{}{}{0ex}{}{k+1}{n-1})\right).$

Relación de recorrencia

Unha relación de recorrencia para os coeficientes multiconxunto pódese dar como $$\left((\genfrac{}{}{0ex}{}{n}{k})\right)=\left((\genfrac{}{}{0ex}{}{n}{k-1})\right)+\left((\genfrac{}{}{0ex}{}{n-1}{k})\right)\text{para }n,k>0$$ con $$\left((\genfrac{}{}{0ex}{}{n}{0})\right)=1,n\in \mathbb{N},\text{e}\left((\genfrac{}{}{0ex}{}{0}{k})\right)=0,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 Modelo:Mvar por un número arbitrario Modelo:Mvar (negativo, real ou complexo):

$\left((\genfrac{}{}{0ex}{}{\alpha }{k})\right)=\frac{{\alpha }^{\bar{k}}}{k!}=\frac{\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}\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((\genfrac{}{}{0ex}{}{\alpha }{k})\right)$ coeficientes binomiais negativos:

$(1-X{)}^{-\alpha }=\sum _{k=0}^{\mathrm{\infty }}\left((\genfrac{}{}{0ex}{}{\alpha }{k})\right)X^k.$

Esta fórmula da serie de Taylor é válida para todos os números complexos $\alpha$ e $X$ con Modelo:Math. 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 Modelo:Mvar é un número enteiro non positivo Modelo:Mvar, entón todos os termos con Modelo:Math son cero e a serie infinita convértese nunha suma finita. No entanto, para outros valores de Modelo:Mvar, incluídos os enteiros positivos e os números racionais, a serie é infinita.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro

Modelo:Control de autoridades