This article needs more work.
Please help by expanding it!
A multiset (some authors use bag or mset) is a generalization of the notion of set. In a multiset, the members (elements) are allowed to appear more than once (i.e. the [finite] multiplicity is any positive integer), whereas in a set the members can appear only once. (Both are unordered collections.) Some authors allow infinite multiplicities.[1]
For example, the multiset
{a, a, a, a, a, b, b, b, c, d, d} |
, which may be written in compact form as the
map , where for each distinct member we specify the
multiplicity. (An alternative notation is
.)
A common application for the multiset is the
prime factors dividing a number. For example, the multiset of prime factors of
is
{2, 2, 2, 2, 2, 3, 3, 3, 5, 11, 11} |
, which may be written in compact form as the map
{2: 5, 3: 3, 5: 1, 11: 2} |
, where for each distinct member we specify the multiplicity. (An alternative notation is
.)
Support set
The root set (or support set) of a multiset is the set of its distinct elements. The dimension of a multiset is the cardinality of the support set.[2]
Multiplicity
An element
of a multiset
has multiplicity
if and only if
where
means "is contained at least
times," where
is a nonnegative integer. (Trivially,
is always true.)
[2]
Multiplicity function
The multiplicity of an element
, denoted
, is a
cardinal number; most authors require a positive integer, though some are more general.
[1] The multiplicity is positive if
is contained at least once in the multiset
, and zero otherwise. The
multiplicity function of a multiset is a generalization of the
characteristic function of a set. The
height of a multiset is the greatest
multiplicity.
Cardinality
The cardinality of a multiset is a cardinal number. The
cardinality of a multiset
is the number of elements (with multiplicity) that it contains, and is thus the sum of the multiplicities of its members, i.e.
where
is the multiplicity of
.
Submultisets
A
submultiset is a generalization of the notion of
subset. To obtain a submultiset of a multiset
, for each member
we may choose a multiplicity in the range
.
Powerset of a multiset
The
powerset of a multiset is defined as the set of all submultisets of
.
For example, the set (with cardinality
) of submultisets of
are (in
lexicographic order)
{{ }, {a ^1}, {a ^2}, {a ^2, b ^1}, {a ^2, b ^1, c ^1}, {a ^2, c ^1}, {a ^1, b ^1}, {a ^1, b ^1, c ^1}, {a ^1, c ^1}, {b ^1}, {b ^1, c ^1}, {c ^1}}. |
The cardinality of the powerset of a multiset
is
-
where
is the multiplicity of
.
Multiset partitions
(...)
Multiset operations
Multiset sum
The
multiset sum of two multisets
and
is defined as the multiset for which each member
have the sum of the multiplicities it has in both multisets
[3]
-
Generalized set operations
The following multiset operations generalize set operations.
Multiset containment is a Boolean operation, denoted
, which evaluates to true if and only if
.
Multiset inclusion is a Boolean operation, denoted
, which evaluates to true if and only if
.
[4]
Strict multiset inclusion is a Boolean operation, denoted
, which evaluates to true if and only if
.
[5]
The
multiset union of two multisets
and
is defined as the multiset for which each member
have the maximal multiplicity it has in either multisets
[6]
-
The
multiset intersection of two multisets
and
is defined as the multiset for which each member
have the minimal multiplicity it has in either multisets. Example:
.
The
multiset difference of two multisets
and
is defined as the multiset for which each member
have multiplicity. Example:
.
The
multiset symmetric difference M Δ N := (M \ N) ⋃ (N \ M) = (M ⋃ N) \ (M ⋂ N) |
of two multisets
and
is defined as the multiset for which each member
have multiplicity. Example:
max(M / gcd(M, N), N / gcd(M, N)) = lcm(M, N) / gcd(M, N) |
.
Generalizations of multisets
Signed multisets
A signed multiset is a generalization of the notion of multiset. In a signed multiset, the members (elements) may have any integer as signed multiplicity, whereas in a multiset the members may only have nonnegative integers as multiplicity.
An example is the signed multiset of prime factors of
rational numbers (in
reduced form), e.g. for
we get
{2: 5, 3: 3, 5: 1, 7: −3, 11: 2, 29: −1} |
, where for each distinct member we specify the signed multiplicity. (An alternative notation is
{2^5, 3^3, 5^1, 7^(−3), 11^2, 29^(−1)} |
.)
Weighted sets
Weighted sets might be a further generalization of multisets where the multiplicity would be any real number.
Equivalence with maps
As stated in the introduction, a multiset can be seen a map from some domain
(containing the support) to the nonnegative integers
, this map being the same as the multiplicity function. The above generalizations of
signed or
weighted multisets then simply consist in allowing signed integers (
) or real numbers (
) as values of the map which defines the multiset.
See also
- Sequence (ordered collection of elements, not necessary distinct)
Notes
External links