マルチセット

数学において、マルチセット（またはバッグ、mset ）は、セットの概念を修正したもので、セットとは異なり、各要素に対して複数のインスタンスを許容します。 ^{[ 1 ]}各要素に対して与えられるインスタンスの数は、マルチセットにおけるその要素の多重度と呼ばれます。結果として、要素aとbのみを含むものの、要素の多重度が異なるマルチセットが無限に存在します。

• 集合{ a , b }は要素aとbのみを含み、 { a , b } を多重集合とみなした場合、それぞれの要素の重複度は 1 です。
• 多重集合{ a , a , b }において、要素aの多重度は 2、要素b の多重度は 1 である。
• 多重集合{ a , a , a , b , b , b }において、aとb はどちらも重複度 3 を持ちます。

これらのオブジェクトは、すべて同じ要素から構成されているため、同じ集合ではあるものの、多重集合として見るとすべて異なります。集合と同様に、タプルとは対照的に、多重集合を区別する際には要素の列挙順序は重要ではないため、{ a , a , b }と{ a , b , a }は同じ多重集合を表します。集合と多重集合を区別するために、角括弧を含む表記法が使用されることがあります。多重集合{ a , a , b }は[ a , a , b ]と表記できます。^{[ 2 ]}

多重集合の濃度、つまり「サイズ」は、そのすべての要素の重複度の合計です。たとえば、多重集合{ a , a , b , b , b , c }では、要素a、b、cの重複度はそれぞれ 2、3、1 なので、この多重集合の濃度は 6 です。

ドナルド・クヌースによれば、ニコラース・ゴバート・デ・ブルインが1970年代に「マルチセット」という言葉を造語した。^{[ 3 ] : 694}しかし、マルチセットの概念は「マルチセット」という言葉が造語される何世紀も前から存在していた。クヌース自身は、マルチセットの最初の研究はインドの数学者バースカラチャリヤによるもので、彼は1150年頃にマルチセットの順列について記述したとしている。この概念には、リスト、バンチ、バッグ、ヒープ、サンプル、重み付きセット、コレクション、スイートなど、他の名称も提案または使用されてきた。^{[ 3 ] : 694}

ウェイン・ブリザードは、多重集合を数の起源まで遡って調べ、「古代では、数nはしばしばn本の線、正の字、または単位の集合で表されていた」と主張した。^{[ 4 ]}線、正の字、または単位は区別できないと考えられているため、これらや同様のオブジェクトの集合は多重集合とみなすことができる。これは、数学が出現する前から人々が暗黙のうちに多重集合を使用していたことを示している。

この構造に対する実際的なニーズにより、マルチセットは何度か再発見され、文献では異なる名前で登場しています。^{[ 5 ] : 323}例えば、QA4 のような初期のAI言語では重要であり、 Peter Deutschに帰属する用語であるbagと呼ばれていました。^{[ 6 ]}マルチセットは、集約、ヒープ、バンチ、サンプル、重み付きセット、出現セット、ファイアセット (有限繰り返し要素セット) とも呼ばれています。^{[ 5 ] : 320 [ 7 ]}

多重集合は古代から暗黙のうちに使用されていましたが、明示的な研究ははるか後になってから行われました。多重集合に関する最初の既知の研究は、1150 年頃のインドの数学者Bhāskarāchāryaによるもので、彼は多重集合の順列について記述しました。 ^{[ 3 ] : 694} Marius Nizolius (1498–1576)の著作には、多重集合の概念に関する別の初期の言及が含まれています。^{[ 8 ]} Athanasius Kircher は、1 つの要素を繰り返すことができる場合の多重集合の順列の数を見つけました。^{[ 9 ]} Jean Prestet は1675 年に多重集合の順列に関する一般的な規則を発表しました。^{[ 10 ]} John Wallis は1685 年にこの規則をより詳細に説明しました。^{[ 11 ]}

多重集合はリヒャルト・デデキントの著作に明示的に登場した。^{[ 12 ] [ 13 ]}

他の数学者たちは多重集合を形式化し、20世紀にそれらを正確な数学的構造として研究し始めた。例えば、ハスラー・ホイットニー（1933）は一般化集合（特性関数 が正、負、またはゼロの任意の整数値をとることができる「集合」）を記述した。 ^{[ 5 ]： 326 [ 14 ]： 405} モンロー（1987）は多重集合とその射のカテゴリーMulを調査し、多重集合を「同じ種類の」要素間の同値関係を持つ集合として定義し、多重集合間の射を種類を尊重する関数として定義した。彼はまた、多重集合から自然数への関数f ( x ) である多重数を導入し、多重集合内の要素xの多重度を与えた。モンローは、多重集合と多重数の概念はどちらも有用であるにもかかわらず、しばしば区別なく混同されていると主張した。^{[ 5 ]： 327–328 [ 15 ]}

最も単純で自然な例の1つは、自然数nの素因数の多重集合です。ここで、基となる要素の集合は、 nの素因数の集合です。たとえば、数120 の素因数分解は次のようになります。$${\displaystyle 120=2^{3}3^{1}5^{1},}$$ これにより、多重集合{2, 2, 2, 3, 5}が得られます。

関連する例として、代数方程式の解の多重集合が挙げられます。例えば、二次方程式には2つの解があります。しかし、場合によっては、それらは両方とも同じ数になります。したがって、方程式の解の多重集合は{3, 5}になる場合もあれば、 {4, 4}になる場合もあります。後者の場合、多重度2の解を持ちます。より一般的には、代数学の基本定理は、次数dの多項式方程式の複素解は常に濃度dの多重集合を形成すると主張しています。

上記の特殊なケースは行列の固有値であり、その重複度は通常、特性多項式の根としての重複度として定義されます。しかし、固有値には他に2つの重複度が自然に定義されます。最小多項式の根としての重複度と、幾何重複度です。幾何重複度は、 A − λI ( λは行列Aの固有値)の核の次元として定義されます。これら3つの重複度は、すべて異なる可能性のある3つの固有値の多重集合を定義します。Aを、単一の固有値を持つジョルダン標準形のn × n行列とします。その重複度はnであり、最小多項式の根としての重複度は最大のジョルダンブロックのサイズであり、幾何重複度はジョルダンブロックの数です。

多重集合は、形式的には順序対( U , m )として定義され、ここでUは宇宙または基礎集合と呼ばれる集合であり、${\displaystyle m\colon U\to \mathbb {N} }$はUから非負整数への関数である。^{[ 7 ]}値⁠${\displaystyle m(a)}$要素の場合${\displaystyle a\in U}$⁠は、⁠の多重度と呼ばれます${\displaystyle a}$マルチセット内で、の出現回数として解釈される。${\displaystyle a}$マルチセット内。

多重集合のサポート、ルート、またはキャリアは、のサブセットです。${\displaystyle U}$要素によって形成された${\displaystyle a\in U}$⁠そのため⁠${\displaystyle m(a)>0}$⁠ . ^{[ 7 ]}有限マルチセットとは、有限のサポートを持つマルチセットのことです。ほとんどの著者は、マルチセットを有限マルチセットとして定義しています。この記事でも、特に断りのない限り、すべてのマルチセットは有限マルチセットです。

一部の著者^{[ 16 ]}は、多重集合を次の追加制約で定義している。${\displaystyle m(a)>0}$⁠全ての⁠${\displaystyle a}$⁠、あるいは同等に、サポートは基礎となる集合と等しい。無限多重度を持つ多重集合も研究されているが^{[ 17 ]}、本稿では考慮しない。一部の著者は、有限インデックス集合の観点から多重集合を定義している。${\displaystyle I}$⁠そして関数⁠${\displaystyle f\colon I\rightarrow U}$要素の多重度${\displaystyle a\in U}$⁠は⁠${\displaystyle |f^{-1}(a)|}$⁠、 の要素の数⁠${\displaystyle I}$⁠マッピングされる⁠${\displaystyle a}$⁠による⁠${\displaystyle f}$⁠ .

多重集合は、一部の要素が重複する集合として表現できます。たとえば、サポートを持つ多重集合は⁠${\displaystyle \{a,b\}}$⁠および多重度関数は次のようになる。${\displaystyle m(a)=2,\;m(b)=1}$は{ a , a , b }と表すことができます。多重度が高い場合のより簡潔な表記法は次のとおりです。${\displaystyle \{(a,2),(b,1)\}}$同じマルチセットの場合。

もし${\displaystyle A=\{a_{1},\ldots ,a_{n}\},}$サポートを含むマルチセット${\displaystyle A}$ はしばしば次のように表現されます 。$${\displaystyle a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},}$$不定数 の計算規則を適用できる。つまり、指数1と指数0の因数は削除でき、多重集合は因数の順序に依存しない。これにより、表記を無限基底集合に拡張できる。 $$\displaystyle \prod _{a\in U}a^{m(a)}.}$$ 表記法の利点は、正確なサポートを知らなくても表記法を使用できることです。たとえば、自然数の素因数${\displaystyle n}$多重集合を形成 する$${\displaystyle n=\prod _{p\;{\text{prime}}}p^{m(p)}=2^{m(2)}3^{m(3)}5^{m(5)}\cdots .}$$

多重集合の要素は一般に固定された集合U (宇宙とも呼ばれ、多くの場合自然数の集合)から取られます。与えられた多重集合に属さないUの要素は、その多重集合において重複度 0 を持つと言われます。これは、多重集合の重複度関数を、 Uから集合への関数に拡張したものです。${\displaystyle \mathbb {N} }$非負整数の集合。これにより、これらの関数と、要素がUに含まれる多重集合との間に1 対 1 の対応関係が定義されます。

この拡張された多重度関数は、一般に単に多重度関数と呼ばれ、要素を含む全体集合が固定されている場合に多重集合を定義するのに十分である。この多重度関数は部分集合の指示関数の一般化であり、それといくつかの性質を共有している。

マルチセットのサポート${\displaystyle A}$宇宙Uは多重集合の基礎となる集合であり、^{[ 7 ]}は次のように表される。${\displaystyle A^{*}}$^{[ 7 ]} または${\displaystyle \operatorname {Supp} (A)}$多重度関数を使用する${\displaystyle m}$それは、 $${\displaystyle \operatorname {Supp} (A):=\{x\in U\mid m_{A}(x)>0\}.}$$

多重集合は、そのサポートが有限である場合、または同等に、その濃度が有限である場合に 有限である。$${\displaystyle |A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)}$$ は有限である。空の多重集合は、サポート（基底集合）が空である唯一の多重集合であり、したがって濃度は0である。

集合の通常の演算は、部分集合の指示関数を用いるのと同様に、多重度関数を用いることで多重集合にも拡張できる。以下では、AとBは与えられた全体集合Uにおける多重集合であり、多重度関数はそれぞれ以下の通りである。${\displaystyle m_{A}}$そして${\displaystyle m_{B}.}$

• 包含関係: AがBに含まれる場合、A ⊆ Bと表記されます。$${\displaystyle m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.}$$
• 和集合: AとBの和集合(文脈によっては最大公倍数または最小公倍数と呼ばれる)は多重度関数^{[ 13 ]}を持つ多重集合Cである。$${\displaystyle m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.}$$
• 交差：AとBの交差（文脈によっては最小値または最大公約数と呼ばれる）は多重度関数を持つ多重集合Cである。$${\displaystyle m_{C}(x)=\min(m_{A}(x),m_{B}(x))\quad \forall x\in U.}$$
• 合計：AとBの合計は多重度関数を持つ多重集合Cである$${\displaystyle m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.}$$これは、集合の非交和の一般化と見なすことができる。与えられた宇宙内の有限多重集合上に可換モノイド構造を定義する。このモノイドは、宇宙を基底とする自由可換モノイドである。
• 差：AとBの差は多重度関数を持つ多重集合Cである$${\displaystyle m_{C}(x)=\max(m_{A}(x)-m_{B}(x),0)\quad \forall x\in U.}$$

2つの多重集合は、それらの支持集合が互いに素な集合である場合に、互いに素であると言います。これは、それらの共通部分が空の多重集合である、あるいはそれらの和がそれらの和集合に等しい、と言うことと同義です。

有限多重集合には（集合の場合と同様に）包含排除原理があり、有限多重集合の有限和は2つの多重集合の和の差であると規定しています。最初の和では、与えられた多重集合の奇数個のすべての可能な交差を考慮し、2番目の和では、与えられた多重集合の偶数個のすべての可能な交差を考慮します。

集合の有限部分集合${\displaystyle U}$は、基底集合を持つ多重集合です。${\displaystyle U}$⁠、したがって⁠${\displaystyle m(a)\leq 1}$⁠全ての⁠${\displaystyle a\in U}$⁠ .

有限集合nから要素を取り出してkの要素を持つ多重集合の数は、多重集合係数または多重集合数と呼ばれることがあります。この数は、一部の著者によって次のように表記されます。${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)}$、二項係数の表記に似せることを意図した表記法。例えば (Stanley, 1997) で使用されており、 「 n choose k」に似せて「 n multichoose k 」と発音されることもある。${\displaystyle {\tbinom {n}{k}}.}$二項係数を含む二項分布と同様に、多重集合係数が現れる負の二項分布が存在する。多重集合係数は、多項定理に現れる多項係数と混同してはならない。

多重集合係数の値は、明示的に次のように表すことができます。 $${\displaystyle \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!},}$$ ここで、2番目の式は二項係数として表されます。^{[ a ]}実際、多くの著者は別々の表記を避け、単に二項係数と表記しています。したがって、このような多重集合の数は、要素数n + k − 1の集合の要素数kの部分集合の数と同じです。二項係数との類似性は、上記の式の分子を上昇階乗として表記することで強調できます。$${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},}$$ 二項係数の式を、下降階乗を用いて表現するには： $${\displaystyle {n \choose k}={n^{\underline {k}} \over k!}.}$$

例えば、${\displaystyle \textstyle 4=\left(\!{\binom {2}{3}}\!\right)}$要素数が 3 の多重集合で、要素は 2 要素集合{1, 2}から取られ、具体的には{1, 1, 1}、 {1, 1, 2}、 {1, 2, 2}、および{2, 2, 2}である。また、${\displaystyle \textstyle 4={\binom {4}{3}}}$ 4つの要素からなる集合{1, 2, 3, 4}の要素数 3 の部分集合、すなわち{1, 2, 3}、 {1, 2, 4}、 {1, 3, 4}、および{2, 3, 4}。

上述の多重集合係数と二項係数の等価性を証明する簡単な方法の一つは、多重集合を次のように表現することです。まず、 { a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d } ( 6つの a s、2 つのb s、3 つのc s、7 つのd s )を次の形式で表す多重集合の表記法を考えてみましょう。

 • • • • • • | • • | • • • • • • • • • •​                    

これは、要素数n = 4の集合の要素から構成される、要素数k = 18の多重集合です。この表記法で使用される点と縦線を含む文字の数は18 + 4 − 1です。縦線の数は 4 − 1 です。要素数 18 の多重集合の数は、 18 + 4 − 1 個の文字の中に4 − 1本の縦線を配置する方法の数であり、したがって、要素数18 + 4 − 1 の集合の要素数 4 − 1 の部分集合の数です。同様に、18 個の点を18 + 4 − 1個の文字の中に配置する方法の数であり、これは要素数18 + 4 − 1の集合の要素数 18 の部分集合の数です。これは $${\displaystyle {4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,}$$ したがって、多重集合係数の値とその同値関係は次のようになります。 $${\displaystyle {\begin{aligned}\left(\!\!{4 \choose 18}\!\!\right)&={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3},\\[1ex]&={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},\\[1ex]&={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;1\cdot 2\cdot 3\quad } }},\\[1ex]&={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.\end{aligned}}}$$

二項係数と多重集合係数の関係から、n個の要素を持つ集合におけるk個の要素を持つ多重集合の数は次のように表せる。 $${\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.}$$ さらに、 $${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).}$$

マルチセットにはさまざまな応用があります。^{[ 7 ]}組み合わせ論では基本的なものになりつつあります。^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]}マルチセットは、同義語バッグがよく使われる関係データベースの理論で重要なツールになっています。^{[ 22 ] [ 23 ] [ 24 ]}例えば、マルチセットはデータベースシステムで関係を実装するためによく使用されます。特に、テーブル（主キーなし）は、複数の同一のレコードを持つことができるため、マルチセットとして機能します。同様に、SQLはマルチセットに対して操作を行い、同一のレコードを返します。たとえば、「SELECT name FROM Student」を考えてみましょう。student テーブルに名前が「Sara」のレコードが複数ある場合、それらすべてが表示されます。つまり、SQL クエリの結果はマルチセットです。結果がセットだった場合、結果セット内の重複レコードは削除されます。マルチセットのもう 1 つの応用は、マルチグラフのモデリングです。多重グラフでは、任意の2つの頂点間に複数の辺が存在する可能性があります。そのため、辺を指定するエンティティは集合ではなく多重集合です。

他にも応用例がある。例えば、リチャード・ラドは多重集合を集合族の性質を研究するための手段として用いた。彼は次のように述べている。「集合の概念は、その要素の複数回の出現を考慮していないが、まさにこの種の情報こそがしばしば重要なのである。多項式f ( x ) の根の集合や線形作用素のスペクトルを考えればよい。」^{[ 5 ] : 328-329}

多重集合のさまざまな一般化が導入され、研究され、問題解決に応用されてきた。

• 符号付き多重集合（要素の多重度が任意の整数となる）^{[ 25 ]}
• 実数値多重集合（要素の多重度が任意の実数となる）^{[ 26 ]}
• ファジーマルチセット^{[ 27 ]}
• ラフマルチセット^{[ 28 ]}
• ハイブリッドセット^{[ 29 ]}
• 多重度が任意の実数値階段関数である多重集合^{[ 30 ]}
• ソフトマルチセット^{[ 31 ]}
• ソフトファジーマルチセット^{[ 32 ]}
• 名前付き集合（集合のすべての一般化の統一）^{[ 33 ] [ 34 ] [ 35 ] [ 36 ]}

• 多重度類似物としての頻度（統計）
• 準集合
• 集合論
• 単語の袋モデル
• Wikiversityにある多重集合の分割に関する学習教材