Namespaces
Variants
Actions

Difference between revisions of "Multiset"

From Encyclopedia of Mathematics
Jump to: navigation, search
(better)
m (→‎References: isbn link)
 
Line 10: Line 10:
  
 
====References====
 
====References====
* Gallier, Jean ''Discrete mathematics'' Springer (2011) ISBN 978-1-4419-8046-5 {{ZBL|1227.05002}}
+
* Gallier, Jean ''Discrete mathematics'' Springer (2011) {{ISBN|978-1-4419-8046-5}} {{ZBL|1227.05002}}
* Stanley, Richard P. ''Enumerative combinatorics'' '''I''' (2nd ed.) Cambridge University Press (2012) ISBN 9781107015425 {{ZBL|1247.05003}}
+
* Stanley, Richard P. ''Enumerative combinatorics'' '''I''' (2nd ed.) Cambridge University Press (2012) {{ISBN|9781107015425}} {{ZBL|1247.05003}}
  
 
{{TEX|done}}
 
{{TEX|done}}

Latest revision as of 19:01, 9 November 2023

A generalisation of the concept of set in which elements may appear multiple times: an unordered sequence of elements. The multisets $\{a,a,b\}$, $\{a,b,a\}$ and $\{b,a,a\}$ are the same, but not equal to either $\{a,b,b\}$ or to $\{a,b\}$. The carrier $C(X)$ of a multiset $X$ is the set (in the usual sense) consisting of the elements which occur in $X$ but with multiplicity not counted: so $C(\{a,a,b\}) = C(\{a,b,b\}) = \{a,b\}$. A multiset over a set $C$ is a multiset for which $C$ is a carrier.

The predicate $x \in X$ for $x$ being an element of $X$ is replaced by a multiplicity function $\epsilon_X(x)$ taking values in the natural numbers, generalising the characteristic function of a set, which takes only values $0$ or $1$.

We may extend the usual set theoretic notions: $X$ is a submultiset of $Y$ if $\epsilon_X \le \epsilon_Y$, the intersection of $X$ and $Y$ corresponds to $\min(\epsilon_X, \epsilon_Y)$, the union to $\max(\epsilon_X, \epsilon_Y)$. We may also define multiset addition $X + Y$ by the multiplicity function $\epsilon_X+ \epsilon_Y$.

If $C$ is an ordered finite set $C = \{x_1,\ldots,x_n\}$ then a multiset $X$ with $C$ as carrier may be encoded by the Parikh vector of multiplicities $(\epsilon_X(x_1),\ldots,\epsilon_X(x_n))$.

See also: Tuple, Word.

References

  • Gallier, Jean Discrete mathematics Springer (2011) ISBN 978-1-4419-8046-5 Zbl 1227.05002
  • Stanley, Richard P. Enumerative combinatorics I (2nd ed.) Cambridge University Press (2012) ISBN 9781107015425 Zbl 1247.05003
How to Cite This Entry:
Multiset. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Multiset&oldid=37512