multiset

Multiset

A multiset is a modification of the concept of a set that allows for multiple instances of the same element. Unlike regular sets where each element appears exactly once, multisets track the multiplicity (number of occurrences) of each element.

A multiset $\mathcal{M}$ on a set $U$ is specified by its multiplicity function:

$$m:U\to {\mathbb{N}}_{0}u\mapsto m(u)$$

We get the indexed family $(m_u{)}_{u\in U}$, where $m_u=m(u)$ is the number of occurrences of $u$.

Key properties:

• Order is irrelevant (like regular sets)
• Elements can appear multiple times
• Elements can have zero occurrences
• The cardinality: is $|\mathcal{M}|={\sum }_{u\in U}m(u)$

Notation: If $\mathcal{M}$ is a multiset, we can denote it as:

• $\mathcal{M}=\{1,2,2,3,3,3\}$ (listing all occurrences)
• $\mathcal{M}=\{1^1,2^2,3^3\}$ (using superscripts for multiplicity)

Examples

The string “hello” as a multiset: $\{h^1,e^1,l^2,o^1\}$
Chemical formula H₂O as a multiset: $\{H^2,O^1\}$

permutation of a multiset

Permuting a multiset is like permuting a string of characters:
There are $n!$ ways to permute a set with $n$ elements, but for a multiset, we need divide by the amount of permutations of equal elements whose order doesn’t matter (eliminating all those sub-trees). E.g. $(a,a,b)$ has $3!$ permutations, but only $\frac{3!}{2!}$ unique ones.
Let $M$ be a multiset with elements $\{m_1^{k_1},m_2^{k_2},\dots ,m_n^{k_n}\}$ where $m_i$ is an element and $k_i$ is the multiplicity of $m_i$.
The number of unique permutations of $M$ is:

$$\frac{(|M|)!}{k_1!\cdot k_2!\cdot \cdots \cdot k_n!}$$