Multiset
A multiset (sometimes called a bag) is a concept from mathematics. In many ways, multisets are like sets. Certain items are either elements of that multiset, or they are not. However, multisets are different from sets: The same type of item can be in the multiset more than once. For this reason, mathematicians have defined a relation (function) that tells, how many copies of a certain type of item there are in a certain multiset. They call this multiplicity. For example, in the multiset { a, a, b, b, b, c }, the multiplicities of the members a, b, and c are 2, 3, and 1, respectively. From a set of n elements, the number of r-element multisets is written as [math]\displaystyle{ \textstyle \left(\!\binom{n}{r}\!\right) }[/math]. This is sometimes called the multiset coefficient.[1][2][3]
A multiset is illustrated by means of a histogram.
A multiset can also be considered an unordered tuple:
- The tuples (a,b) and (b,a) are not equal, and the tuples (a,a) and (a) are not equal either.
- The multisets {a,b} and {b,a} are equal, but the multisets {a,a} and {a} are not equal.
- The sets {a,b} and {b,a} are equal, and the sets {a,a} and {a} are equal too.
Examples
One of the simplest 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 number 120 has the prime factorisation
- [math]\displaystyle{ 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. A quadratic equation, for example, has two solutions. However, 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.
Multiset Media
Bijection between 3-subsets of a 7-set (left)and 3-multisets with elements from a 5-set (right)So this illustrates that {7 \choose 3} = \left(\!\!{5 \choose 3}\!\!\right).
Related pages
References
CItations
- ↑ "List of Probability and Statistics Symbols". Math Vault. 2020-04-26. Retrieved 2020-09-23.
- ↑ "3.7: Counting Multisets". Mathematics LibreTexts. 2020-01-19. Retrieved 2020-09-23.
- ↑ "Multiset | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2020-09-23.
Sources
- Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1..