Main Index
Computer Science
Data Structures
Subject Index
comment on the page
A multiset 1 is a generalization of the concept of a set. Its main idea is to allow a member of a multiset to have a multiple membership, while in a set each member can only have one membership.
Starting with classical set theory
, a multiset is formally defined as a pair
where
is a set and
is a function from
to the set
of positive integers. The set
is called the underlying set of elements, and the value
of function
at
gives the multiplicity (that is, number of occurrences) of
in
.
A multiset becomes a set if the multiplicity of every element is equal to one.
The cardinality of a finite set is defined as a number of its elements. If we extend the concept of set indicator function
by releasing the constraint that the values are 0 and 1 only and define it as the multiplicity of the corresponding element then the cardinality of multiset
is again given by formula
The concepts of intersection, union, subset, and Cartesian product of multisets are defined by formulas
If then
for each
.
If are two multisets of a multiset
, then
The number of multisets of cardinality , with elements taken from a set of cardinality
is given by the binomial coefficients
. This common value is often called multiset coefficient and denoted
.
To see this represent the multiset, say in the form
This is a multiset of cardinality made of elements of a set of cardinality
. The number of all signs including both dots and vertical lines is
,
dots and
vertical lines.
Thus the number of multisets of cardinality made of elements of a set of cardinality
equals the number of ways to arrange the
vertical lines among the
symbols. Generally, it is the number of ways to arrange the
dots among the
characters. This is given by the binomial coefficient
. This clearly equals the number of subsets of cardinality
of a set of cardinality
.
Example: A free commutative monoid
with a set of generators
can be viewed as the set of finite multisets with elements drawn from
, equipped with the obvious addition operation. Another interpretation of such monoids is as finite formal sums of elements of
with positive integral coefficients.
1 | The term multiset goes back to Nicolaas Govert de Bruijn in the 1970's. The word multiset is often shortened to mset. According to some sources it is an abbreviation of multiple-membership set. Also used names for this concept are bag, bunch, weighted set, occurrence set, heap, sample, or fireset (from finitely repeated element set). |
[1] | Blizard, W. D. (1988). Multiset theory. Notre Dame J. Formal Logic , 30(Number 1), 36-66. |
Cite this web-page as:
Štefan Porubský: Multiset.