In mathematics, a multiset (or bag) is a generalization of a set. A member of a multiset can have more than one membership, while each member of a set has only one membership. The term "multiset" was coined by Nicolaas Govert de Bruijn in the 1970s.^[1] The use of multisets in mathematics predates the name "multiset" by nearly 90 years; Richard Dedekind used multisets in a paper published in 1888.^[2] Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... A Dutch mathematician, especially noted for the invention of the de Bruijn Sequence. External links About the de Bruijn sequence ... Richard Dedekind Julius Wilhelm Richard Dedekind (October 6, 1831 – February 12, 1916) was a German mathematician who did important work in abstract algebra and the foundations of the real numbers. ...

The total number of elements in a multiset, including repeated memberships, is the cardinality of the multiset, and the number of times an element belongs to the multiset is the multiplicity of that member. i.e. in the multiset {a, a, b, b, b, c} the multiplicities of the members a, b, and c are respectively 2, 3, and 1, and the cardinality of the multiset is 6. In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... In mathematics, the multiplicity of a member of a multiset is how many memberships in the multiset it has. ...

In multisets, as in sets, the order of elements does not matter; in contrast to tuples, where order is important. The following list displays the difference between the three concepts, note how a multiset can also be considered an unordered tuple: In mathematics, a tuple is a finite sequence (also known as an ordered list) of objects, each of a specified type. ...

• The tuples (a, b) and (b, a) are not equal, because in tuples order is important; and the tuples (a, a) and (a) are not equal either, because in tuples and multisets multiplicity is considered, affecting cardinality.

• The multisets {a, b} and {b, a} are equal, because in multisets order is unimportant; but the multisets {a, a} and {a} are not equal, as they have different cardinalities.

• The sets {a, b} and {b, a} are equal, like the multisets {a, b} and {b, a}; but the sets {a, a} and {a} are equal, unlike the multisets {a, a} and {a}, this is because in sets, the concept of multiplicity does not exist, or in other words all objects, no matter how many times they belong to the set, still count as one.

In mathematics, a tuple is a finite sequence (also known as an ordered list) of objects, each of a specified type. ... In mathematics, the multiplicity of a member of a multiset is how many memberships in the multiset it has. ...

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 = {1, 2, 3, ...} of (positive) natural numbers. The set A is called the underlying set of elements. For each a in A the multiplicity (that is, number of occurrences) of a is the number m(a). Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... A negative number is a number that is less than zero, such as −3. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...

The concept of a multiset is a generalization of the concept of a set. A multiset is a set if the multiplicity of every element is one. For the term in the context of mathematical logic, see Generalization (logic). ...

The function m is a set of ordered pairs { (a, m(a)) : a in A }. For example, the multiset written as { a, a, b } is defined as { (a, 2), (b, 1) }, and the multiset { a, b } is defined as { (a, 1), (b, 1) }. An ordered pair is a collection of two objects such that one can be distinguished as the first element and the other as the second element. ...

An indexed family, ( a_i ), where i is in some index-set, defines the multiset { a_i } , provided no element occurs more than a finite number of times in the family. Even in an infinite multiset, the multiplicities must be finite numbers. In mathematics, an index set is another name for a function domain. ...

Multiplicity function

The set indicator function of a subset of a set is the function In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...

defined by

The set indicator function of the intersection of sets is the minimum function of the indicator functions In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ...

The set indicator function of the union of sets is the maximum function of the indicator functions In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...

The set indicator function of a subset is smaller than or equal to that of the superset “Superset” redirects here. ...

The set indicator function of a cartesian product is the product of the indicator functions of the cartesian factors In mathematics, the Cartesian product is a direct product of sets. ...

The cardinality of a (finite) set is the sum of the indicator function values In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ...

Now generalize the concept of set indicator function by releasing the constraint that the values are 0 and 1 only and allow the values 2, 3, 4 and so on. The resulting function is called a multiplicity function and such a function defines a multiset. The concepts of intersection, union, subset, cartesian product and cardinality of multisets are defined by the above formulas.-1...

The multiplicity function of a join, sometimes called the sum, is the sum of the multiplicity functions

.

A small finite multiset, A, is represented by a list where each element, x, occurs as many times as the multiplicity, 1_A(x), indicates.

Examples

One of the simplest and most natural 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 factorization In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... 120 (one hundred twenty in American English; one hundred and twenty in British English) is the natural number following 119 and preceding 121. ... In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ...

120 = 2³3¹5¹

which gives the multiset {2, 2, 2, 3, 5}.

A related example 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. In mathematics, a quadratic equation is a polynomial equation of the second degree. ...

Multiset coefficients

The number of multisets of cardinality k, with elements taken from a set of cardinality n, is the multiset coefficient

where the expressions to the right of "=" are binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality k in a set of cardinality n + k − 1. In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ...

There are for example 4 multisets of cardinality 3 with elements taken from the set {1,2} of cardinality 2, namely : {1,1,1}, {1,1,2}, {1,2,2}, {2,2,2}. And there are also 4 subsets of cardinality 3 in the set {1,2,3,4} of cardinality 4, namely : {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

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 cardinality 18 made of elements of a set of cardinality 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 cardinality 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 cardinality 4 − 1 in a set of cardinality 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 cardinality 18 of a set of cardinality 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 empty product.) Then the number of multisets of cardinality k in a set of cardinality n is In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ...

This fact led Gian-Carlo Rota to ask "Why are negative sets multisets?".^{[citation needed]} He considered that question worthy of the attention of philosophers of mathematics. Gian-Carlo Rota (April 27, 1932 – April 18, 1999, known as Juan Carlos Rota to Spanish speakers) was an Italian-born American mathematician and philosopher. ... // Philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. ...

Polynomial notation

The set {x} may be represented by the monomial x. The set of subsets, { {}, {x} } , is represented by the binomial 1 + x. In mathematics, a monomial (or mononomial) is a particular kind of polynomial, having just one term. ... In elementary algebra, a binomial is a polynomial with two terms: the sum of two monomials. ...

The set {x,y} may be represented by the monomial x·y. The set of subsets, { {}, {x}, {y}, {x,y} } , is represented by the polynomial In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...

(1 + x)·(1 + y) = 1 + x + y + x·y.

The multiset {x,x} may be represented by the monomial x·x = x². The multiset of submultisets, { {}, {x}, {x}, {x,x} } , is represented by the polynomial

(1 + x)² = 1 + x + x + x·x = 1 + 2·x + x².

The multiset of submultisets of the multiset xⁿ is

That is why the binomial coefficient counts the number of k-combinations of an n-set. In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ... For other uses, see Combination (disambiguation). ...

The multiset x^K·y^N−K , containing N elements, K of which are hits, is called a statistical population, and a submultiset is called a statistical sample. The set of samples is In statistics, a statistical population is a set of entities concerning which statistical inferences are to be drawn, often based on a random sample taken from the population. ... A sample is that part of a population which is actually observed. ...

(1 + x)^K·(1 + y)^N−K

which by the binomial theorem equals In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. ...

So the number of n-samples with k hits is

See hypergeometric distribution and inferential statistics for further on the distribution of hits. // In probability theory and statistics, the hypergeometric distribution is a discrete probability distribution that describes the number of successes in a sequence of n draws from a finite population without replacement. ... It has been suggested that this article or section be merged with statistical inference. ...

The infinite set of finite multisets of elements taken from the set {x}:

{ {}, {x}, {x,x}, {x,x,x}, ... }

may be represented by the formal power series In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is...

S = 1 + x + x² + x³ + ... = 1 + xS .

The formal solution,

S = (1 − x)⁻¹,

makes sense as a set of multisets, but the intermediate result, 1−x, does not make sense as a set of multisets.

The infinite set of finite multisets of elements taken from the set x·y is

(1 − x)⁻¹·(1 − y)⁻¹ = 1 + (x + y) + (x² + x·y + y²) + ...

The special case y=x : The infinite multiset of finite multisets of elements taken from the multiset x² is

(1 − x)⁻² =  1 + 2·x + 3·x² + ...

The general case: The infinite multiset of finite multisets of elements taken from the multiset xⁿ is

 .

This explains why "multisets are negative sets". The negative binomial coefficients count the number of k-multisets of elements taken from an n-set. In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ...

Cumulant generating function

A non-negative integer, n, can be represented by the monomial xⁿ . Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...

So a finite multiset of non-negative integers, say {2, 2, 2, 3, 5}, can be represented by a polynomial f(x), say f(x) = 3·x² + x³ + x⁵ .

It is convenient to consider the cumulant generating function g(t) = log(f(e^t)), say g(t) = log(3·e^2·t + e^3·t  + e^5·t) .

The number of elements in the multiset is e^g(0) = f(1), say 3 + 1 + 1 = 5.

The derivative of the g function is g '(t) = f(e^t)⁻¹·f '(e^t)·e^t, say g '(t) = (3·e^2·t + e^3·t  + e^5·t)⁻¹ ·(6·e^2·t + 3·e^3·t  + 5·e^5·t) . For a non-technical overview of the subject, see Calculus. ...

The mean value of the multiset is μ = g '(0) = f(1)⁻¹·f '(1), say μ = (3+1+1)⁻¹·(6+3+5) = 2.8 . In mathematics, there are numerous methods for calculating the average or central tendency of a list of n numbers. ...

The second derivative of the g function is g ' '(t) .

The variance of the multiset is σ² = g ' '(0) . In probability theory and statistics, the variance of a random variable (or somewhat more precisely, of a probability distribution) is a measure of its statistical dispersion, indicating how its possible values are spread around the expected value. ...

The numbers ( μ, σ², ··· )  = ( g '(0), g ' '(0), ··· ) are called cumulants, and that's why g is called the cumulant generating function. // Cumulants of probability distributions In probability theory and statistics, the cumulants κn of the probability distribution of a random variable X are given by In other words, κn/n! is the nth coefficient in the power series representation of the logarithm of the moment-generating function. ...

The infinite set of non-negative integers {0, 1, 2, ···} is represented by the formal power series 1 + x + x² + ··· = (1 − x)⁻¹. The mean value and standard deviation are undefined. Nevertheless it has a cumulant-generating function, g(t) = −log(1−e^t). The derivative of this cumulant-generating function is g '(t) = (e^−t−1)⁻¹. In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is...

A finite multiset of real numbers , A = { A_i }, is represented by the cumulant generating function

This representation is unique: different multisets have different cumulant generating functions. See partition function (statistical mechanics) for the case where the numbers in question are the energy levels of a physical system. In statistical mechanics, the partition function Z is an important quantity that encodes the statistical properties of a system in thermodynamic equilibrium. ...

The cumulant-generating function of a multiset of n real numbers having mean μ and standard deviation σ is: g(t) = log(n) + μ·t  + 2⁻¹·(σ·t)² + ··· , and the derivative is simply: g '(t) = μ + σ²·t + ···

The cumulant-generating function of set, {k}, consisting of a single real number, k, is g(t) = k·t , and the derivative is the number itself: g '(t) = k . So the concept of the derivative of the cumulant generating function of a multiset of real numbers is a generalization of the concept of a real number. For the term in the context of mathematical logic, see Generalization (logic). ...

The cumulant-generating function of a constant multiset, {k, k, k, k, ··· , k} of n elements all equal to the same real number k, is g(t) = log(n)+k·t , and the derivative is the number itself: g '(t) = k , irrespective of n.

The cumulant-generating function of the multiset of sums of elements of two multisets of numbers is the sum of the two cumulant-generating functions:

There is unfortunately no general formula for computing the cumulant generating function of a product

but the special case of a constant times a multiset of numbers is:

The multiset 2·A = {2·A_i} is not the same multiset as 2×A =A+A = {A_i+A_j}. For example, 2·{+1,−1} = {+2,−2} while 2×{+1,−1} = {+1,−1} + {+1,−1} = {+1+1,+1−1,−1+1,−1−1} = {+2,0,0,−2}.

The standard normal distribution is like a limit of big multisets of numbers. Probability density function of Gaussian distribution (bell curve). ...

This limit does not make sense as a multiset of numbers, but the derivative of the cumulant generating functions of the multisets in question makes sense, and the limit is well defined.

The constant term k²·log(2) vanishes by differentiation. The terms ··· vanish in the limit. So for the standard normal distribution, having mean 0 and standard deviation 1, the derivative of the cumulant generating function is simply g '(t) = t . For the normal distribution having mean μ and standard deviation σ, the derivative of the cumulant generating function is g '(t) = μ+σ²·t . Probability density function of Gaussian distribution (bell curve). ... In probability and statistics, the standard deviation of a probability distribution, random variable, or population or multiset of values is a measure of the spread of its values. ... The normal distribution, also called the Gaussian distribution, is an important family of continuous probability distributions, applicable in many fields. ...

See also random variable. In probability theory, a random variable is a quantity whose values are random and to which a probability distribution is assigned. ...

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. Such monoids are also known as (finite) formal sums of elements of X with natural coefficents. Compare free abelian group. In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. ... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ... In abstract algebra, a free abelian group is an abelian group that has a basis in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients. ...

References

1. ^ Knuth, Donald E. (1998). The Art of Computer Programming - Vol. 2: Seminumerical Algorithms, 3rd edition, Addison Wesley, 694. ISBN 0201896842.  Knuth also lists other names that were proposed for multisets, such as list, bunch, bag, heap, sample, weighted set, collection, suite.
2. ^ Syropoulos, Apostolos (2001), p. 347.

• Blizard, Wayne D. (1989). Multiset theory. Notre Dame Journal of Formal Logic 30.1 (Winter 1989) pp. 36-66.
• Bogart, Kenneth P. (2000). Introductory combinatorics, 3rd. ed. Harcourt: San Diego.
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1..
• Syropoulos, Apostolos (2001). Mathematics of Multisets. In C. S. Calude et. al. (Eds.) (2001), Multiset processing: Mathematical, computer science, and molecular computing points of view, LNCS 2235, Springer-Verlag: Berlin, Heidelberg. pp. 347-358.