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.
Formally, a multiset $M$ over a universe (base set) $U$ is defined via its “multiplicity function”:

$$M:U\to {\mathbb{N}}_0$$

Key properties:

• Order is irrelevant (like regular sets)
• Elements can appear multiple times
• The multiplicity of each element is significant
• Elements can have zero occurrences

Notation: If $M$ is a multiset, we can denote it as:

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

The cardinality of a multiset includes all instances: $|M|={\sum }_{x\in M}\text{multiplicity}(x)$

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!}$$