Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Multiset
Main Page | See live article | Alphabetical index

Multiset

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.

Table of contents
1 Formal definition
2 Operations
3 Counting
4 Free commutative monoids

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

Operations

The usual set operations such as set union, set intersection and cartesian product can be easily generalized for multisets.

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.