View source for Multiset

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 simple set 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 number]]s, generalising the [[characteristic function of a set]], which on a simple set 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 simple 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))$.

====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}}

{{TEX|done}}