Multiset

In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural 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.
Contents 
Formal definition
Within set theory, a multiset can be formally defined as a pair (A, m) where A is some set and m : A → N is a function from A to the set N of (positive) natural numbers. The set A is called the underlying set of elements. For each a in A the multiplicity of a is the number m(a).
It is common to write the function m as a set of ordered pairs {(a, m(a)) : a ∈ A} — indeed, this is the settheoretic definition of the function m. For example,
 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 {a, b} is defined as {(a, 1), (b, 1)}.
If the set A is finite, the size or length of the multiset (A, m) is the sum of all multiplicities for each element of A:
 <math>\sum_{a\in A}m(a).<math>
One often says that this is the size of A counted with multiplicity.
A submultiset (B, n) of a multiset (A, m) is a subset B ⊆ A and a function n : B → N such that n(a) ≤ m(a).
Examples
One of the most natural and simple examples is the multiset of prime factors of a number n. Here the underlying set of elements is the set of prime divisors of n. For example the 120 has the prime factorization
 <math>120 = 2^3 3^1 5^1<math>
which gives the multiset {2, 2, 2, 3, 5}.
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.
Operations
The usual set operations such as union, intersection and Cartesian product can be easily generalized for multisets.
Suppose (A, m) and (B, n) are multisets
 The union can be defined as (A ∪ B, f) where f(x) = m(x) + n(x).
 The intersection can be defined as (A ∩ B, f) where f(x) = min{m(x), n(x)}.
 The cartesian product can be defined as (A × B, f) where f((x,y)) = m(x)n(y).
Multiset coefficients
The number of submultisets of size k in a set of size n is the multiset coefficient
 <math>\left\langle \begin{matrix}n \\ k \end{matrix}\right\rangle = {n + k  1 \choose n1}={n+k1 \choose k},<math>
where the expressions to the right of "=" are binomial coefficients, i.e., the number of such multisets is the same as the number of subsets of size k in a set of size n + k − 1. Unlike the situation with sets, this cardinality will not be 0 when k > n. One simple way to prove this involves representing multisets in the following way. First, consider the notation for multisets that would represent { a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d } (6 as, 2 bs, 3 cs, 7 ds) in this form:
 <math>\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet <math>
This is a multiset of size 18 made of elements of a set of size 4. The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1. The number of vertical lines is 4 − 1. The number of multisets of size 18 is then the number of ways to arrange the 4 − 1 vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of size 4 − 1 in a set of size 18 + 4 − 1. Equivalently, it is the number of ways to arrange the 18 dots among the 18 + 4 − 1 characters, which is the number of subsets of size 18 of a set of size 18 + 4 − 1. This is
 <math>{18+41 \choose 41}={18+41 \choose 18},<math>
so that is the value of the multiset coefficient
 <math>\left\langle\begin{matrix} 4 \\ 18 \end{matrix}\right\rangle.<math>
One may define a generalized binomial coefficient
 <math>{n \choose k}={n(n1)(n2)\cdots(nk+1) \over k!}<math>
in which n is not required to be a nonnegative integer, but may be negative or a noninteger, or a nonreal complex number. (If k = 0, then the value of this coefficient is 1 because it is the product of no numbers.) Then the number of multisets of size k in a set of size n is
 <math>\left\langle\begin{matrix} n \\ k \end{matrix}\right\rangle=(1)^k{n \choose k}.<math>
This fact led GianCarlo Rota to ask "Why are negative sets multisets?". He considered that question worthy of the attention of philosophers of mathematics.
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.de:Multimenge nl:Multiset pl:Multizbiór sl:večkratna množica