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 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[edit]

* 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