# 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 |

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

- 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

*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.