多重集合のソースを表示

[[数学]]における'''多重集合'''（たじゅうしゅうごう、<em lang="en">multiset</em>）あるいは'''バッグ'''（{{lang|en|''bag''}}; かばん）は、[[集合]]に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという[[重複度]]を考え合わせた集合概念である。'''非順序対'''、非順序組 {{lang|en|(unordered tuple)}} ともいう{{efn|文脈によっては集合のことを非順序対 (unordered pair) などと呼ぶこともある。特に、{{math|''x'' &ne; ''y''}} のときの {{math|{{mset|''x'', ''y''}}}} を非順序対と呼ぶときは、これが集合であると理解しても多重集合であると理解しても論理的には同じである（{{math|1=''x'' = ''y''}} のときは差異が認められる）。}}。

[[クヌース]]によれば、1970年代に最初に多重集合 (multiset) という言葉を提案したのは、オランダ人数学者の[[ニコラース・ホーバート・ド・ブラン]] (IPA: {{IPA|dɪ bʁœyn}}) であるという<ref name="Knuth1998">{{cite book | last = Knuth | first = Donald E. | authorlink = クヌース
| title = [[The Art of Computer Programming]] &ndash; Vol. 2: Seminumerical Algorithms
| publisher = Addison Wesley
| year =1998 | edition=3rd edition
| pages =694
| isbn =0201896842 }} 

クヌースは同書で、多重集合に対して提案された他の名前（例えば,リスト(list)、まとまり(bunch)、バッグ(bag)、堆積(heap)、標本(sample)、重みつき集合(weighted set)、コレクション(collection)、組(suite).など）も提示している。
</ref><ref name="Blizard">
{{Cite journal|
|author= Wayne D. Blizard
|year= 1991
|title = The development of multiset theory
|journal = The Review of Modern Logic
|volume = 1 |issue = 4 |pages = 319-352
|doi=
|url= https://projecteuclid.org/journals/modern-logic/volume-1/issue-4/The-development-of-multiset-theory/rml/1204834739.full
|accessdate= 2022-02-12
}}

多重集合の歴史に関するサーベイ論文である。
</ref>。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表された[[リヒャルト・デデキント]]の有名な論文 "Was sind und was sollen die Zahlen?" （「数とは何か、何であるべきか？」）において、実質的に多重集合の概念が用いられている<ref>{{cite book | author=デーデキント | coauthors = 河野伊三郎 (訳) | title = 数について | publisher = 岩波書店 | year =1967 |isbn = 4003392418| pages = 139 }} </ref><ref>
{{Cite journal|
|last= Syropoulos | first= Apostolos
|year= 2001
|title = Mathematics of Multisets
|journal = WMP '00 Proceedings of the Workshop on Multiset Processing: Mathematical, Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View
|editor = C. S. Calude et al.
|pages = 347&ndash;358
|publisher= Springer-Verlag
|doi = 
|id = ISBN 3-540-43063-6
|url= http://citeseerx.ksu.edu.sa/viewdoc/summary?doi=10.1.1.58.5406
|format= PDF
|accessdate= 2010-11-26
}}
</ref><ref name="Blizard" />。

== 導入 ==
集合と多重集合の峻別のために、集合のように [[ブレース|波括弧]] {{math|{{mset|,}}}}で囲む代わりに、二重波括弧 {{math|{{braces|,}}}} (<math display="inline">\{\!\!\{,\}\!\!\}</math>){{efn|[[黒板太字|中抜き太字]]の類例だが、{{仮リンク|重ね打ち|en|Overstrike}} (double struck) で表すときは間が広いと「集合の集合」と紛らわしい。}} や[[ブラケット|角括弧]] {{math|{{bracket|,}}}}<ref>{{cite book|title=Discrete mathematics|first=James L.|last=Hein|publisher=Jones & Bartlett Publishers|year=2003|isbn=0-7637-2210-3|pages=29–30}}</ref> あるいは中抜き波括弧 {{math|{{unicode|&#x2983;,&#x2984;}}}}(<math display="inline">\{\!\vert,\vert\!\}</math>).<ref>Cristian S. Calude, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View Springer Verlag 2001, ISBN 3-540-43063-6 S. 105</ref> などで囲むこともある。

集合と多重集合と[[順序対]]（あるいは組）は例えば次のような点で差異が認められる。{{math|''a'' &ne; ''b''}} として、
* 順序対: {{math|(''a'', ''a'', ''b'')}} と {{math|(''a'', ''b'', ''a'')}} とは順序三つ組として異なる（各成分の現れる順番を変えてはいけない）。これらはもちろん {{math|(''a'', ''b'')}} とも異なる。
* 多重集合: {{math|{{unicode|⦃}}''a'', ''a'', ''b''{{unicode|⦄}}}} と {{math|{{unicode|⦃}}''a'', ''b'', ''a''{{unicode|⦄}}}} は多重集合として一致する（元の現れる順番は関係無い）が、{{math|{{unicode|⦃}}''a'', ''a'', ''b''{{unicode|⦄}}}} と {{math|{{unicode|⦃}}''a'', ''b''{{unicode|⦄}}}} は多重集合として異なる（重複度が異なるなら多重集合としては異なる）。
* 集合: {{math|{{mset|''a'', ''a'', ''b''}}}} と {{math|{{mset|''a'', ''b'', ''a''}}}} と {{math|{{mset|''a'', ''b''}}}} はいずれも同じ集合である（元の現れる順番は関係なく、また同じ元は何度現われてもひとつあることと同じ）{{efn|このような外延的記法での例を挙げると、集合なのになぜか多重集合のようではないか、不自然だといったようなことを考える向きもあるだろうが、内包的記法が多用される数学の文脈では（それを外延的に書き直すと）このような例は実際に頻繁に遭遇することであり、このように規約を設けることには便宜上も意味のあることである。簡単な例で言えば、偶数の集合 {{math|1=2'''Z''' = {{mset|2''n'' {{!}} ''n'' は整数}}}} と 4 の倍数の集合 {{math|1=4'''Z''' = {{mset|4''n'' {{!}} ''n'' は整数}}}} の和集合はもちろん偶数の集合だが、{{math|1=2'''Z''' &cup; 4'''Z''' = {{mset|1=''x'' {{!}} ''x'' = 2''n'' または ''x'' = 4''m'' (''n'', ''m'' は整数)}}}} の右辺には 4 の倍数が 2 回ずつ現れている。}}。

建前上は基本的に集合のみを扱い多重集合を扱わないというような（しばしば初等的な）文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 {{math|''x''&sup2; + ''ax'' + ''b''}} に対して、{{math|1=&Delta; := ''a''&sup2; &minus; 4''b''}} とおき、その[[多項式の根|根]]の集合
: <math>\lbrace x\mid x^2 + ax + b = 0\rbrace</math>
を考えると、この集合の濃度（根の個数）は {{math|&Delta; &ne; 0}} のとき {{math|2}} だが、{{math|1=&Delta; = 0}} のときは[[退化 (数学)|退化]]して {{math|1}} になってしまう。これを {{math|1=&Delta; = 0}} のときは 2 つの根がたまたま重なったもの（[[重根 (多項式)|重根]]）と考えて重複度 {{math|2}} を与えることにより、根は {{math|1=&Delta; = 0}} のときも含めて常に {{math|2}} 個であると考えることができる。この例は一般に、[[代数学の基本定理|代数方程式論の基本定理]]の一つの表現「[[代数方程式|{{mvar|n}}-次方程式]]は必ず重複度まで込めてちょうど {{mvar|n}} 個の根を持つ」として述べることができる。同様の例として、複素解析函数に対する[[零点]]や[[極 (複素解析)|極]]の位数（重複度）あるいは曲線の[[接触 (数学)|接触]]の位数（接触度）なども挙げられる（[[重複度 (数学)]]の項を参照）。

またたとえば、自然数 {{mvar|n}} の[[素因数分解]]
: <math>n = 2^{m(2)}3^{m(3)}5^{m(5)}\cdots p^{m(p)}\cdots</math>
（実際には {{mvar|n}} ごとに右辺に現れる素因子は有限個、つまり殆どの {{math|''m''(''p'')}} が {{math|0}} となる実質有限積である）は、自然数 {{mvar|n}} を素数全体の成す集合 {{math|'''P'''}} を台とする多重集合 {{math|('''P''', ''m'')}} として表示する方法を与えるものと解釈することができる（[[算術の基本定理|素因数分解が積の順番の違いを除いて一意であるということ]]が多重集合の性質に対応する）。[[置換 (数学)|置換]]の巡回置換分解あるいは巡回置換型も同様である。

同様に、自然数 {{mvar|n}} の[[自然数の分割|分割]]を考えることは、分割に現れる各整数 {{math|''k'' (&le; ''n'')}} の個数を重複度 {{math|''m''(''k'')}} ととれば、自然数全体の成す集合 {{math|'''N'''}} を台とする多重集合 {{math|('''N''', ''m'')}} であって、重複度関数 {{mvar|m}} が次の二条件
: <math> m(k) =0 \quad (k > n)</math> 
: <math> 1 \cdot m(1) + 2 \cdot m(2) + \cdots + k \cdot m(k) + \cdots + n \cdot m(n) = n</math>
を満たすようなものを一つ定めることに他ならない。ゆえに、[[分割数]]は、各自然数 {{mvar|n}} に対してこのような重複度関数 {{mvar|m}} のとり方が {{math|''p''(''n'')}} 通りあることを示している。

== 歴史 ==
Wayne Blizard は、“in ancient times, the number n was often represented by a collection of n strokes, tally marks, 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}}</ref>（「古代、数 {{mvar|n}} は {{mvar|n}} 本の棒、画線、単位の集まりとして表されていた」）なる論法を以って、多重集合の起源はまさに数の起源にまで遡れるとする。これら、あるいは同様の対象の集まりは、棒・画線・単位が各々区別できないもの (indistinguishable) と考えて多重集合になる。これは多重集合の概念が数学に取り入れられる以前から人々に暗に用いられていたことを示している。

そのような理由により多重集合は、この構造が必要とされるたびに何度も再発見され、異なる名称を以って文献に現れることとなる<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>。例えば、{{harvtxt|Peterson|1981}} はこれを bag と呼んでおり<ref name="Peterson1981">{{cite book|first=James L.|last=Peterson|title=Petri Net Theory and the Modelling of Systems|publisher=Prentice-Hall|location=Englewood Cliffs, New Jersey|year=1981|url=http://jklp.org/profession/books/pn/}}</ref>、その語は {{harv|Cerf||||1971}} の影響によるものである<ref>{{cite report|first=Vint|last=Cerf|authorlink=Vint Cerf|first2=E.|last2=Fernandez|first3=K.|last3=Gostelow|first4=S.|last4=Volansky|title=Formal Control Flow Properties of a Model of Computation|id=ENG-7178|publisher=Computer Science Department, University of California|location=Los Angeles, California|date=December 1971}}</ref>。多重集合は他にも aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set) などと呼ばれている<ref name="Blizard1991" /><ref name="Singh2007">{{cite journal|last=Singh|first=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>。

ただ多重集合の概念が古代より暗に用いられていたと言っても、それらが明示的に調べられるようになるのはずっと後になってからのことである。多重集合の最初の研究として知られるのは1150年ごろ、インドの数学者[[バースカラ2世]]による、多重集合の順列に関するものである<ref name="Knuth1998"/>{{rp|694}}。{{仮リンク|マリウス・ニゾリウス|en|Marius Nizolius}} (1498–1576) の業績には多重集合の概念に関する別の先駆的言及が含まれる<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>。{{harvtxt|Kircher|1650}} は一つの元のみ重複する場合の多重集合の順列の数を求めた<ref>{{cite book|last=Kircher|first=Athanasius|authorlink=アタナシウス・キルヒャー|year=1650|title=Musurgia Universalis|publisher=Corbelletti|location=Rome}}</ref>。{{仮リンク|ジャン・プルステ|en|Jean Prestet}}は1675年に多重集合の順列に関する一般法則を著した<ref>{{cite book|last=Prestet|first=Jean|year=1675|title=Elemens des Mathematiques|publisher=André Pralard|location=Paris}}</ref>。{{harvtxt|Wallis|1685}} はこの法則をより詳細に説明している<ref>{{cite book|last=Wallis|first=John|authorlink=ジョン・ウォリス|year=1685|title=A treatise of algebra|publisher=John Playford|location=London}}</ref>

明確な形で多重集合が現れるのは[[リヒャルト・デーデキント]]の手による<ref>{{cite book|last=Dedekind|first=Richard|authorlink=Richard Dedekind|year=1888|title=Was sind und was sollen die Zahlen?|publisher=Vieweg|location=Braunschweig}}</ref><ref>{{cite book|last=Syropoulos|first=Apostolos|year=2001|chapter=Mathematics of Multisets|editor-first=C. S.|editor-last=Calude|title=Multiset processing: Mathematical, computer science, and molecular computing points of view|publisher=Springer-Verlag|pages=347&ndash;358|display-editors=etal}}</ref>が、数学者が多重集合を定式化して明確な数学的対象としてその研究を始めたのは20世紀に入ってからである。

== 定義 ==
{{mvar|X}} を全体集合とし、その任意の部分集合 {{mvar|A}} と {{mvar|X}} から非負整数全体の集合 {{math|'''N'''}} への写像 {{math|''m'': ''X'' &rarr; '''N'''}} で、{{math|[[関数の台|supp]](''m'') &sub; ''A''}} すなわち {{mvar|A}} に属さない元 {{mvar|x}} に対しては恒等的に {{math|1=''m''(''x'') = 0}} を満たすものの組 {{math|(''A'', ''m'')}} を、{{mvar|A}} を台集合とする'''多重集合'''といい、台集合 {{mvar|A}} の各元 {{mvar|a}} に対してその {{mvar|m}} による像 {{math|''m''(''a'')}} を {{mvar|a}} の'''重複度'''という。紛れのおそれの無い場合、多重集合 {{math|(''A'', ''m'')}} をその台集合 {{mvar|A}} で表す。

非負整数値の重複度を持つ多重集合 {{math|(''A'', ''m'')}} は、項の値に重複のある[[列 (数学)|列]]の集合として
: <math>\{(\overbrace{a_1,a_1,\ldots,a_1}^{m(a_1)\text{ terms}}),(
\overbrace{a_2,a_2,\ldots,a_2}^{m(a_2)\text{ terms}}),\ldots\}</math>
のようにも記される。

たとえば、二つの文字 {{mvar|a, b}} について {{mvar|a}} を 2 個、{{mvar|b}} を 1 個含むような多重集合を考えると、この台集合は {{math|{{mset|''a'', ''b''}}}} であり、各元の重複度 {{math|1=(''a'', ''m''(''a'') = 2), (''b'', ''m''(''b'') = 1)}} を合わせた {{math|({{mset|''a'', ''b''}}, {{mset|(''a'', 2), (''b'', 1)}})}} が、同じ多重集合を台集合とその上の重複度という構造によって表したものとなる。またこれは簡単に {{math|{{mset|''a'', ''a'', ''b''}}}} とも記す。

新たに添字を導入して
: <math>\{a_1^{(1)},a_1^{(2)},\ldots,a_1^{(m(a_1))},
 a_2^{(1)},a_2^{(2)},\ldots,a_2^{(m(a_2))},\ldots\}</math>
などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような[[族 (数学)|族]] {{math|(''b{{ind|i}}''){{sub|''i''&isin;''I''}}}} に対して、同じ元からなる多重集合を {{math|{{mset|''b{{ind|i}}''}}{{sub|''i''&isin;''I''}}}} で表すことがある{{efn|この記法は（特に添字集合が明らかであるとして省略するとき）[[数列]]を表す慣習的な記法 {{math|{''a{{ind|n}}''} }}と紛らわしい。}}。

== 多重集合の構成 ==
[[文字集合]] {{math|&Omega;}} を固定したとき、{{math|&Omega;}} 上の有限多重集合は、{{math|&Omega;}} 上の[[文字列]]で文字の順番を自由に取り替えたものと同一視できるから、{{math|&Omega;}} 上の有限文字列全体が[[文字列結合|文字列の連接]]を演算として[[空文字列]]を[[単位元]]とする {{math|&Omega;}} の生成する[[自由群|自由モノイド]]となるのと並行して、{{math|&Omega;}} の生成する[[自由加群|自由可換モノイド]]と {{math|&Omega;}} 上の有限多重集合の全体とが同一視される。すなわち、{{math|&Omega;}} の元からなる有限多重集合は、{{math|&Omega;}} 上の自由モノイドの[[アーベル商|アーベル化]]の元である。

長さ {{mvar|n}} の有限列（[[タプル|{{mvar|n}}-組]]）に {{mvar|n}}-次[[対称群]]を成分の（番号の）入れ替えとして作用させるとき、この作用で割って得られる同値類（軌道）あるいはその任意の代表元を（重複度まで込めた濃度が {{mvar|n}} の）多重集合と見做すことができる。

== 多重集合の演算と重複度函数 ==
{{seealso|指示函数|ファジィ集合}}
多重集合 {{math|(''A'', ''m{{ind|A}}'')}} に対し、台集合 {{mvar|A}} の部分集合 {{mvar|B}} を台集合とする多重集合 {{math|(''B'', ''m{{ind|B}}'')}} で {{mvar|B}} の各元 {{mvar|b}} の重複度について
: <math>m_B(b) \leq m_A(b)</math>
が成り立つとき、多重集合 {{math|(''B'', ''m{{ind|B}}'')}} は多重集合 {{math|(''A'', ''m{{ind|A}}'')}} の'''部分多重集合'''であるといい、{{math|(''B'', ''m{{ind|B}}'') &sub; (''A'', ''m{{ind|A}}'')}} で表す。

また、多重集合に対する和、差、積、対称差などの概念が、通常の集合に関する[[合併 (集合論)|和]]、[[差集合|差]]、[[共通部分 (数学)|積]]、[[対称差]]などに従って定義される。例えば、多重集合 {{mvar|A, B}} の和 {{math|''A'' &cup; ''B''}} は包含関係 {{math|&sub;}} を順序とする上限、積 {{math|''A'' &cap; ''B''}} は {{math|&sub;}} に関する下限である。多重集合の演算は台集合に対しては通常の集合演算として作用するが、その元の重複度については多少の注意を要する。

{| class="wikitable" style="float: right; margin: 1ex auto 1ex 1em;"
|+ 集合の[[指示函数]] {{mvar|&chi;}}
|-
!
| {{mvar|U}}: 全体集合, {{math|''A'' &sube; ''U''}}
<math>\chi_A\colon U \to {0,1}</math>
|-
! [[交叉 (集合論)|交叉]]
| <math>\chi_{A\cap B} = \min\{\chi_A,\chi_B\}</math>
|-
! [[合併 (集合論)|合併]]
| <math>\chi_{A\cup B} = \max\{{\chi_A,\chi_B}\}</math>
|-
! [[補集合]]
| <math>\chi_{\complement A} = \chi_U - \chi_A</math>
|-
! [[包含写像|包含]]
| <math>A\subseteq B \iff \chi_{A} \le \chi_{B}</math>
|-
! [[デカルト積]]
| <math>\chi_{A \times B} = \chi_A\cdot\chi_B</math>
|-
! [[濃度 (数学)|濃度]]
| <math>|A|=\sum_{x\in X} \chi_{A}(x)</math>
|}
集合 {{mvar|X}} の（全ての元を各個に区別して）各元の重複度を {{math|1}} としたときの重複度関数は集合 {{mvar|X}} の[[指示関数]]である。[[有限集合]]の指示関数を[[数え上げ測度]]で積分したものは集合の基数をあたえるから、多重集合の元 {{mvar|a}} の重複度は、同じ値 {{mvar|a}} を持つ元を全てあわせた集合の指示関数の積分で得られる。指示関数が集合を定義するのと同様に、多重集合は重複度関数によって定義されると考えることができる（指示函数を「集合の定義函数」と呼ぶことがあるのと同様に、重複度函数を「'''多重集合の定義函数'''」と呼ぶことがある）。特に、多重集合の和、積、対称差などの重複度関数は、集合の指示関数が満たすのと同様の算術
:<math>m_{A\cap B}(x) = \min\{m_A(x),m_B(x)\}(=: (m_A \wedge m_B)(x)),</math>
:<math>m_{A\cup B}(x) = \max\{m_A(x),m_B(x)\}(=: (m_A \vee m_B)(x)),</math>
:<math>m_{A\triangle B}(x) = |m_A(x) - m_B(x)|</math>
に従う。また重複度函数の和 {{math|''m''{{ind|''A''}} + ''m''{{ind|''B''}}}} を重複度函数に持つ多重集合を {{mvar|A}} と {{mvar|B}} との'''結合''' (join) あるいは直和（非交和、sum）と呼び
: <math>A\sqcup B, A\uplus B</math>
などで表す（非交和と呼ぶことがあるにもかかわらず、台集合として {{math|1=''A'' &cap; ''B'' = &empty;}} であることは必要でないことに注意。これは台集合の交わりに属する元であっても、それらはその重複度のために、何れの台集合に由来する元であるかの区別を受けるためである）。すなわち
: <math>m_{A\sqcup B}(x) = m_A(x) + m_B(x)</math>
が成り立つ。特に台集合が交わりを持たないときは
: <math>m_{A\sqcup B}(x) = \max\{m_A(x),m_B(x)\} = \begin{cases}m_A(x) & (x\in A)\\ m_B(x) & (x\in B)\end{cases}</math>
と書ける。

== 多重集合の数え上げ ==
{{See also|重複組合せ}}
濃度 {{mvar|n}} の有限集合から元をとって作られる濃度 {{mvar|k}} の多重集合の総数は'''多重集合（係）数''' (''multiset coefficient'', ''multiset number'') と呼ばれる。この数はしばしば[[二項係数]]と似せて {{math|(({{su|p=''n''|b=''k''}}))}} と書かれる<ref>例えば{{harvnb|Stanley|1997}}</ref>{{efn|二項係数が初等組合せ論において[[組合せ]] (choose) に関係することのアナロジーで、多重集合係数を "multi&shy;choose" と呼ぶこともある<ref>{{MathWorld|urlname=Mutichoose|title=Multichoose}}</ref>。しかし、二項係数の場合と異なり、多重集合係数に対する組合せ論的な多項式展開定理（いわば「多重集合定理」）は知られていない。またそのため、[[多項定理]]に現れる[[多項係数]]（これは多重集合係数とは直接的には関係ない）と混同の虞は無いであろう。}}

多重集合係数の値は
:<math>\begin{align}\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!}\end{align}</math>
で明示的に与えることができる。ただし、二番目の式は二項係数としての表示である（多重集合を別に定義することを嫌って二項係数としてのみ書く文献も多い）であり、このような多重集合の総数は濃度 {{math|''n'' + ''k'' &minus; 1}} の集合内の {{mvar|k}}-元部分集合の総数に等しい。二項係数との類似性を見るために、上記の式の分子に[[上昇階乗冪]]を用いて {{math|(({{su|p=''n''|b=''k''}})) {{=}} {{fraction|''n''{{exp|{{overline|''k''}}}}|''k''!}}}} と書けば、二項係数が下降階乗冪を用いて {{math|({{su|p=''n''|b=''k''}}) {{=}} {{fraction|''n''{{exp|{{underline|''k''}}}}|''k''!}}}} と書かれることとの対比は明瞭である。

一般化された二項係数を
: <math>{n \choose k}={n(n-1)(n-2)\cdots(n-k+1) \over k!}</math>
において {{mvar|n}} が非負整数とは限らず、負の整数、整数でない実数、実数でない[[複素数]]などとすることによって定義することができる（{{math|''k'' {{=}} 0}} ならば[[空積]]となるからこの係数の値は {{math|1}} であるものと約束する）。この意味において、{{mvar|n}}-元集合から得られる {{mvar|k}}-元部分多重集合の総数は
:<math>\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k}</math>
と書ける。

=== 漸化式 ===
多重集合係数に対して[[漸化式]]
: <math>\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right) \quad (n,k>0)</math>
を初期条件 {{math|(({{su|p=''n''|b=0}})) {{=}} 1 (''n'' &isin; '''N''')}} および {{math|(({{su|p=0|b=''k''}})) {{=}} 0 (''k'' > 0)}} の下で与えることができる。この漸化式は以下のように組合せ論的に解釈することができる。

以下 {{math|{{bracket|''n''}} {{=}} {1, …, ''n''} }}と書く。位数 {{math|0}} の（空）多重集合は常にただ一つであり、また {{math|''n'' {{=}} 0}} のときそれより位数の大きな多重集合は存在しないから、初期条件はこの解釈に適合する。さて {{math|''n'',''k'' &gt; 0}} のとき、集合 {{math|{{bracket|''n''}}}} の元からなる位数 {{mvar|k}} の多重集合が末尾の元 {{mvar|n}} を含むか含まないかに分けて考える。含むならば、{{mvar|n}} の一つはさておいて残りの{{math|''k'' &minus; 1}} 個の元を {{math|[''n'']}} から選んで多重集合を作りそこに {{mvar|n}} を加えればよいから、そのようなものは {{math|(({{su|p=''n''|b=''k''&minus;1|a=c}}))}} 通りある。他方、含まないときは、末尾を除いた集合 {{math|{{bracket|''n''&nbsp;&minus;&nbsp;1}}}} から {{mvar|k}}-元多重集合をつくることになるから、そのようなものは {{math|(({{su|p=''n''&minus;1|b=''k''|a=c}}))}} 通りである。従って {{math|(({{su|p=''n''|b=''k''}})) {{=}} (({{su|p=''n''|b=''k''&minus;1|a=c}})) + (({{su|p=''n''&minus;1|b=''k''|a=c}}))}} が得られた。

== 多項式表現 ==
集合 {{math|{{mset|''x''}}}} を[[単項式]] {{math|''x''}} で表すと、その[[冪集合]] {{math|{{mset|{{mset|}}, {{mset|''x''}}}}}} は[[二項式]] {{math|1 + ''x''}} で表すことができる。集合 {{math|{{mset|''x'', ''y''}}}} を単項式 {{mvar|xy}} に対応させればその冪集合 {{math|{{mset|{{mset|}}, {{mset|''x''}}, {{mset|''y''}}, {{mset|''x'', ''y''}}}}}} は[[多項式]] {{math|(1 + ''x'')(1 + ''y'') {{=}} 1 + ''x'' + ''y'' + ''xy''}} が対応する。同様に多重集合 {{math|{{mset|''x'', ''x''}}}} を単項式 {{math|''x''{{exp|2}}}} に対応させれば、その冪多重集合（部分多重集合全体の成す多重集合）{{math|{{mset|{{mset|}}, {{mset|''x''}}, {{mset|''x''}}, {{mset|''x'', ''x''}}}}}} は多項式 {{math|(1 + ''x''){{exp|2}} {{=}} 1 + 2''x'' + ''x''{{exp|2}}}} に対応する。単項式 {{mvar|x{{exp|n}}}} で表される多重集合の冪多重集合が
: <math>(1+x)^n=\sum_{k=0}^n{n \choose k} x^k</math>
で表されることは、[[二項係数]] {{math|({{su|p=''n''|b=''k''}})}} が {{mvar|n}}-元集合から選んだ {{mvar|k}}-元の組合せの総数を数え上げることになる理由を説明するものである。

集合 {{math|{{mset|''x''}}}} に元をとる有限多重集合全体の成す無限集合 {{math|{{mset|{{mset|}}, {{mset|''x''}}, {{mset|''x'', ''x''}}, {{mset|''x'', ''x'', ''x''}}, …}}}} は[[形式冪級数]] {{math|''S'' {{=}} 1 + ''x'' + ''x''{{exp|2}} + ''x''{{exp|3}} + ⋯ ({{=}} 1 + ''xS'')}} で表され、形式解 {{math|''S'' {{=}} (1 &minus; ''x''){{exp|&minus;1}}}} に多重集合の集合としての意味を与えることができるが、中間表現である {{math|1 &minus; ''x''}} は多重集合の集合として意味を成さない。同様に、単項式 {{mvar|xy}} で表される集合に値を持つ有限多重集合全体の成す無限集合は
: <math>(1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+\dotsb</math>
で表され、単項式 {{math|''x''{{exp|2}}}} で表される多重集合から元をとって作られる有限多重集合全体の成す無限多重集合は {{math|''x'' {{=}} ''y''}} なる特別の場合として {{math|(1 &minus; ''x''){{exp|&minus;2}} {{=}} 1 + 2''x'' + 3''x''{{exp|2}} + ⋯}} で表される。さらに進めて単項式 {{mvar|x{{exp|n}}}} に対応する多重集合に値をとる有限多重集合全体の成す無限多重集合は
: <math>(1-x)^{-n}=\sum_{k=0}^\infty{-n \choose k} (-x)^k</math>
である。これを「多重集合は濃度が負の集合」と形式的に説明することができる。'''負の二項係数''' {{math|({{su|p=&minus;''n''|b=''k''|a=c}})}} は {{mvar|n}}-元集合から元をとって得られる {{mvar|k}}-元多重集合の総数を数えるものである。

== 累積母函数 ==
=== 非負整数の多重集合 ===
[[自然数|非負整数]] {{mvar|n}} を単項式 {{mvar|x{{exp|n}}}} で表すと、同様にして非負整数からなる有限多重集合を多項式 {{math|''f''(''x'')}} で表すことができる。

これには'''累積母函数''' {{math|1=''g''(''t'') = log ''f''(''e''{{exp|''t''}})}} を考えるのが簡便である。
* 多重集合の濃度は {{math|''e''{{exp|''g''(0)}} {{=}} ''f''(1)}}.
* 累積母函数の[[導函数]]は <math>g'(t) = f(e^t)^{-1} f'(e^t) e^t</math>.
** 多重集合の[[平均値]] <math>\mu=g'(0)= f(1)^{-1}f'(1)</math>.
** 多重集合の[[分散 (確率論)|分散]] <math>\sigma^2=g''(0)</math>.
例えば非負整数の多重集合 {{math|{{mset|2, 2, 2, 3, 5}}}} に対応する多項式は {{math|''f''(''x'') {{=}} 3''x''{{exp|2}} + ''x''{{exp|3}} + ''x''{{exp|5}}}} であり、その累積母函数 {{math|''g''(''t'') {{=}} log(3''e''{{exp|2''t''}} + ''e''{{exp|3''t''}} + ''e''{{exp|5''t''}})}}, 濃度 {{math|3 + 1 + 1 {{=}} 5}}, 導函数 {{math|''g{{'}}''(''t'') {{=}} (3''e''{{exp|2''t''}} + ''e''{{exp|3''t''}} + ''e''{{exp|5''t''}}){{exp|&minus;1}}(6''e''{{exp|2''t''}} + 3''e''{{exp|3''t''}} + 5''e''{{exp|5''t''}})}}, 平均値 {{math|''μ'' {{=}} (3 + 1 + 1){{exp|&minus;1}}(6 + 3 + 5) {{=}} 2.8}} などと計算できる。

ここに現れる数 {{math|(&mu;,&sigma;{{exp|2}}, …) {{=}} (''g{{'}}''(0), ''g"''(0), …)}} は各次数の[[キュムラント|累積率]]と呼ばれる。

非負整数全体の成す無限集合 {{math|{{mset|0, 1, 2, …}}}} は[[形式冪級数]] {{math|1 + ''x'' + ''x''{{exp|2}} + ⋯ {{=}} (1 &minus; ''x''){{exp|&minus;1}}}} で表され、平均値や標準偏差は定義されないが、累積母函数 {{math|''g''(''t'') {{=}} &minus;log(1 &minus; ''e''{{exp|''t''}})}} は持つ。この累積母函数の導函数は {{math|''g{{'}}''(''t'') {{=}} (''e''{{exp|&minus;''t''}} &minus; 1){{exp|&minus;1}}}} である。

=== 実数の多重集合 ===
実数からなる有限多重集合 {{math|''A'' {{=}} {{mset|''A''{{ind|''i''}}}}}} は累積母函数
: <math>g_A(t) = \log \left(\sum_i e^{t A_i}\right)</math>
で表される。この表現は一意である（つまり、相異なる多重集合は相異なる累積母函数を持つ）。平均 {{mvar|μ}}, 標準偏差 {{mvar|σ}} を持つ {{mvar|n}} 個の実数からなる多重集合の累積母函数は {{math|''g''(''t'') {{=}} log ''n'' + ''μt'' + 2{{exp|&minus;1}}(''σt''){{exp|2}} + ⋯}} で与えられ、その導函数は {{math|''g{{'}}''(''t'') {{=}} &mu; + &sigma;{{exp|2}}''t'' + ⋯}}となる。

ただ一つの実数 {{mvar|k}} からなる集合 {{math|{''k''&#125;}} の累積母函数は {{math|''g''(''t'') {{=}} ''kt''}} であり、その導函数 {{math|''g{{'}}''(''t'') {{=}} ''k''}} はその数自身に一致する。この意味において、「実数からなる多重集合の累積母函数の導函数」は実数の概念を一般化するものである。

一つの実数 {{mvar|k}} のみを含む {{mvar|n}} 元の定値多重集合 {{math|{{mset|''k'', ''k'', ''k'', ''k'', …, ''k''}}}} は {{math|''g''(''t'') {{=}} log ''n'' + ''kt''}} が対応し、導函数は {{mvar|n}} に無関係に {{math|''g{{'}}''(''t'') {{=}} ''k''}} である。

=== 性質 ===
実数からなる二つの多重集合の元ごとの和の成す多重集合の累積母函数は、各々の多重集合の累積母函数の和に等しい:
: <math>g_{A+B}(t) = g_A(t) + g_B(t).</math>

元ごとの積の累積母函数
: <math>g_{A\cdot B}(t) = \log \left(\sum_i\sum_j e^{t A_i B_j}\right)</math>
を計算する一般式は存在しないが、その特別の場合として定数倍は
: <math>g_{k\cdot A}(t) = g_A(kt)</math>
となる。多重集合 {{math|1=2⋅''A'' {{=}} {{mset|2''A{{ind|i}}''}}}} は多重集合 {{math|1=2 &times; ''A'' {{=}} ''A'' + ''A'' {{=}} {{mset|''A{{ind|i}}'' + ''A{{ind|j}}''}}}} とは異なることに注意せよ。例えば、{{math|1=2 &sdot;{{mset|1,&thinsp;&minus;1}} {{=}} {{mset|2,&thinsp;&minus;2}}}} に対し、{{math|1=2 &times; {{mset|1, &minus;1}} {{=}} {{mset|1, &minus;1}} + {{mset|1, &minus;1}} {{=}} {{mset|1 + 1, 1 &minus; 1, &minus;1 + 1, &minus;1 &minus;1}} {{=}} {{mset|2, 0, 0, &minus;2}}}} である。{{math|''k'' &times; ''A''}} の累積母函数は
: <math>g_{k\times A}(t) = k\,g_{A}(t)</math>
となる。標準[[正規分布]]は実数からなる巨大な多重集合の極限
: <math>\lim_{k \rarr \infty}k^{-1}(k^2\times \{1,-1\})</math>
と看做せる。この極限は実数の多重集合として意味を成すものではないが、極限をとる多重集合の累積母函数の導函数には意味を持たせることができて、その極限は
:<math>
\begin{align}
\lim_{k \rarr \infty} g'_{k^{-1} (k^2\times \{1,-1\})}(t) & = \lim_{k \rarr \infty} \frac{d}{dt}(k^2 \log(e^{+t k^{-1}}+e^{-t k^{-1}})) \\
& = \lim_{k \rarr \infty} \frac{d}{dt}(k^2 \log 2+2^{-1} t^2+\dotsb) = t.
\end{align}
</math>
と矛盾なく定義される。定数項 {{math|''k''{{exp|2}}log(2)}} は微分で消え、省略した後続の項は極限をとれば消える。ゆえに平均 {{math|0}}, 標準偏差 {{math|1}} を持つ標準正規分布に対して、その累積母函数の導函数は {{math|''g{{'}}''(''t'') {{=}} ''t''}} となる。平均 {{mvar|μ}}, 標準偏差 {{mvar|σ}} の正規分布の累積母函数の導函数は {{math|''g{{'}}''(''t'') {{=}} &mu; + &sigma;{{exp|2}}''t''}} で与えられる。

== 応用 ==
多重集合は様々な応用を持つ<ref name="Singh2007" />。多重集合はそのより高度な厳密さが希求されたことの結果として、組合せ論における主要な構造となり、現代組合せ論は集合ではなく多重集合に対する理論として発展した<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|publisher=Clarendon Press|location=Oxford}}</ref><ref name="Stanley1997">{{cite book|last=Stanley|first=Richard P.|authorlink=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>。多重集合はデータベースにおいて重要な道具となった<ref name="GrumbachMilo1996">{{cite journal|last=Grumbach|first=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}}</ref><ref name="LibkinWong1994">{{cite book|last=Libkin|first=L.|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|last=Libkin|first=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}}</ref>。例えば多重集合はデータベースシステムにおける重要な関係としてしばしば用いられる。多重集合は計算機科学においても重要な役割を務める<ref name="Knuth1998" />。

他にも応用はある。例えば、{{仮リンク|リチャード・ラド|en|Richard Rado}}は多重集合を集合族の性質を調べる仕掛けとして用いた。ラドは「集合の概念はその各元がいくつ現れるかを考慮しないものだが、そうは言ってもこの手の情報はたびたび重要になる。多項式 f(x) の根全体の成す集合とか線型作用素のスペクトルとかを考えるだけでもそれは分かるだろう。」と書いている<ref name="Blizard1991" />。

== 一般化 ==
重複度関数の値域を変更することにより、重複度を負の値も含めた整数値や実数値などに拡張して考えることができる。拡張された意味での多重集合に関する多重集合演算は、大抵の場合には非負整数値の場合の重複度関数の算術がそのまま成立するものとして演算後の重複度関数を定め、それによって特徴付けられる多重集合として定義される。

たとえば、[[ファジィ集合]]（曖昧集合、確率的集合）は、区間 {{closed-closed|0, 1}} に値をとる重複度函数を備えた多重集合と考えることもできる。この場合、ファジィ集合の帰属率函数（メンバシップ函数）が重複度函数に相当する。ただし、ある集合 ''X'' を全体集合として固定して、その部分集合となっているようなものだけにファジィ集合だけを考えるときは、（確率的な解釈を与えるため）''X'' の任意の[[集合の分割|分割]]
: <math>X = \sum_{\lambda\in\Lambda}A_\lambda</math>
に対して、
: <math>(\mu_X =) \sum_{\lambda\in\Lambda}\mu_{A_\lambda} \equiv 1</math>
となるように帰属率函数に制限を加えて考えることも多い。

各種問題の研究と解法に応じて様々に異なる多重集合の一般化が存在する:
* 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|pages=23–37}}</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>
* 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|pages=77–97}}</ref><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=1|pages=346–368}}</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|pages=64–74}}</ref>
* where multiplicity is any real-valued step function<ref name="Miyamoto2001">{{cite journal|last=Miyamoto|first=S.|year=2001|title=Fuzzy Multisets and their Generalizations|journal=Multiset Processing|volume=2235|pages=225–235}}</ref>
* Soft multisets<ref name="Alkhazaleh2011">{{cite journal|last=Alkhazaleh|first=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|last=Alkhazaleh|first=S.|last2=Salleh|first2=A. R.|year=2012|title=Fuzzy Soft Multiset Theory|journal=Abstract and Applied Analysis}}</ref>
* Named set (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>

== 注釈 ==
{{notelist}}

== 出典と参考文献 ==
{{reflist}}

== 関連項目 ==
* [[集合]]
* [[族 (数学)]]

== 外部リンク ==
* {{MathWorld|urlname=Multiset|title=Multiset}}
* {{nlab|urlname=multiset|title=multiset}}
* {{PlanetMath|urlname=Multiset|title=multiset}}
* {{ProofWiki|urlname=Definition:Multiset|title=Definition:Multiset}}
* {{SpringerEOM|urlname=Multiset|title=Multiset}}

{{DEFAULTSORT:たしゆうしゆうこう}}
[[Category:集合の基本概念]]
[[Category:数学的構造]]
[[Category:数学の表記法]]
[[Category:数学に関する記事]]