View source for Multiset

{{Short description|Mathematical set with repetitions allowed}}
{{About|the mathematical concept|the computer science data structure|Multiset (abstract data type)}}

In [[mathematics]], a '''multiset''' (or '''bag''', or '''mset''') is a modification of the concept of a [[set (mathematics)|set]] that, unlike a set,<ref name="Cantor">{{cite journal |quote=By a set (Menge) we are to understand any collection into a whole (Zusammenfassung zu einem Gansen) M of definite and '''separate''' objects m  (p.85)|last1=Cantor |first1=Georg |author1link = Georg Cantor|last2=Jourdain |first2=((Philip E.B. (Translator))) |title=beiträge zur begründung der transfiniten Mengenlehre |journal=[[Mathematische Annalen]] |date=1895 |volume=xlvi;xlix |pages=481–512;207–246 |trans-title=contributions to the founding of the theory of transfinite numbers |publisher=New York Dover Publications (1954 English translation) |language=German |url=http://brinkmann-du.de/mathe/fos/fos01_03.htm |archive-url=https://web.archive.org/web/20110610133240/http://brinkmann-du.de/mathe/fos/fos01_03.htm |archive-date=2011-06-10 }}</ref> allows for multiple instances for each of its [[element (mathematics)|element]]s. The number of instances given for each element is called the [[Multiplicity (mathematics)|''multiplicity'']] of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements {{mvar|a}} and {{mvar|b}}, but vary in the multiplicities of their elements:
* The set {{math|{{mset|''a'', ''b''}}}} contains only elements {{mvar|a}} and {{mvar|b}}, each having multiplicity 1 when {{math|{{mset|''a'', ''b''}}}} is seen as a multiset.
* In the multiset {{math|{{mset|''a'', ''a'', ''b''}}}}, the element {{mvar|a}} has multiplicity 2, and {{mvar|b}} has multiplicity 1.
* In the multiset {{math|{{mset|''a'', ''a'', ''a'', ''b'', ''b'', ''b''}}}}, {{mvar|a}} and {{mvar|b}} both have multiplicity 3.

These objects are all different when viewed as  multisets, although they are the same set, since they all consist of the same elements. As with sets, and in contrast to ''[[tuple]]s'', the order in which elements are listed does not matter in discriminating multisets, so {{math|{{mset|''a'', ''a'', ''b''}}}} and {{math|{{mset|''a'', ''b'', ''a''}}}} denote the same multiset.  To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset {{math|{{mset|''a'', ''a'', ''b''}}}} can be denoted by {{math|[''a'', ''a'', ''b'']}}.<ref>{{cite book|title=Discrete mathematics|url=https://archive.org/details/discretemathemat00hein_966|url-access=limited|first=James L.|last=Hein|publisher=Jones & Bartlett Publishers|year=2003|isbn=0-7637-2210-3|pages=[https://archive.org/details/discretemathemat00hein_966/page/n43 29]–30}}</ref>

The [[cardinality]] or "size" of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset {{math|{{mset|''a'', ''a'', ''b'', ''b'', ''b'', ''c''}}}} the multiplicities of the members {{mvar|a}}, {{mvar|b}}, and {{mvar|c}} are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.

[[Nicolaas Govert de Bruijn]] coined the word ''multiset'' in the 1970s, according to [[Donald Knuth]].<ref name="Knuth1998">{{cite book
  | last = Knuth
  | first = Donald E.
  | author-link =Donald Knuth
  | series= [[The Art of Computer Programming]]
  | volume= 2 | title = Seminumerical Algorithms
  | publisher = [[Addison Wesley]]
  | date=1998 | edition = 3rd
  | isbn =0-201-89684-2 }}</ref>{{rp|p=694}} However, the concept of multisets predates the coinage of the word ''multiset'' by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematician [[Bhāskara II|Bhāskarāchārya]], who described [[Permutation#Permutations of multisets|permutations of multisets]] around 1150. Other names have been proposed or used for this concept, including ''list'', ''bunch'', ''bag'', ''heap'', ''sample'', ''weighted set'', ''collection'', and ''suite''.<ref name="Knuth1998"/>{{rp|p=694}}

==History==
Wayne Blizard traced multisets back to the very origin of numbers, arguing that "in ancient times, the number ''n'' was often represented by a collection of ''n'' strokes, [[tally mark]]s, or units."<ref name="Blizard1989">{{cite journal|last=Blizard|first=Wayne D|year=1989|title=Multiset theory|journal=[[Notre Dame Journal of Formal Logic]]|volume=30|issue=1|pages=36–66|url=http://projecteuclid.org/download/pdf_1/euclid.ndjfl/1093634995|doi=10.1305/ndjfl/1093634995|doi-access=free}}</ref> These and similar collections of objects can be regarded as multisets, because strokes, tally marks, or units are considered indistinguishable. This shows that people implicitly used multisets even before mathematics emerged.

Practical needs for this structure have caused multisets to be rediscovered several times, appearing in literature under different names.<ref name="Blizard1991">{{cite journal|last=Blizard|first=Wayne D.|year=1991|title=The Development of Multiset Theory|journal=Modern Logic|volume=1|issue=4|pages=319–352|url=http://projecteuclid.org/download/pdf_1/euclid.rml/1204834739}}</ref>{{rp|p=323}} For instance, they were important in early [[AI]] languages, such as QA4, where they were referred to as ''bags,'' a term attributed to [[L. Peter Deutsch|Peter Deutsch]].<ref name="Rulifson1972">{{cite tech report|last1=Rulifson|first1=J. F.|last2=Derkson|first2=J. A.|last3=Waldinger|first3=R. J.|date=November 1972|institution=SRI International|title=QA4: A Procedural Calculus for Intuitive Reasoning|number=73}}</ref> A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set).<ref name="Blizard1991" />{{rp|p=320}}<ref name="Singh2007">{{cite journal | last1=Singh|first1=D.| last2=Ibrahim|first2=A. M.| last3=Yohanna|first3=T.|last4=Singh|first4=J. N.|year=2007|title=An overview of the applications of multisets | journal=Novi Sad Journal of Mathematics|volume=37|issue=2|pages=73–92}}</ref>

Although multisets were used implicitly from ancient times, their explicit exploration happened much later. The first known study of multisets is attributed to the Indian mathematician [[Bhāskara II|Bhāskarāchārya]] circa 1150, who described permutations of multisets.<ref name="Knuth1998"/>{{rp|p=694}} The work of [[Marius Nizolius]] (1498–1576) contains another early reference to the concept of multisets.<ref name="Angelelli1965">{{cite journal| last=Angelelli|first=I.| year=1965| title=Leibniz's misunderstanding of Nizolius' notion of 'multitudo'|journal=Notre Dame Journal of Formal Logic| issue=6| pages=319–322}}</ref> [[Athanasius Kircher]] found the number of multiset permutations when one element can be repeated.<ref>{{cite book|last=Kircher|first=Athanasius|author-link=Athanasius Kircher|year=1650|title=Musurgia Universalis| url=https://archive.org/details/bub_gb_97xCAAAAcAAJ|publisher=Corbelletti|location=Rome}}</ref> [[Jean Prestet]] published a general rule for multiset permutations in 1675.<ref>{{cite book|last=Prestet|first=Jean|year=1675|title=Elemens des Mathematiques|publisher=André Pralard|location=Paris}}</ref> [[John Wallis]] explained this rule in more detail in 1685.<ref>{{cite book|last=Wallis|first=John|author-link=John Wallis|year=1685|title=A treatise of algebra|publisher=John Playford|location=London}}</ref>

Multisets appeared explicitly in the work of [[Richard Dedekind]].<ref>{{cite book|last=Dedekind|first=Richard|author-link=Richard Dedekind|year=1888|title=Was sind und was sollen die Zahlen?|publisher=Vieweg|location=Braunschweig | page = 114}}</ref><ref name=syropoulos>{{cite conference
 | last = Syropoulos | first = Apostolos
 | editor1-last = Calude | editor1-first = Cristian
 | editor2-last = Paun | editor2-first = Gheorghe
 | editor3-last = Rozenberg | editor3-first = Grzegorz
 | editor4-last = Salomaa | editor4-first = Arto
 | contribution = Mathematics of multisets
 | doi = 10.1007/3-540-45523-X_17
 | pages = 347–358
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View [Workshop on Multiset Processing, WMP 2000, Curtea de Arges, Romania, August 21–25, 2000]
 | volume = 2235
 | year = 2000| isbn = 978-3-540-43063-6
 }}</ref>

Other mathematicians formalized multisets and began to study them as precise mathematical structures in the 20th century.  For example, [[Hassler Whitney]] (1933) described ''generalized sets'' ("sets" whose [[characteristic function]]s may take any [[integer]]  value: positive, negative or zero).<ref name="Blizard1991" />{{rp|p=326}}<ref name="Whitney">{{cite journal |last1=Whitney |first1=Hassler |title=Characteristic Functions and the Algebra of Logic |journal=[[Annals of Mathematics]] |date=1933 |volume=34 |issue=3 |pages=405–414 |doi=10.2307/1968168|jstor=1968168 }}</ref>{{rp|p=405}}  Monro (1987) investigated the [[category (mathematics)|category]] '''Mul''' of multisets and their [[morphism]]s, defining a ''multiset'' as a set with an [[equivalence relation]] between elements "of the same ''sort''", and a ''morphism'' between multisets as a [[function (mathematics)|function]] that respects ''sorts''.  He also introduced a ''multinumber'': a function ''f''{{hairsp}}(''x'') from a multiset to the [[natural number]]s, giving the ''multiplicity'' of element ''x'' in the multiset.  Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful.<ref name="Blizard1991" />{{rp|pp=327–328}}<ref>{{cite journal |last1=Monro |first1=G. P. |title=The Concept of Multiset |journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik |date=1987 |volume=33 |issue=2 |pages=171–178 |doi=10.1002/malq.19870330212}}</ref>

==Examples==
One of the simplest and most natural examples is the multiset of [[prime factor]]s of a natural number {{mvar|n}}. Here the underlying set of elements is the set of prime factors of {{mvar|n}}. For example, the number [[120 (number)|120]] has the [[prime factorization]]
<math display="block">120 = 2^3 3^1 5^1,</math>
which gives the multiset {{math|{{mset|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 {{math|{{mset|3, 5}}}}, or it could be {{math|{{mset|4, 4}}}}.  In the latter case it has a solution of multiplicity 2. More generally, the [[fundamental theorem of algebra]] asserts that the [[complex number|complex]] solutions of a [[polynomial equation]] of [[degree of a polynomial|degree]] {{mvar|d}} always form a multiset of cardinality {{mvar|d}}.

A special case of the above are the [[eigenvalue]]s of a [[matrix (mathematics)|matrix]], whose multiplicity is usually defined as their multiplicity as [[root of a polynomial|roots]] of the [[characteristic polynomial]]. However two other multiplicities are naturally defined for eigenvalues, their multiplicities as roots of the [[minimal polynomial (linear algebra)|minimal polynomial]], and the [[geometric multiplicity]], which is defined as the [[dimension (vector space)|dimension]] of the [[Kernel (linear algebra)|kernel]] of {{math|''A'' − ''λI''}} (where {{mvar|λ}} is an eigenvalue of the matrix {{mvar|A}}). These three multiplicities define three multisets of eigenvalues, which may be all different: Let {{mvar|A}} be a {{math|''n''&thinsp;×&thinsp;''n''}} matrix in [[Jordan normal form]] that has a single eigenvalue. Its multiplicity is {{mvar|n}}, its multiplicity as a root of the minimal polynomial is the size of the largest Jordan block, and its geometric multiplicity is the number of Jordan blocks.

==Definition==
A '''multiset''' may be formally defined as an [[ordered pair]] {{math|(''U'', ''m'')}} where {{mvar|U}} is a [[set (mathematics)|set]] called a [[Universe (mathematics)|''universe'']] or the ''underlying set'', and <math>m\colon U \to \mathbb{Z}_{\ge 0}</math> is a function from {{mvar|U}} to the [[nonnegative integer]]s. The value {{tmath|m(a)}} for an element {{tmath|a\in U}} is called the ''multiplicity'' of {{tmath|a}} in the multiset and intepreted as the number of occurences of {{tmath|a}} in the multiset.

The ''support'' of a multiset is the subset of {{tmath|U}} formed by the elements {{tmath|a\in U}} such that {{tmath|m(a)>0}}. A ''finite multiset'' is a multiset with a [[finite set|finite]] support. Most authors define ''multisets'' as finite multisets. This is the case in this article, where, unless otherwise stated, all multisets are finite multisets. 

Some authors{{who|date=February 2025}} define multisets with the additional constraint that {{tmath|m(a)>0}} for every {{tmath|a}}, or, equivalently, the support equals the underlying set.
Multisets with infinite multiplicities have also been studied;<ref>Cf., for instance, Richard Brualdi, ''Introductory Combinatorics'', Pearson.</ref> they are not considered in this article.
Some authors{{who|date=February 2025}} define a multiset in terms of a finite index set {{tmath|I}} and a function {{tmath|f \colon I \rightarrow U}} where the multiplicity of an element {{tmath|a \in U}} is {{tmath|{{!}}f^{-1}(a){{!}}}}, the number of elements of {{tmath|I}} that get mapped to {{tmath|a}} by {{tmath|f}}.

Multisets may be represented as sets, with some elements repeated. For example, the multiset with support {{tmath|\{a,b\} }} and multiplicity function such that {{tmath|1=m(a)=2, \; m(b)=1}} can be represented as {{math|{{mset|''a'', ''a'', ''b''}}}}. A more compact notation, in case of high multiplicities is {{tmath| \{(a, 2), (b, 1)\} }} for the same multiset.

If <math>A=\{a_1, \ldots, a_n\},</math>  a multiset with support included in {{tmath|A}}  is often represented as 
<math display=block>a_1^{m(a_1)} \cdots a_n^{m(a_n)},</math>
to which the computation rules of [[indeterminate (variable)|indeterminate]]s can be applied; that is, exponents 1 and factors with exponent 0 can be removed, and the multiset does not depend on the order of the factors. This allows extending the notation to infinite underlying sets as
<math display=block>\prod_{a\in U} a^{m(a)}.</math> 
An advantage of notation is that it allows using the notation without knowing the exact support. For example, the [[prime factor]]s of a [[natural number]] {{tmath|n}} form a multiset such that
<math display=block>n=\prod_{p \;\text {prime}} p^{m(p)}= 2^{m(2)} 3^{m(3)} 5^{m(5)}\cdots.</math> 

The finite subsets of a set {{tmath|U}} are exactly the multisets with underlying set {{tmath|U}}, such that {{tmath|m(a)\le 1}} for every {{tmath|a\in U}}.

==Basic properties and operations==
Elements of a multiset are generally taken in a fixed set {{mvar|U}}, sometimes called a ''universe'', which is often the set of [[natural number]]s. An element of {{mvar|U}} that does not belong to a given multiset is said to have a multiplicity 0 in this multiset. This extends the multiplicity function of the multiset to a function from {{mvar|U}} to the set <math>\N</math> of non-negative integers. This defines a [[one-to-one correspondence]] between these functions and the multisets that have their elements in {{mvar|U}}.

This extended multiplicity function is commonly called simply the '''multiplicity function''', and suffices for defining multisets when the universe containing the elements has been fixed. This multiplicity function is a generalization of the [[indicator function]] of a [[subset]], and shares some properties with it.

The '''support''' of a multiset <math>A</math> in a universe {{mvar|U}} is the underlying set of the multiset. Using the multiplicity function <math>m</math>, it is characterized as 
<math display="block">\operatorname{Supp}(A) := \{x \in U \mid m_{A}(x) > 0 \}.</math>

A multiset is ''finite'' if its support is finite, or, equivalently, if its cardinality
<math display="block">|A| = \sum_{x\in\operatorname{Supp}(A)} m_A(x) = \sum_{x\in U} m_A(x)</math>
is finite. The ''empty multiset'' is the unique multiset with an [[empty set|empty]] support (underlying set), and thus a cardinality 0.

The usual operations of sets may be extended to multisets by using the multiplicity function, in a similar way to using the indicator function for subsets. In the following, {{mvar|A}} and {{mvar|B}} are multisets in a given universe {{mvar|U}}, with multiplicity functions <math>m_A</math> and <math>m_B.</math>

* '''Inclusion:''' {{mvar|A}} is ''included'' in {{mvar|B}}, denoted {{math|''A'' ⊆ ''B''}}, if <math display="block">m_A(x) \le  m_B(x)\quad\forall x\in U.</math>
* '''Union:''' the ''union'' (called, in some contexts, the ''maximum'' or ''lowest common multiple'') of {{mvar|A}} and {{mvar|B}} is the multiset {{mvar|C}} with multiplicity function<ref name=syropoulos/> <math display="block">m_C(x) = \max(m_A(x),m_B(x))\quad\forall x\in U.</math>
* '''Intersection:''' the ''intersection'' (called, in some contexts, the ''infimum'' or ''greatest common divisor'') of {{mvar|A}} and {{mvar|B}} is the multiset {{mvar|C}} with multiplicity function <math display="block">m_C(x) = \min(m_A(x),m_B(x))\quad\forall x\in U.</math>
* '''Sum:''' the ''sum'' of {{mvar|A}} and {{mvar|B}} is the multiset {{mvar|C}} with multiplicity function <math display="block">m_C(x) = m_A(x) + m_B(x)\quad\forall x\in U.</math> It may be viewed as a generalization of the [[disjoint union]] of sets. It defines a [[commutative monoid]] structure on the finite multisets in a given universe. This monoid is a [[free commutative monoid]], with the universe as a basis.
* '''Difference:''' the ''difference'' of {{mvar|A}} and {{mvar|B}} is the multiset {{mvar|C}} with multiplicity function <math display="block">m_C(x) = \max(m_A(x) - m_B(x), 0)\quad\forall x\in U.</math>

Two multisets are ''disjoint'' if their supports are [[disjoint sets]]. This is equivalent to saying that their intersection is the empty multiset or that their sum equals their union.

There is an inclusion–exclusion principle for finite multisets (similar to [[inclusion–exclusion principle|the one for sets]]), stating that a finite union of finite multisets is the difference of two sums of multisets: in the first sum we consider all possible intersections of an [[parity (mathematics)|odd]] number of the given multisets, while in the second sum we consider all possible intersections of an [[parity (mathematics)|even]] number of the given multisets.{{Citation needed|date=August 2019}}

== Counting multisets ==<!-- Multiset coefficient and Multiset number redirect here -->
[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|370px|[[Bijection]] between 3-subsets of a 7-set (left)<br>and 3-multisets with elements from a 5-set (right)<br>So this illustrates that <math display="inline"> {7 \choose 3} = \left(\!\!{5 \choose 3}\!\!\right).</math>]]
{{See also|Stars and bars (combinatorics)}}
The number of multisets of cardinality {{mvar|k}}, with elements taken from a finite set of cardinality {{mvar|n}}, is sometimes called the '''multiset coefficient''' or '''multiset number'''. This number is written by some authors as <math>\textstyle\left(\!\!{n\choose k}\!\!\right)</math>, a notation that is meant to resemble that of [[binomial coefficient]]s; it is used for instance in (Stanley, 1997), and could be pronounced "{{mvar|n}} multichoose {{mvar|k}}" to resemble "{{mvar|n}} choose {{mvar|k}}" for <math>\tbinom n k.</math> Like the [[binomial distribution]] that involves binomial coefficients, there is a [[negative binomial distribution]] in which the multiset coefficients occur.  Multiset coefficients should not be confused with the [[multinomial coefficient]]s that occur in the [[multinomial theorem]].

The value of multiset coefficients can be given explicitly as
<math display="block">\left(\!\!{n\choose k}\!\!\right) = {n+k-1 \choose k} = \frac{(n+k-1)!}{k!\,(n-1)!} = {n(n+1)(n+2)\cdots(n+k-1)\over k!},</math>
where the second expression is as a binomial coefficient;{{efn|The formula {{tmath|\tbinom{n+k-1}k}} does not work for {{math|1=''n'' = 0}} (where necessarily also {{math|1=''k'' = 0}}) if viewed as an ordinary binomial coefficient since it evaluates to {{tmath|\tbinom{-1}0}}, however the formula {{math|''n''(''n''+1)(''n''+2)...(''n''+''k''−1)/''k''!}} does work in this case because the numerator is an [[empty product]] giving {{math|1=1/0! = 1}}. However {{tmath|\tbinom{n+k-1}k}} does make sense for {{math|1=''n'' = ''k'' = 0}} if interpreted as a [[Binomial coefficient#Binomial coefficients as polynomials|generalized binomial coefficient]]; indeed {{tmath|\tbinom{n+k-1}k}} seen as a generalized binomial coefficient equals the extreme right-hand side of the above equation.}} many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality {{mvar|k}} of a set of cardinality {{math|''n'' + ''k'' −&thinsp;1}}. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a [[rising factorial power]]
<math display="block">\left(\!\!{n \choose k}\!\!\right) = {n^{\overline{k}}\over k!},</math>
to match the expression of binomial coefficients using a falling factorial power:
<math display="block">{n \choose k} = {n^{\underline{k}}\over k!}.</math>

For example, there are 4 multisets of cardinality 3 with elements taken from the set {{math|{{mset|1, 2}}}} of cardinality 2 ({{math|1=''n'' = 2}}, {{math|1=''k'' = 3}}), namely {{math|{{mset|1, 1, 1}}}}, {{math|{{mset|1, 1, 2}}}}, {{math|{{mset|1, 2, 2}}}}, {{math|{{mset|2, 2, 2}}}}. There are also 4 ''subsets'' of cardinality 3 in the set {{math|{{mset|1, 2, 3, 4}}}} of cardinality 4 ({{math|''n'' + ''k'' −&thinsp;1}}), namely {{math|{{mset|1, 2, 3}}}}, {{math|{{mset|1, 2, 4}}}}, {{math|{{mset|1, 3, 4}}}}, {{math|{{mset|2, 3, 4}}}}.

One simple way to [[mathematical proof|prove]] the equality of multiset coefficients and binomial coefficients given above involves representing multisets in the following way.  First, consider the notation for multisets that would represent {{math|{{mset|''a'', ''a'', ''a'', ''a'', ''a'', ''a'', ''b'', ''b'', ''c'', ''c'', ''c'', ''d'', ''d'', ''d'', ''d'', ''d'', ''d'', ''d''}}}} (6 {{mvar|a}}s, 2 {{mvar|b}}s, 3 {{mvar|c}}s, 7 {{mvar|d}}s) in this form:

:{{nowrap|{{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} }}

This is a multiset of cardinality {{math|1=''k'' =&thinsp;18}} made of elements of a set of cardinality {{math|1=''n'' = 4}}.  The number of characters including both dots and vertical lines used in this notation is {{math|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 {{math|4 − 1}} vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 of a set of cardinality {{math|18 + 4 − 1}}.  Equivalently, it is the number of ways to arrange the 18 dots among the {{math|18 + 4 − 1}} characters, which is the number of subsets of cardinality 18 of a set of cardinality {{math|18 + 4 − 1}}. This is
<math display="block">{4+18-1 \choose 4-1}={4+18-1 \choose 18} = 1330,</math>
thus is the value of the multiset coefficient and its equivalencies:
<math display="block">\begin{align}
\left(\!\!{4\choose18}\!\!\right)
&={21\choose18}=\frac{21!}{18!\,3!}={21\choose3}, \\[1ex]
&=\frac{{\color{red}{\mathfrak{
4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}
\cdot
\mathbf{19\cdot20\cdot21}}{\mathbf{1\cdot2\cdot3}
\cdot
{\color{red}{\mathfrak{
4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}}, \\[1ex]
&=\frac{
1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18\;\mathbf{\cdot\;19\cdot20\cdot21}}
{\,1\cdot2\cdot3\cdot4\cdot5\cdots
16\cdot17\cdot18\;\mathbf{\cdot\;1\cdot2\cdot3\quad}}, \\[1ex]
&=\frac{19\cdot20\cdot21}{1\cdot2\cdot3}.
\end{align}</math>

From the relation between binomial coefficients and multiset coefficients, it follows that the number of multisets of cardinality {{mvar|k}} in a set of cardinality {{mvar|n}} can be written
<math display="block">\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k}.</math>
Additionally,
<math display="block">\left(\!\!{n\choose k}\!\!\right)=\left(\!\!{k+1\choose n-1}\!\!\right).</math>

=== Recurrence relation ===
A [[recurrence relation]] for multiset coefficients may be given as
<math display="block">\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right) \quad \mbox{for } n,k>0</math>
with
<math display="block">\left(\!\!{n \choose 0}\!\!\right) = 1,\quad n\in\N, \quad\mbox{and}\quad \left(\!\!{0 \choose k}\!\!\right) = 0,\quad k>0.</math>

The above recurrence may be interpreted as follows.
Let <math>[n] := \{1,\dots,n\}</math> be the source set. There is always exactly one (empty) multiset of size 0, and if {{math|1=''n'' = 0}} there are no larger multisets, which gives the initial conditions.

Now, consider the case in which {{math|''n'', ''k'' > 0}}. A multiset of cardinality {{mvar|k}} with elements from {{math|[''n'']}} might or might not contain any instance of the final element {{mvar|n}}. If it does appear, then by removing {{mvar|n}} once, one is left with a multiset of cardinality {{math|''k'' −&thinsp;1}} of elements from {{math|[''n'']}}, and every such multiset can arise, which gives a total of
<math display="block">\left(\!\!{n\choose k - 1}\!\!\right)</math> possibilities.

If {{mvar|n}} does not appear, then our original multiset is equal to a multiset of cardinality {{mvar|k}} with elements from {{math|[''n'' −&thinsp;1]}}, of which there are
<math display="block">\left(\!\!{n-1\choose k}\!\!\right).</math>

Thus,
<math display="block">\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right).</math>

===Generating series===
The [[generating function]] of the multiset coefficients is very simple, being
<math display="block">\sum_{d=0}^\infty \left(\!\!{n\choose d}\!\!\right)t^d = \frac{1}{(1-t)^n}.</math>
As multisets are in one-to-one correspondence with [[monomial]]s, <math>\left(\!\!{n\choose d}\!\!\right)</math> is also the number of monomials of [[Degree of a polynomial#Extension to polynomials with two or more variables|degree]] {{mvar|d}} in {{mvar|n}} indeterminates. Thus, the above series is also the [[Hilbert series]] of the [[polynomial ring]] <math>k[x_1, \ldots, x_n].</math>

As <math>\left(\!\!{n\choose d}\!\!\right)</math> is a polynomial in {{mvar|n}}, it and the generating function are well defined for any [[complex number|complex]] value of {{mvar|n}}.

=== Generalization and connection to the negative binomial series ===
The multiplicative formula allows the definition of multiset coefficients to be extended by replacing {{mvar|n}} by an arbitrary number {{mvar|α}} (negative, [[real number|real]], or complex):
<math display="block">\left(\!\!{\alpha\choose k}\!\!\right) = \frac{\alpha^{\overline k}}{k!} = \frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k(k-1)(k-2)\cdots 1}
  \quad\text{for } k\in\N \text{ and arbitrary } \alpha.
</math>

With this definition one has a generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the <math>\left(\!\!{\alpha\choose k}\!\!\right)</math> negative binomial coefficients:
<math display="block">(1-X)^{-\alpha} = \sum_{k=0}^\infty \left(\!\!{\alpha\choose k}\!\!\right) X^k.</math>

This [[Taylor series]] formula is valid for all complex numbers ''α'' and ''X'' with {{math|{{abs|''X''}} < 1}}. It can also be interpreted as an [[identity (mathematics)|identity]] of [[formal power series]] in ''X'', where it actually can serve as definition of arbitrary powers of series with constant coefficient equal to&nbsp;1; the point is that with this definition all identities hold that one expects for [[exponentiation]], notably

<math display="block">(1-X)^{-\alpha}(1-X)^{-\beta}=(1-X)^{-(\alpha+\beta)} \quad\text{and}\quad ((1-X)^{-\alpha})^{-\beta}=(1-X)^{-(-\alpha\beta)},</math>
and formulas such as these can be used to prove identities for the multiset coefficients.

If {{mvar|α}} is a nonpositive integer {{mvar|n}}, then all terms with {{math|''k'' > −''n''}} are zero, and the infinite series becomes a finite sum. However, for other values of {{mvar|α}}, including positive integers and [[rational number]]s, the series is infinite.

==Applications==
Multisets have various applications.<ref name="Singh2007" /> They are becoming fundamental in [[combinatorics]].<ref name="Aigner1979">{{cite book|last=Aigner|first=M.|year=1979|title=Combinatorial Theory|publisher=Springer Verlag | location=New York/Berlin}}</ref><ref name="Anderson1987">{{cite book|last=Anderson|first=I.|year=1987|title=Combinatorics of Finite Sets|url=https://archive.org/details/combinatoricsoff0000ande|url-access=registration|publisher=Clarendon Press | location=Oxford|isbn=978-0-19-853367-2 }}</ref><ref name="Stanley1997">{{cite book|last=Stanley|first=Richard P.|author-link=Richard P. Stanley|year=1997|title=Enumerative Combinatorics|volume=1|publisher=Cambridge University Press | url=http://www-math.mit.edu/~rstan/ec/|isbn=0-521-55309-1}}</ref><ref name="Stanley1999">{{cite book | last=Stanley|first=Richard P. |year=1999|title=Enumerative Combinatorics|volume=2|publisher=Cambridge University Press|isbn=0-521-56069-1}}</ref> Multisets have become an important tool in the theory of [[relational database]]s, which often uses the synonym ''bag''.<ref name="GrumbachMilo1996">{{cite journal| last1=Grumbach|first1=S.| last2=Milo|first2=T| year=1996| title=Towards tractable algebras for bags|journal=Journal of Computer and System Sciences| volume=52| issue=3| pages=570–588| doi=10.1006/jcss.1996.0042|doi-access=free}}</ref><ref name="LibkinWong1994">{{cite book| last1=Libkin|first1=L.|author1link = Leonid Libkin| last2=Wong|first2=L.|year=1994|chapter=Some properties of query languages for bags| title=Proceedings of the Workshop on Database Programming Languages|publisher=Springer Verlag|pages=97–114}}</ref><ref name="LibkingWong1995">{{cite journal|last1=Libkin|first1=L.|last2=Wong|first2=L.|year=1995|title=On representation and querying incomplete information in databases with bags|journal=[[Information Processing Letters]]| volume=56| issue=4| pages=209–214|doi=10.1016/0020-0190(95)00154-5}}</ref> For instance, multisets are often used to implement relations in database systems. In particular, a table (without a primary key) works as a multiset, because it can have multiple identical records. Similarly, [[SQL]] operates on multisets and returns identical records. For instance, consider "SELECT name from Student". In the case that there are multiple records with name "Sara" in the student table, all of them are shown. That means the result of an SQL query is a multiset; if the result were instead a set, the repetitive records in the result set would have been eliminated. Another application of multisets is in modeling [[multigraph]]s. In multigraphs there can be multiple edges between any two given [[vertex (graph theory)|vertices]]. As such, the entity that specifies the edges is a multiset, and not a set.

There are also other applications. For instance, [[Richard Rado]] used multisets as a device to investigate the properties of families of sets. He wrote, "The notion of a set takes no account of multiple occurrence of any one of its members, and yet it is just this kind of information that is frequently of importance. We need only think of the set of roots of a polynomial ''f''{{hairsp}}(''x'') or the [[spectrum of an operator|spectrum]] of a [[linear operator]]."<ref name="Blizard1991" />{{rp|pp=328–329}}

==Generalizations==
Different generalizations of multisets have been introduced, studied and applied to solving problems.
* Signed multisets (in which multiplicity of an element can be any [[integer]])<ref name="Blizard1990">{{cite journal|last=Blizard|first=Wayne D.|year=1990|title=Negative Membership|journal=Notre Dame Journal of Formal Logic|volume=31|issue=3|pages=346–368|doi=10.1305/ndjfl/1093635499 |s2cid=42766971 |doi-access=free}}</ref>
* Real-valued multisets (in which multiplicity of an element can be any [[real number]])<ref>{{cite journal| last=Blizard|first=Wayne D.|year=1989|title=Real-valued Multisets and Fuzzy Sets|journal=[[Fuzzy Sets and Systems]]|volume=33|issue=1 |pages=77–97|doi=10.1016/0165-0114(89)90218-2}}</ref>
* Fuzzy multisets<ref name="Yager1986">{{cite journal|last=Yager|first=R. R.|year=1986|title=On the Theory of Bags|journal=International Journal of General Systems|volume=13|issue=1 |pages=23–37|doi=10.1080/03081078608934952}}</ref>
* Rough multisets<ref name="Grzymala-Busse1987">{{cite book|last=Grzymala-Busse|first=J.|year=1987|chapter=Learning from examples based on rough multisets|title=Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems|location=Charlotte, North Carolina|pages=325–332}}</ref>
* Hybrid sets<ref name="Loeb1992">{{cite journal|last=Loeb|first=D.|year=1992|title=Sets with a negative numbers of elements|journal=[[Advances in Mathematics]]|volume=91|issue=1 |pages=64–74|doi=10.1016/0001-8708(92)90011-9|doi-access=free}}</ref>
* Multisets whose multiplicity is any real-valued [[step function]]<ref name="Miyamoto2001">{{cite book|last=Miyamoto|first=S.|title=Multiset Processing |chapter=Fuzzy Multisets and Their Generalizations |year=2001|series=Lecture Notes in Computer Science |volume=2235|pages=225–235|publisher=Springer |location=Berlin, Heidelberg |doi=10.1007/3-540-45523-X_11 |isbn=978-3-540-43063-6 }}</ref>
* Soft multisets<ref name="Alkhazaleh2011">{{cite journal|last1=Alkhazaleh|first1=S.|last2=Salleh|first2=A. R.|last3=Hassan|first3=N.|year=2011|title=Soft Multisets Theory|journal=Applied Mathematical Sciences|volume=5|issue=72|pages=3561–3573}}</ref>
* Soft fuzzy multisets<ref name="Alkhazaleh2012">{{cite journal|last1=Alkhazaleh|first1=S.|last2=Salleh|first2=A. R.|year=2012|title=Fuzzy Soft Multiset Theory|journal=Abstract and Applied Analysis|volume=2012 |pages=1–20 |doi=10.1155/2012/350603 |doi-access=free }}</ref>
* Named sets (unification of all generalizations of sets)<ref>{{cite book|last=Burgin|first=Mark|year=1990|chapter=Theory of Named Sets as a Foundational Basis for Mathematics|title=Structures in Mathematical Theories|publisher=San Sebastian|pages=417–420|chapter-url=http://www.blogg.org/blog-30140-date-2005-10-26.html}}</ref><ref>{{cite journal|last=Burgin|first=Mark|year=1992|title=On the concept of a multiset in cybernetics|journal=Cybernetics and System Analysis|volume=3|pages=165–167}}</ref><ref>{{cite arXiv|last=Burgin|first=Mark|year=2004|title=Unified Foundations of Mathematics|eprint=math/0403186}}</ref><ref>{{cite book|last=Burgin|first=Mark|year=2011|title=Theory of Named Sets|series=Mathematics Research Developments|publisher=Nova Science Pub Inc|isbn=978-1-61122-788-8}}</ref>

== See also ==
* [[Frequency (statistics)]] as multiplicity analog
* [[Quasi-set theory|Quasi-sets]]
* [[Set theory]]
* [[Bag-of-words model]]
* {{Wikiversity-inline|Partitions of multisets}}

== Notes ==
{{Notelist}}

==References==
<references/>

[[Category:Basic concepts in set theory]]
[[Category:Factorial and binomial topics]]