Multiset Guide, Meaning , Facts, Information and Description

In mathematics, a multiset (also called 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 -- "multiset coefficients" 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 union, 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 -- "multiset coefficients"

The number of submultisets of size k in a set of size n is the multiset coefficient

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:

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

so that is the value of the multiset coefficient

One may define a generalized binomial coefficient

in which n is not required to be a nonnegative integer, but may be negative or a non-integer, or a non-real 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

This fact led Gian-Carlo 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.

This is an Article on Multiset. Page Contains Information, Facts Details or Explanation Guide About Multiset

	Web www.E-paranoids.com