multiset

A multiset, also known as a bag, is a generalization of a set that allows repeated elements. Instead of simply containing distinct elements, a multiset assigns a nonnegative multiplicity to each element of a base set.

Formal definition: Let U be a base set. A finite multiset M on U is a function m: U → N0 (the nonnegative integers) with finite support, where m(x) is the multiplicity of x in M. The empty multiset has multiplicities zero for all elements. The cardinality of M is the sum of its multiplicities: |M| = Σx∈U m(x).

Example: The multiset with multiplicities m(a)=3 and m(b)=1 represents the collection {a, a, a, b}.

Notation and equivalence: Two multisets M and N are equal if m(x) = n(x) for all x in U. M ⊆ N if m(x) ≤ n(x) for every x. The representation [a^3 b^1] or [a,a,a,b] is a common compact way to denote a multiset.

Operations: Multiset union and intersection are defined pointwise on multiplicities: (M ∪ N)(x) = max(m(x), n(x)) and (M ∩ N)(x) = min(m(x), n(x)). The multiset sum (often called disjoint union) is (M + N)(x) = m(x) + n(x). Multiset difference is (M \ N)(x) = max(m(x) − n(x), 0).

Algebraic structure: Finite multisets over U form a commutative monoid under addition, with the empty multiset as the identity element. They can also be encoded as finite maps from U to N0 or as arrays or lists with repetition.

Applications: Multisets model counting with repetitions, inventories and word generations with repeated letters, probabilistic models with multiplicities, database queries, and various areas of combinatorics and computer science.