|
In mathematics, a multiset (also a bag) differs
from a set in that each member has a multiplicity, which is a cardinal number indicating (loosely speaking) how many times it is a
member, or perhaps how many memberships it has in the multiset. For example, in the multiset { a, a,
b, b, b, c }, the multiplicities of the members a, b, and c are
respectively 2, 3, and 1.
One of the most natural and simple examples is the multiset of prime
factors of a number. Another is the multiset of solutions of an algebraic equation. Everyone learns in secondary school that a
quadratic equation has two solutions, but in some cases they
are both the same number. Thus the multiset of solutions of the equation could be { 3, 5 }, or it could be { 4, 4 }. In the
latter case it has a solution of multiplicity 2.
Formal definition
Formally multisets can be defined, within set theory, as partial functions that map elements to positive natural numbers. So in terms of sets
- the multiset written as {a, b, b} is defined as {(a, 1), (b, 2)},
- likewise {a, a, b} is defined as {(a, 2), (b, 1)}, and
- the multiset meaning of {a, b} is defined as {(a, 1), (b, 1)}.
Operations
The usual set operations such as set union, set intersection and cartesian
product can be easily generalized for multisets.
- the union of A and B can be defined as the function F on the union of the domain of A and
B such that F(x) = A(x) + B(x)
- the intersection of A and B can be defined as the function F on the intersection of the domain of
A and B such that F(x) = MIN(A(x), B(x))
- the cartesian product of A and B can be defined as the function F on the cartesian product of the
domains of A and B such that F((x,y)) =
A(x).B(y)
Counting
The number of submultisets of size k in a set of size n is the binomial coefficient
-
i.e., it is the same as the number of subsets of size k in a set of size n + k − 1. (Note
that, unlike the situation with sets, this cardinality will not be 0 when k > n.)
Free commutative monoids
There is a connection with the free object concept: the free commutative monoid on a set X can
be taken to be the set of finite multisets with elements drawn from X, with the obvious addition operation.
|