|
数学における多重集合（たじゅうしゅうごう、multiset）あるいはバッグ（; かばん）は、集合に同じ値の元がいくつも含まれるとき、各元がそれぞれいくつ含まれるかというを考え合わせた集合概念である。非順序対、非順序組 ともいう〔文脈によっては集合のことを非順序対 (unordered pair) などと呼ぶこともある。特に、''x'' ≠ ''y'' のときの を非順序対と呼ぶときは、これが集合であると理解しても多重集合であると理解しても論理的には同じである（''x'' = ''y'' のときは差異が認められる）。〕。 クヌースによれば、1970年代に最初に多重集合 (multiset) という言葉を提案したのは、オランダ人数学者のニコラース・ホーバート・ド・ブラン (IPA: ) であるという〔 クヌースは同書で、多重集合に対して提案された他の名前（例えば,リスト(list)、まとまり(bunch)、バッグ(bag)、堆積(heap)、標本(sample)、重みつき集合(weighted set)、コレクション(collection)、組(suite).など）も提示している。 〕〔 多重集合の歴史に関するサーベイ論文である。 〕。しかし、数学における多重集合の概念は、"multiset" という名称がつけられる90年以上も前にすでに使用が認められる。実際、1888年に発表されたリヒャルト・デデキントの有名な論文 "Was sind und was sollen die Zahlen?" （「数とは何か、何であるべきか？」）において、実質的に多重集合の概念が用いられている〔 〕〔 〕〔。 == 導入 == 集合と多重集合の峻別のために、集合のように 波括弧 で囲む代わりに、二重ブレース 〔中抜き太字の類例だが、重ねうちで表すときは間が広いと「集合の集合」と紛らわしい。〕 や角括弧 あるいは中抜きブレース ⦃⦄().〔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〕 などで囲むこともある。 集合と多重集合と順序対（あるいは組）は例えば次のような点で差異が認められる。''a'' ≠ ''b'' として、 * 順序対: (''a'', ''a'', ''b'') と (''a'', ''b'', ''a'') とは順序三つ組として異なる（各成分の現れる順番を変えてはいけない）。これらはもちろん (''a'', ''b'') とも異なる。 * 多重集合: と は多重集合として一致する（元の現れる順番は関係無い）が、 と は多重集合として異なる（重複度が異なるなら多重集合としては異なる）。 * 集合: と と はいずれも同じ集合である（元の現れる順番は関係なく、また同じ元は何度現われてもひとつあることと同じ）〔このような外延的記法での例を挙げると、集合なのになぜか多重集合のようではないか、不自然だといったようなことを考える向きもあるだろうが、内包的記法が多用される数学の文脈では（それを外延的に書き直すと）このような例は実際に頻繁に遭遇することであり、このように規約を設けることには便宜上も意味のあることである。簡単な例で言えば、偶数の集合 2Z = と 4 の倍数の集合 4Z = の和集合はもちろん偶数の集合だが、2Z ∪ 4Z = の右辺には 4 の倍数が 2 回ずつ現れている。〕。 建前上は基本的に集合のみを扱い多重集合を扱わないというような（しばしば初等的な）文脈でも、「重複度を込めて」という注釈とともに一時的に多重集合が扱われることがある。たとえば、二次式 ''x''² + ''ax'' + ''b'' に対して、Δ := ''a''² − 4''b'' とおき、その根の集合 : を考えると、この集合の濃度（根の個数）は Δ ≠ 0 のとき 2 だが、Δ = 0 のときは退化して 1 になってしまう。これを Δ = 0 のときは 2 つの根がたまたま重なったもの（重根）と考えて重複度 2 を与えることにより、根は Δ = 0 のときも含めて常に 2 個であると考えることができる〔文脈によっては、「解（の個数）」と言ったときは集合として、「根（の個数）」と言ったときは多重集合として、それぞれ考えるといったような便宜上の規約が設けられていることがあるので注意。〕。この例は一般に、代数方程式論の基本定理の一つの表現「''n'' 次方程式は必ず重複度まで込めてちょうど ''n'' 個の根を持つ」として述べることができる。同様の例として、複素解析函数に対する零点や極の位数（重複度）なども挙げられる。 またたとえば、自然数の素因数分解 : （実際には ''n'' ごとに右辺に現れる素因子は有限個、つまり殆どの ''m''(''p'') が 0 となる実質有限積である）は、自然数 ''n'' を素数全体の成す集合 P を台とする多重集合 (P, ''m'') として表示する方法を与えるものと解釈することができる（素因数分解が積の順番の違いを除いて一意であるということが多重集合の性質に対応する）。置換の巡回置換分解あるいは巡回置換型も同様である。 もう少し複雑な例として、自然数の分割を考える。自然数''n''のある分割を''D''とし、分割''D''における整数''k''(≦''n'')の重複度を''mD,n''(''k'')とすると、''n''は : と表現できる。この表現を、重複度関数の方を主体として考えてみる。''n''を固定したとき、自然数全体の成す集合 N を台とするある多重集合 (N, ''m'')であって、重複度関数 ''m''が次の2条件 : : を満たすようなものを1つ定めれば、多重集合 (N, ''m'')は''n''のある分割を定めていることになる。 ''n'' を固定すると、''n''の分割を与えるような重複度関数 ''m'' のとり方は複数ある(その総数は分割関数 ''p''(''n'') で与えられる）から、このような多重集合(N, ''m'')も''p''(''n'') 個存在し、それらの多重集合による集合族が''n''の分割に対応する。 言い換えれば、N を台集合とする多重集合全体から自然数全体の成す集合 N へのある種の写像 ''P'' による ''n'' ∈ N の逆像 ''P''−1(''n'') として自然数 ''n'' の分割を解釈することができる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多重集合」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Multiset 」があります。 スポンサード リンク
|