多重集合

数学における多重集合（たじゅうしゅうごう、multiset）あるいはバッグ（bag; かばん）は、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかという重複度を考え合わせた集合概念である。非順序対、非順序組 (unordered tuple) ともいう。

クヌースによれば、1970年代に最初に多重集合 (multiset) という言葉を提案したのは、オランダ人数学者のニコラース・ホーバート・ド・ブラン (IPA: [dɪ bʁœyn]) であるという。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表されたリヒャルト・デデキントの有名な論文 "Was sind und was sollen die Zahlen?" （「数とは何か、何であるべきか？」）において、実質的に多重集合の概念が用いられている。

導入

集合と多重集合の峻別のために、集合のように 波括弧 {,}で囲む代わりに、二重波括弧 テンプレート:Braces ([math]\scriptstyle\{\!\!\{,\}\!\!\}[/math]) や角括弧 テンプレート:Bracket あるいは中抜き波括弧 ⦃,⦄([math]\scriptstyle\{\!\vert,\vert\!\}[/math]). などで囲むこともある。

集合と多重集合と順序対（あるいは組）は例えば次のような点で差異が認められる。a ≠ b として、

• 順序対: (a, a, b) と (a, b, a) とは順序三つ組として異なる（各成分の現れる順番を変えてはいけない）。これらはもちろん (a, b) とも異なる。
• 多重集合: ⦃a, a, b⦄ と ⦃a, b, a⦄ は多重集合として一致する（元の現れる順番は関係無い）が、⦃a, a, b⦄ と ⦃a, b⦄ は多重集合として異なる（重複度が異なるなら多重集合としては異なる）。
• 集合: {a, a, b} と {a, b, a} と {a, b} はいずれも同じ集合である（元の現れる順番は関係なく、また同じ元は何度現われてもひとつあることと同じ）。

建前上は基本的に集合のみを扱い多重集合を扱わないというような（しばしば初等的な）文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 x² + ax + b に対して、Δ := a² − 4b とおき、その根の集合

[math]\lbrace x\mid x^2 + ax + b = 0\rbrace[/math]

を考えると、この集合の濃度（根の個数）は Δ ≠ 0 のとき 2 だが、Δ = 0 のときは退化して 1 になってしまう。これを Δ = 0 のときは 2 つの根がたまたま重なったもの（重根）と考えて重複度 2 を与えることにより、根は Δ = 0 のときも含めて常に 2 個であると考えることができる。この例は一般に、代数方程式論の基本定理の一つの表現「n-次方程式は必ず重複度まで込めてちょうど n 個の根を持つ」として述べることができる。同様の例として、複素解析函数に対する零点や極の位数（重複度）あるいは曲線の接触の位数（接触度）なども挙げられる。

またたとえば、自然数 n の素因数分解

[math]n = 2^{m(2)}3^{m(3)}5^{m(5)}\cdots p^{m(p)}\cdots[/math]

（実際には n ごとに右辺に現れる素因子は有限個、つまり殆どの m(p) が 0 となる実質有限積である）は、自然数 n を素数全体の成す集合 P を台とする多重集合 (P, m) として表示する方法を与えるものと解釈することができる（素因数分解が積の順番の違いを除いて一意であるということが多重集合の性質に対応する）。置換の巡回置換分解あるいは巡回置換型も同様である。

同様に、自然数 n の分割を考えることは、分割に現れる各整数 k (≤ n) の個数を重複度 m(k) ととれば、自然数全体の成す集合 N を台とする多重集合 (N, m) であって、重複度関数 m が次の二条件

[math] m(k) =0 \quad (k \gt n)[/math]

[math] 1 \cdot m(1) + 2 \cdot m(2) + \cdots + k \cdot m(k) + \cdots + n \cdot m(n) = n[/math]

を満たすようなものを一つ定めることに他ならない。ゆえに、分割数は、各自然数 n に対してこのような重複度関数 m のとり方が p(n) 通りあることを示している。

歴史

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

そのような理由により多重集合は、この構造が必要とされるたびに何度も再発見され、異なる名称を以って文献に現れることとなる。例えば、Peterson (1981) はこれを bag と呼んでおり、その語は {{#invoke:Footnotes | harvard_citation }} の影響によるものである。多重集合は他にも aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set) などと呼ばれている。

ただ多重集合の概念が古代より暗に用いられていたと言っても、それらが明示的に調べられるようになるのはずっと後になってからのことである。多重集合の最初の研究として知られるのは1150年ごろ、インドの数学者バースカラ2世による、多重集合の順列に関するものである。マリウス・ニゾリウス (1498–1576) の業績には多重集合の概念に関する別の先駆的言及が含まれる。Kircher (1650) は一つの元のみ重複する場合の多重集合の順列の数を求めた。ジャン・プルステは1675年に多重集合の順列に関する一般法則を著した。Wallis (1685) はこの法則をより詳細に説明している

明確な形で多重集合が現れるのはリヒャルト・デーデキントの手によるが、数学者が多重集合を定式化して明確な数学的対象としてその研究を始めたのは20世紀に入ってからである。

定義

X を全体集合とし、その任意の部分集合 A と X から非負整数全体の集合 N への写像 m: X → N で、supp(m) ⊂ A すなわち A に属さないの元 x に対しては恒等的に m(x) = 0 を満たすものの組 (A, m) を、A を台集合とする（非負整数値の重複度関数 (multiplicity function) m を持つ）多重集合といい、台集合 A の各元 a に対してその m による像 m(a) を a の重複度という。紛れのおそれの無い場合、多重集合 (A, m) をその台集合 A で表す。

非負整数値の重複度を持つ多重集合 (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]

のようにも記される（パーレンはしばしば省略される）。

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

などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような族 (bテンプレート:Ind)_i∈I に対して、同じ元からなる多重集合を {bテンプレート:Ind}_i∈I で表すことがある。

多重集合の構成

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

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

多重集合の演算と重複度函数

多重集合 (A, mテンプレート:Ind) に対し、台集合 A の部分集合 B を台集合とする多重集合 (B, mテンプレート:Ind) で B の各元 b の重複度について

[math]m_B(b) \leq m_A(b)[/math]

が成り立つとき、多重集合 (B, mテンプレート:Ind) は多重集合 (A, mテンプレート:Ind) の部分多重集合であるといい、(B, mテンプレート:Ind) ⊂ (A, mテンプレート:Ind) で表す。

また、多重集合に対する和、差、積、対称差などの概念が、通常の集合に関する和、差、積、対称差などに従って定義される。例えば、多重集合 A, B の和 A ∪ B は包含関係 ⊂ を順序とする上限、積 A ∩ B は ⊂ に関する下限である。多重集合の演算は台集合に対しては通常の集合演算として作用するが、その元の重複度については多少の注意を要する。

集合の指示函数 χ

	U: 全体集合, A ⊆ 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]

集合 X の（全ての元を各個に区別して）各元の重複度を 1 としたときの重複度関数は集合 X の指示関数である。有限集合の指示関数を数え上げ測度で積分したものは集合の基数をあたえるから、多重集合の元 a の重複度は、同じ値 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]

に従う。また重複度函数の和　mテンプレート:Ind + mテンプレート:Ind を重複度函数に持つ多重集合を A と B との結合 (join) あるいは直和（非交和、sum）と呼び

[math]A\sqcup B, A\uplus B[/math]

などで表す（非交和と呼ぶことがあるにもかかわらず、台集合として A ∩ B = ∅ であることは必要でないことに注意。これは台集合の交わりに属する元であっても、それらはその重複度のために、何れの台集合に由来する元であるかの区別を受けるためである）。すなわち

[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]

と書ける。

多重集合の数え上げ

濃度 n の有限集合から元をとって作られる濃度 k の多重集合の総数は多重集合（係）数 (multiset coefficient, multiset number) と呼ばれる。この数はしばしば二項係数と似せて ((テンプレート:Su)) と書かれる

多重集合係数の値は

[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]

で明示的に与えることができる。ただし、二番目の式は二項係数としての表示である（多重集合を別に定義することを嫌って二項係数としてのみ書く文献も多い）であり、このような多重集合の総数は濃度 n + k − 1 の集合内の k-元部分集合の総数に等しい。二項係数との類似性を見るために、上記の式の分子に上昇階乗冪を用いて ((テンプレート:Su)) = テンプレート:Fraction と書けば、二項係数が下降階乗冪を用いて (テンプレート:Su) = テンプレート:Fraction と書かれることとの対比は明瞭である。

一般化された二項係数を

[math]{n \choose k}={n(n-1)(n-2)\cdots(n-k+1) \over k!}[/math]

において n が非負整数とは限らず、負の整数、整数でない実数、実数でない複素数などとすることによって定義することができる（k = 0 ならば空積となるからこの係数の値は 1 であるものと約束する）。この意味において、n-元集合から得られる 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\gt 0)[/math]

を初期条件 ((テンプレート:Su)) = 1 (n ∈ N) および ((テンプレート:Su)) = 0 (k > 0) の下で与えることができる。この漸化式は以下のように組合せ論的に解釈することができる。

以下 テンプレート:Bracket = {1, …, n} と書く。位数 0 の（空）多重集合は常にただ一つであり、また n = 0 のときそれより位数の大きな多重集合は存在しないから、初期条件はこの解釈に適合する。さて n,k > 0 のとき、集合 テンプレート:Bracket の元からなる位数 k の多重集合が末尾の元 n を含むか含まないかに分けて考える。含むならば、n の一つはさておいて残りのk − 1 個の元を [n] から選んで多重集合を作りそこに n を加えればよいから、そのようなものは ((テンプレート:Su)) 通りある。他方、含まないときは、末尾を除いた集合 テンプレート:Bracket から k-元多重集合をつくることになるから、そのようなものは ((テンプレート:Su)) 通りである。従って ((テンプレート:Su)) = ((テンプレート:Su)) + ((テンプレート:Su)) が得られた。

多項式表現

集合 {x} を単項式 x で表すと、その冪集合 {{}, {x}} は二項式 1 + x で表すことができる。集合 {x, y} を単項式 xy に対応させればその冪集合 {{}, {x}, {y}, {x, y}} は多項式 (1 + x)(1 + y) = 1 + x + y + xy が対応する。同様に多重集合 {x, x} を単項式 xテンプレート:Exp に対応させれば、その冪多重集合（部分多重集合全体の成す多重集合）{{}, {x}, {x}, {x, x}} は多項式 (1 + x)テンプレート:Exp = 1 + 2x + xテンプレート:Exp に対応する。単項式 xテンプレート:Exp で表される多重集合の冪多重集合が

[math](1+x)^n=\sum_{k=0}^n{n \choose k} x^k[/math]

で表されることは、二項係数 (テンプレート:Su) が n-元集合から選んだ k-元の組合せの総数を数え上げることになる理由を説明するものである。

集合 {x} に元をとる有限多重集合全体の成す無限集合 {{}, {x}, {x, x}, {x, x, x}, …} は形式冪級数 S = 1 + x + xテンプレート:Exp + xテンプレート:Exp + ⋯ (= 1 + xS) で表され、形式解 S = (1 − x)テンプレート:Exp に多重集合の集合としての意味を与えることができるが、中間表現である 1 − x は多重集合の集合として意味を成さない。同様に、単項式 xy で表される集合に値を持つ有限多重集合全体の成す無限集合は

[math](1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+\dotsb[/math]

で表され、単項式 xテンプレート:Exp で表される多重集合から元をとって作られる有限多重集合全体の成す無限多重集合は x = y なる特別の場合として (1 − x)テンプレート:Exp = 1 + 2x + 3xテンプレート:Exp + ⋯ で表される。さらに進めて単項式 xテンプレート:Exp に対応する多重集合に値をとる有限多重集合全体の成す無限多重集合は

[math](1-x)^{-n}=\sum_{k=0}^\infty{-n \choose k} (-x)^k[/math]

である。これを「多重集合は濃度が負の集合」と形式的に説明することができる。負の二項係数 (テンプレート:Su) は n-元集合から元をとって得られる k-元多重集合の総数を数えるものである。

累積母函数

非負整数の多重集合

非負整数 n を単項式 xテンプレート:Exp で表すと、同様にして非負整数からなる有限多重集合を多項式 f(x) で表すことができる。

これには累積母函数 g(t) = log f(eテンプレート:Exp) を考えるのが簡便である。

• 多重集合の濃度は eテンプレート:Exp = 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].

例えば非負整数の多重集合 {2, 2, 2, 3, 5} に対応する多項式は f(x) = 3xテンプレート:Exp + xテンプレート:Exp + xテンプレート:Exp であり、その累積母函数 g(t) = log(3eテンプレート:Exp + eテンプレート:Exp + eテンプレート:Exp), 濃度 3 + 1 + 1 = 5, 導函数 gテンプレート:'(t) = (3eテンプレート:Exp + eテンプレート:Exp + eテンプレート:Exp)テンプレート:Exp(6eテンプレート:Exp + 3eテンプレート:Exp + 5eテンプレート:Exp), 平均値 μ = (3 + 1 + 1)テンプレート:Exp(6 + 3 + 5) = 2.8 などと計算できる。

ここに現れる数 (μ,σテンプレート:Exp, …) = (gテンプレート:'(0), g"(0), …) は各次数の累積率と呼ばれる。

非負整数全体の成す無限集合 {0, 1, 2, …} は形式冪級数 1 + x + xテンプレート:Exp + ⋯ = (1 − x)テンプレート:Exp で表され、平均値や標準偏差は定義されないが、累積母函数 g(t) = −log(1 − eテンプレート:Exp) は持つ。この累積母函数の導函数は gテンプレート:'(t) = (eテンプレート:Exp − 1)テンプレート:Exp である。

実数の多重集合

実数からなる有限多重集合 A = {Aテンプレート:Ind} は累積母函数

[math]g_A(t) = \log \left(\sum_i e^{t A_i}\right)[/math]

で表される。この表現は一意である（つまり、相異なる多重集合は相異なる累積母函数を持つ）。平均 μ, 標準偏差 σ を持つ n 個の実数からなる多重集合の累積母函数は g(t) = log n + μt + 2テンプレート:Exp(σt)テンプレート:Exp + ⋯ で与えられ、その導函数は gテンプレート:'(t) = μ + σテンプレート:Expt + ⋯となる。

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

一つの実数 k のみを含む n 元の定値多重集合 {k, k, k, k, …, k} は g(t) = log n + kt が対応し、導函数は n に無関係に 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]

となる。多重集合 2⋅A = {2Aテンプレート:Ind} は多重集合 2 × A = A + A = {Aテンプレート:Ind + Aテンプレート:Ind} とは異なることに注意せよ。例えば、2 ⋅{1, −1} = {2, −2} に対し、2 × {1, −1} = {1, −1} + {1, −1} = {1 + 1, 1 − 1, −1 + 1, −1 −1} = {2, 0, 0, −2} である。k × 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]

と矛盾なく定義される。定数項 kテンプレート:Explog(2) は微分で消え、省略した後続の項は極限をとれば消える。ゆえに平均 0, 標準偏差 1 を持つ標準正規分布に対して、その累積母函数の導函数は gテンプレート:'(t) = t となる。平均 μ, 標準偏差 σ の正規分布の累積母函数の導函数は gテンプレート:'(t) = μ + σテンプレート:Expt で与えられる。

応用

多重集合は様々な応用を持つ。多重集合はそのより高度な厳密さが希求されたことの結果として、組合せ論における主要な構造となり、現代組合せ論は集合ではなく多重集合に対する理論として発展した。多重集合はデータベースにおいて重要な道具となった。例えば多重集合はデータベースシステムにおける重要な関係としてしばしば用いられる。多重集合は計算機科学においても重要な役割を務める。

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

一般化

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

たとえば、ファジィ集合（曖昧集合、確率的集合）は、区間 テンプレート:Closed-closed に値をとる重複度函数を備えた多重集合と考えることもできる。この場合、ファジィ集合の帰属率函数（メンバシップ函数）が重複度函数に相当する。ただし、ある集合 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
• Rough multisets
• Real-valued multisets (in which multiplicity of an element can be any real number)
• Hybrid sets
• where multiplicity is any real-valued step function
• Soft multisets
• Soft fuzzy multisets
• Named set (unification of all generalizations of sets)

関連項目

• 集合
• 族 (数学)

外部リンク

• Weisstein, Eric W. “Multiset”. MathWorld（英語）.
• multiset in nLab
• multiset - PlanetMath.（英語）
• テンプレート:ProofWiki
• {{#invoke:citation/CS1|citation

|CitationClass=citation }}