多重集合

数学における多重集合（たじゅうしゅうごう、multiset）あるいはバッグ（; かばん）は、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという重複度を考え合わせた集合概念である。非順序対、非順序組 ともいう。
クヌースによれば、1970年代に最初に多重集合 (multiset) という言葉を提案したのは、オランダ人数学者のニコラース・ホーバート・ド・ブラン (IPA: ) であるという。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表されたリヒャルト・デデキントの有名な論文 "Was sind und was sollen die Zahlen?" （「数とは何か、何であるべきか？」）において、実質的に多重集合の概念が用いられている。
導入.
集合と多重集合の峻別のために、集合のように 波括弧 で囲む代わりに、二重波括弧 (formula_1) や角括弧 あるいは中抜き波括弧 (formula_2). などで囲むこともある。
集合と多重集合と順序対（あるいは組）は例えば次のような点で差異が認められる。 として、
建前上は基本的に集合のみを扱い多重集合を扱わないというような（しばしば初等的な）文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 に対して、 とおき、その根の集合
を考えると、この集合の濃度（根の個数）は のとき だが、 のときは退化して になってしまう。これを のときは 2 つの根がたまたま重なったもの（重根）と考えて重複度 を与えることにより、根は のときも含めて常に 個であると考えることができる。この例は一般に、代数方程式論の基本定理の一つの表現「-次方程式は必ず重複度まで込めてちょうど 個の根を持つ」として述べることができる。同様の例として、複素解析函数に対する零点や極の位数（重複度）あるいは曲線の接触の位数（接触度）なども挙げられる（重複度 (数学)の項を参照）。
またたとえば、自然数 の素因数分解
（実際には ごとに右辺に現れる素因子は有限個、つまり殆どの が となる実質有限積である）は、自然数 を素数全体の成す集合 を台とする多重集合 として表示する方法を与えるものと解釈することができる（素因数分解が積の順番の違いを除いて一意であるということが多重集合の性質に対応する）。置換の巡回置換分解あるいは巡回置換型も同様である。
同様に、自然数 の分割を考えることは、分割に現れる各整数 の個数を重複度 ととれば、自然数全体の成す集合 を台とする多重集合 であって、重複度関数 が次の二条件
を満たすようなものを一つ定めることに他ならない。ゆえに、分割数は、各自然数 に対してこのような重複度関数 のとり方が 通りあることを示している。
歴史.
Wayne Blizard は、“in ancient times, the number n was often represented by a collection of n strokes, tally marks, or units.”（「古代、数 は 本の棒、画線、単位の集まりとして表されていた」）なる論法を以って、多重集合の起源はまさに数の起源にまで遡れるとする。これら、あるいは同様の対象の集まりは、棒・画線・単位が各々区別できないもの (indistinguishable) と考えて多重集合になる。これは多重集合の概念が数学に取り入れられる以前から人々に暗に用いられていたことを示している。
そのような理由により多重集合は、この構造が必要とされるたびに何度も再発見され、異なる名称を以って文献に現れることとなる。例えば、 はこれを bag と呼んでおり、その語は の影響によるものである。多重集合は他にも aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set) などと呼ばれている。
ただ多重集合の概念が古代より暗に用いられていたと言っても、それらが明示的に調べられるようになるのはずっと後になってからのことである。多重集合の最初の研究として知られるのは1150年ごろ、インドの数学者バースカラ2世による、多重集合の順列に関するものである。 (1498–1576) の業績には多重集合の概念に関する別の先駆的言及が含まれる。 は一つの元のみ重複する場合の多重集合の順列の数を求めた。は1675年に多重集合の順列に関する一般法則を著した。 はこの法則をより詳細に説明している
明確な形で多重集合が現れるのはリヒャルト・デーデキントの手によるが、数学者が多重集合を定式化して明確な数学的対象としてその研究を始めたのは20世紀に入ってからである。
定義.
 を全体集合とし、その任意の部分集合 と から非負整数全体の集合 への写像 で、 すなわち に属さない元 に対しては恒等的に を満たすものの組 を、 を台集合とする多重集合といい、台集合 の各元 に対してその による像 を の重複度という。紛れのおそれの無い場合、多重集合 をその台集合 で表す。
非負整数値の重複度を持つ多重集合 は、項の値に重複のある列の集合として
のようにも記される。
たとえば、二つの文字 について を 2 個、 を 1 個含むような多重集合を考えると、この台集合は であり、各元の重複度 を合わせた が、同じ多重集合を台集合とその上の重複度という構造によって表したものとなる。またこれは簡単に とも記す。
新たに添字を導入して
などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような族 に対して、同じ元からなる多重集合を で表すことがある。
多重集合の構成.
文字集合 を固定したとき、 上の有限多重集合は、 上の文字列で文字の順番を自由に取り替えたものと同一視できるから、 上の有限文字列全体が文字列の連接を演算として空文字列を単位元とする の生成する自由モノイドとなるのと並行して、 の生成する自由可換モノイドと 上の有限多重集合の全体とが同一視される。すなわち、 の元からなる有限多重集合は、 上の自由モノイドのアーベル化の元である。
長さ の有限列（-組）に -次対称群を成分の（番号の）入れ替えとして作用させるとき、この作用で割って得られる同値類（軌道）あるいはその任意の代表元を（重複度まで込めた濃度が の）多重集合と見做すことができる。
多重集合の演算と重複度函数.
多重集合 に対し、台集合 の部分集合 を台集合とする多重集合 で の各元 の重複度について
が成り立つとき、多重集合 は多重集合 の部分多重集合であるといい、 で表す。
また、多重集合に対する和、差、積、対称差などの概念が、通常の集合に関する和、差、積、対称差などに従って定義される。例えば、多重集合 の和 は包含関係 を順序とする上限、積 は に関する下限である。多重集合の演算は台集合に対しては通常の集合演算として作用するが、その元の重複度については多少の注意を要する。
!
formula_10
! 交叉
! 合併
と矛盾なく定義される。定数項 は微分で消え、省略した後続の項は極限をとれば消える。ゆえに平均 , 標準偏差 を持つ標準正規分布に対して、その累積母函数の導函数は となる。平均 , 標準偏差 の正規分布の累積母函数の導函数は で与えられる。
応用.
多重集合は様々な応用を持つ。多重集合はそのより高度な厳密さが希求されたことの結果として、組合せ論における主要な構造となり、現代組合せ論は集合ではなく多重集合に対する理論として発展した。多重集合はデータベースにおいて重要な道具となった。例えば多重集合はデータベースシステムにおける重要な関係としてしばしば用いられる。多重集合は計算機科学においても重要な役割を務める。
他にも応用はある。例えば、は多重集合を集合族の性質を調べる仕掛けとして用いた。ラドは「集合の概念はその各元がいくつ現れるかを考慮しないものだが、そうは言ってもこの手の情報はたびたび重要になる。多項式 f(x) の根全体の成す集合とか線型作用素のスペクトルとかを考えるだけでもそれは分かるだろう。」と書いている。
一般化.
重複度関数の値域を変更することにより、重複度を負の値も含めた整数値や実数値などに拡張して考えることができる。拡張された意味での多重集合に関する多重集合演算は、大抵の場合には非負整数値の場合の重複度関数の算術がそのまま成立するものとして演算後の重複度関数を定め、それによって特徴付けられる多重集合として定義される。
たとえば、ファジィ集合（曖昧集合、確率的集合）は、区間 に値をとる重複度函数を備えた多重集合と考えることもできる。この場合、ファジィ集合の帰属率函数（メンバシップ函数）が重複度函数に相当する。ただし、ある集合 "X" を全体集合として固定して、その部分集合となっているようなものだけにファジィ集合だけを考えるときは、（確率的な解釈を与えるため）"X" の任意の分割
に対して、
となるように帰属率函数に制限を加えて考えることも多い。
各種問題の研究と解法に応じて様々に異なる多重集合の一般化が存在する: