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 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))$.

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