多重集合

同義語:multisetマルチセット

概要

多重集合(multiset)とは、集合 $X$ の各元に重複度とよぶ自然数を割り当てる写像 $M\colon X\to\mathbb{N}$ のことで、同じ元を何個含むかまで区別する、順序のない集まりである。大きさ $k$ の有限多重集合は $X^k$ の対称群の軌道と 1 対 1 に対応し、$n$ 元集合の上には $\binom{n+k-1}{k}$ 個ある。素因数の集まり、多項式の根、行列の固有値、整数の分割はどれも多重集合である。和・合併・共通部分・差が重複度ごとに定まるが、部分多重集合の束には一般に補元がなく、集合の等式がそのまま成り立つとは限らない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 集合, 写像, 二項係数

集合では、同じ元を 2 度書いても意味は変わらない。$\{2,2,3\}$ と $\{2,3\}$ は同じ集合である。しかし、$12=2\cdot2\cdot3$ の素因数、多項式 $(x-1)^2(x+2)$ の根、行列の固有値、グラフの次数のように、順序には意味がないが「何個あるか」には意味がある集まりが、数学のあちこちに現れる。
多重集合は、このような集まりを「元ごとの個数を与える写像」として扱う言葉である。集合に個数の情報を足したものと見ても、有限列の順序を忘れたものと見てもよい。
この記事では、多重集合を重複度の写像として定義し、和・合併・共通部分・差の演算と、集合のときと違う点を調べる。次に、有限列との対応(thm-ms-orbit)、大きさ $k$ の多重集合の個数 $\binom{n+k-1}{k}$(thm-ms-count)を証明し、最後に、無限下降列のない順序の上では、元を小さい元に置き換える操作が必ず止まるという定理(thm-ms-well-founded)を示す。

定義

多重集合

集合 $X$ 上の多重集合(multiset)とは、写像 $M\colon X\to\mathbb{N}$ のことをいう($\mathbb{N}$ は $0$ を含む)。値 $M(x)$ を $M$ における $x$ の重複度(multiplicity)という。
$\operatorname{supp}M:=\{x\in X\mid M(x)\ge1\}$ を $M$ の台(support)といい、$M(x)\ge1$ のとき $x$ は $M$ に属するという。台が有限である多重集合を有限多重集合といい、その大きさを
$$\lvert M\rvert:=\sum_{x\in X}M(x)$$
で定める。大きさ $k$ の有限多重集合を $k$ 多重集合($k$-multiset)という。

有限多重集合は、元を重複度の回数だけ並べて $\{\!\{2,2,3\}\!\}$ と書く。これは $X=\mathbb{Z}$ 上で $M(2)=2$、$M(3)=1$、ほかの元では $0$ である写像を表す。指数で $\{\!\{2^2,3\}\!\}$ とも書く。多重集合は写像なので、2 つが等しいのはすべての元で重複度が等しいときであり、並べる順序に意味はない。$\{\!\{2,3,2\}\!\}=\{\!\{2,2,3\}\!\}$ である。一方 $\{\!\{2,2,3\}\!\}\ne\{\!\{2,3\}\!\}$ である。
$X$ の部分集合 $A$ は、指示関数 $1_A$ という重複度が $0$ か $1$ の多重集合と同一視できる。すべての元の重複度が $0$ である多重集合を空多重集合といい $0$ と書く。これは大きさ $0$ のただ 1 つの多重集合で、空集合に対応する。

包含と演算

$M,N$ を $X$ 上の多重集合とする。

  1. $M$ が $N$ の部分多重集合(submultiset)であるとは、すべての $x\in X$ で $M(x)\le N(x)$ となることをいい、$M\le N$ と書く。
  2. 和 $M+N$ を $(M+N)(x):=M(x)+N(x)$ で定める。
  3. 合併 $M\cup N$ を $(M\cup N)(x):=\max\{M(x),N(x)\}$ で定める。
  4. 共通部分 $M\cap N$ を $(M\cap N)(x):=\min\{M(x),N(x)\}$ で定める。
  5. 差 $M\setminus N$ を $(M\setminus N)(x):=\max\{M(x)-N(x),0\}$ で定める。

$M,N$ が部分集合 $A,B$ の指示関数なら、$\cup,\cap,\setminus$ は集合の合併・共通部分・差に一致し、$\le$ は包含 $\subset$ に一致する。これに対して和は集合の演算に対応しない。$\{\!\{a\}\!\}+\{\!\{a\}\!\}=\{\!\{a,a\}\!\}$ は重複度 $2$ の元をもつので、集合に戻らない。「まとめる」操作が 2 通りあることに注意する。$\{\!\{a,a,b\}\!\}$ と $\{\!\{a,c\}\!\}$ の和は $\{\!\{a,a,a,b,c\}\!\}$、合併は $\{\!\{a,a,b,c\}\!\}$ である。

例

素因数の多重集合

正の整数 $n$ に、素数 $p$ の重複度を $n$ を割り切る $p$ の最大冪の指数 $v_p(n)$ とする多重集合を対応させる。算術の基本定理 により、これは正の整数全体から、素数全体の上の有限多重集合全体への全単射である。$12$ には $\{\!\{2,2,3\}\!\}$、$1$ には空多重集合が対応する。
積は和に、整除 $m\mid n$ は包含 $\le$ に、最大公約数は共通部分に、最小公倍数は合併に対応する。たとえば $12$ と $18$ では $\{\!\{2,2,3\}\!\}\cap\{\!\{2,3,3\}\!\}=\{\!\{2,3\}\!\}$ が最大公約数 $6$ に、合併 $\{\!\{2,2,3,3\}\!\}$ が最小公倍数 $36$ に対応する。

多項式の根の多重集合

複素数の上の $n$ 次モニック多項式 $f$ に、$a\in\mathbb{C}$ の重複度を根 $a$ の重複度(重根)とする多重集合を対応させる。代数学の基本定理 により $f=\prod_a(x-a)^{M(a)}$ と書けるので、$n$ 次モニック多項式と $\mathbb{C}$ 上の $n$ 多重集合は 1 対 1 に対応する。$(x-1)^2(x+2)$ には $\{\!\{1,1,-2\}\!\}$ が対応する。根の集合 $\{1,-2\}$ だけでは多項式は決まらない。$\mathbb{R}$ 上の多重集合から実係数の多項式を作る写像は単射だが全射ではなく、$x^2+1$ は実数の根の多重集合からは得られない。
$\mathbb{C}$ 上の $n$ 多重集合の全体には自然な位相が入る。これが 対称積(位相空間) $SP^n(\mathbb{C})$ である。

反例:固有値の多重集合が等しくても相似とは限らない

$n$ 次複素正方行列の固有値は、特性多項式の根の多重集合として $n$ 個ある。相似な行列は特性多項式が等しいので、固有値の多重集合も等しい。逆は成り立たない。$\begin{pmatrix}1&1\\0&1\end{pmatrix}$ と単位行列 $I$ の固有値の多重集合はどちらも $\{\!\{1,1\}\!\}$ であるが、$I$ に相似な行列は $I$ だけなので、この 2 つは相似でない。満たす性質:固有値の多重集合が等しい。満たさない性質:相似である。成り立たない含意は「固有値の多重集合が等しい $\Rightarrow$ 相似」である。

グラフの次数と整数の分割

有限グラフの頂点の次数の全体は、$\mathbb{N}$ 上の多重集合である。これを大きい順に並べたものが次数列であり、並べる順序は頂点の名前によらないので、次数の多重集合はグラフの同型で変わらない。
$n$ の分割は、和が $n$ である正の整数の有限多重集合のことである。$4$ の分割は $\{\!\{4\}\!\}$、$\{\!\{3,1\}\!\}$、$\{\!\{2,2\}\!\}$、$\{\!\{2,1,1\}\!\}$、$\{\!\{1,1,1,1\}\!\}$ の 5 個である(分割数)。

有限列の順序を忘れる

多重集合は、有限列の順序を忘れたものとしても定義できる。対称群 $S_k$ を $X^k$ に $\sigma\cdot(x_1,\dots,x_k):=(x_{\sigma^{-1}(1)},\dots,x_{\sigma^{-1}(k)})$ で作用させる(群の作用)。

列の軌道と多重集合

$k\ge0$ とする。列 $(x_1,\dots,x_k)\in X^k$ に、$\Phi(x_1,\dots,x_k)(x):=\#\{i\mid x_i=x\}$ で定まる $k$ 多重集合を対応させる写像を $\Phi$ とする。

  1. $\Phi$ は $X^k$ から $X$ 上の $k$ 多重集合全体への全射である。
  2. 2 つの列の $\Phi$ の値が等しいことと、同じ $S_k$ 軌道に属することは同値である。したがって $\Phi$ は、軌道の集合 $X^k/S_k$ と $k$ 多重集合全体の間の全単射を与える。
  3. $k$ 多重集合 $M$ に対応する軌道の元の個数は $\dfrac{k!}{\prod_{x}M(x)!}$ である。

1:$k$ 多重集合 $M$ の台の元を、重複度の回数ずつ任意の順に並べた列の値は $M$ である。
2:$\sigma$ で列を並べ替えても、値 $x$ をとる添字の個数は変わらないので、同じ軌道の列の値は等しい。逆に $\Phi(a)=\Phi(b)=M$ とする。各 $x$ について、$a_i=x$ となる添字の集合 $I_x$ と $b_i=x$ となる添字の集合 $J_x$ はどちらも $M(x)$ 個の元からなる。$\{1,\dots,k\}$ は $I_x$ たちに分割され、$J_x$ たちにも分割されるので、各 $I_x$ を $J_x$ へ全単射で写して $\sigma\in S_k$ を作れる。$j=\sigma(i)$、$i\in I_x$ なら $(\sigma\cdot a)_j=a_i=x=b_j$ なので $\sigma\cdot a=b$ である。
3:$a$ を $M$ の列とする。$\sigma$ が $a$ を固定することは、$\sigma(I_x)=I_x$ がすべての $x$ で成り立つことと同値であり、そのような $\sigma$ は $\prod_xM(x)!$ 個ある。軌道の元の個数は $k!$ を固定部分群の位数で割ったものである。$\square$

3 は同じものを含む順列の個数(同じものを含む順列)にほかならない。$X$ が $n$ 元集合のとき、すべての $k$ 多重集合について足すと $n^k$ になる。これは多項係数の和が $n^k$ であるという式である。
軌道の大きさは列によって違う。ここを見落とすと数え間違いになる。

反例:列の個数を k! で割っても多重集合の個数にならない

$X=\{a,b\}$、$k=2$ とする。列は $(a,a),(a,b),(b,a),(b,b)$ の $4$ 個であるが、$2$ 多重集合は $\{\!\{a,a\}\!\},\{\!\{a,b\}\!\},\{\!\{b,b\}\!\}$ の $3$ 個で、$4/2!=2$ ではない。満たす性質:$S_2$ が $X^2$ に作用し、軌道と多重集合が対応する。満たさない性質:どの軌道も元を $k!$ 個もつ。実際、$\{\!\{a,a\}\!\}$ の軌道は元を $1$ 個しかもたない。「$\lvert X^k/S_k\rvert=\lvert X^k\rvert/k!$」という式はこの例で成り立たない。この式は $S_k$ の作用が自由であるときに成り立つ(相異なる元の列だけなら、部分集合の個数 $\binom nk$ が正しく出る)。

有限多重集合の全体は、和について可換モノイドをなす。単位元は空多重集合である。これは写像の集合としては $X$ 上の有限台の関数の全体であり、自由可換モノイドの定義そのものである。すなわち、1 元からなる多重集合 $\{\!\{x\}\!\}$ を $e_x$ と書くと、有限多重集合は $M=\sum_xM(x)e_x$ とただ 1 通りに書け、可換モノイド $(A,+)$ への任意の写像 $f\colon X\to A$ は準同型 $M\mapsto\sum_xM(x)f(x)$ にただ 1 通りに延びる(自由可換モノイド の定理「自由可換モノイドの普遍性」)。列 $(x_1,\dots,x_k)$ を $e_{x_1}+\dots+e_{x_k}$ に写すのが $\Phi$ である。
変数の集合 $X$ の上の単項式 $\prod_xx^{M(x)}$ は有限多重集合と 1 対 1 に対応し、積は和に、次数は大きさに対応する。この見方は ex-ms-monomials で使う。

演算の法則

重複度ごとに見ると、演算は $\mathbb{N}$ の中の計算になる。そのため、等式の確かめは 2 つの自然数の大小で場合を分けるだけで済む。

演算の基本法則

$L,M,N$ を $X$ 上の多重集合とする。

  1. $\cup$ と $\cap$ は、可換・結合的で、吸収律 $M\cup(M\cap N)=M=M\cap(M\cup N)$ と分配律 $L\cap(M\cup N)=(L\cap M)\cup(L\cap N)$ を満たす。とくに $X$ 上の多重集合の全体は $\le$ について分配束である。
  2. 和は可換・結合的で、簡約できる:$L+M=L+N$ なら $M=N$ である。
  3. 和は合併と共通部分の上に分配する:$L+(M\cup N)=(L+M)\cup(L+N)$、$L+(M\cap N)=(L+M)\cap(L+N)$。
  4. $(M\cup N)+(M\cap N)=M+N$。
  5. $(M\setminus N)+N=M\cup N$、$M\setminus(M\setminus N)=M\cap N$、$(M+N)\setminus N=M$。

要点:どの等式も、すべての $x$ での値の等式なので、$M(x),N(x),L(x)$ を $a,b,c\in\mathbb{N}$ と書いて $\mathbb{N}$ の中で確かめればよい。

場合分けを開く

1:$\mathbb{N}$ は全順序集合で、$\max,\min$ はその上限・下限である。全順序集合は分配束なので、値ごとに法則が成り立つ。

2:$\mathbb{N}$ の加法の性質である。

3:$a\le b$ なら $c+a\le c+b$ なので、$c+\max\{a,b\}=\max\{c+a,c+b\}$ と、$\min$ についての同じ式が成り立つ。

4:$\max\{a,b\},\min\{a,b\}$ は $a,b$ を大きい順に並べたものなので、和は $a+b$ である。

5:$a\ge b$ のとき、$\max\{a-b,0\}+b=a=\max\{a,b\}$、$a-(a-b)=b=\min\{a,b\}$ である。$a< b$ のとき、$0+b=b=\max\{a,b\}$、$a-0=a=\min\{a,b\}$ である。最後の式は $\max\{(a+b)-b,0\}=a$ である。$\square$

4 の両辺の大きさをとると、有限多重集合について $\lvert M\cup N\rvert+\lvert M\cap N\rvert=\lvert M\rvert+\lvert N\rvert$ を得る。これは包除原理の 2 個の場合の式である。
一方、集合の等式の中には、そのままでは多重集合で成り立たないものがある。下の表では $M=\{\!\{a,a\}\!\}$、$N=\{\!\{a\}\!\}$ とする。

集合で成り立つ等式多重集合での左辺右辺
$(M\setminus N)\cup(M\cap N)=M$$\{\!\{a\}\!\}\cup\{\!\{a\}\!\}=\{\!\{a\}\!\}$$\{\!\{a,a\}\!\}$
$(M\setminus N)\cap N=\emptyset$$\{\!\{a\}\!\}\cap\{\!\{a\}\!\}=\{\!\{a\}\!\}$$0$

どちらも原因は同じで、$M\setminus N$ と $N$ が多重集合では交わることにある。prop-ms-laws の 5 のとおり、$M$ に戻すには合併ではなく和を使う。$N\le M$ なら $(M\setminus N)+N=M$ である。$\cap$ は和の上に分配しないことにも注意する。$N\cap(N+N)=\{\!\{a\}\!\}$ であるが、$(N\cap N)+(N\cap N)=\{\!\{a,a\}\!\}$ である。
また、部分多重集合の全体には一般に補元がない。

反例:部分多重集合の束は Boolean でない

$M=\{\!\{a,a\}\!\}$ の部分多重集合は $0,\{\!\{a\}\!\},\{\!\{a,a\}\!\}$ の $3$ 個で、$\le$ について一直線に並ぶ。$N=\{\!\{a\}\!\}$ に対し、$N\cup N'=M$ かつ $N\cap N'=0$ となる $N'\le M$ はない。前者は $N'=M$ を要し、そのとき $N\cap N'=N\ne0$ だからである。満たす性質:prop-ms-laws の 1 により分配束である。満たさない性質:補元をもつ。成り立たない含意は「部分集合の全体と同じく、部分多重集合の全体も Boolean 代数になる」である。

個数

$X$ が $n$ 元集合のとき、$k$ 多重集合の個数を $\left(\!\!\binom{n}{k}\!\!\right)$ と書く。これは $n$ 種類のものから重複を許して $k$ 個を順序なしに選ぶ方法の数である(高校の記号では ${}_n\mathrm{H}_k$)。

k 多重集合の個数

$n\ge1$、$k\ge0$ とする。$n$ 元集合の上の $k$ 多重集合の個数は
$$\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}$$
である。$n=0$ のときは、$k=0$ で $1$ 個、$k\ge1$ で $0$ 個である。

$X=\{1,\dots,n\}$ としてよい。$k$ 多重集合の元を小さい順に並べると、広義単調増加な列 $1\le b_1\le b_2\le\dots\le b_k\le n$ が得られ、これは多重集合とちょうど 1 対 1 に対応する。$a_i:=b_i+i-1$ とおくと
$$1\le a_1< a_2< \dots< a_k\le n+k-1$$
である。実際、$a_{i+1}-a_i=b_{i+1}-b_i+1\ge1$ で、$a_k=b_k+k-1\le n+k-1$ である。逆に、このような列から $b_i:=a_i-i+1$ とおくと、$b_{i+1}-b_i=a_{i+1}-a_i-1\ge0$、$b_1=a_1\ge1$、$b_k\le n$ となる。この 2 つの対応は互いに逆なので、$k$ 多重集合と $\{1,\dots,n+k-1\}$ の $k$ 元部分集合は 1 対 1 に対応し、後者の個数は $\binom{n+k-1}{k}$ である。
$n=0$ のとき、$X$ は空なので、上の多重集合は空多重集合だけであり、その大きさは $0$ である。$\square$

同じ数は「仕切り」の数え方でも分かる。元 $1,\dots,n$ の重複度 $m_1,\dots,m_n$ を、$k$ 個の玉と $n-1$ 本の仕切りの列 $\underbrace{\bullet\cdots\bullet}_{m_1}\mid\underbrace{\bullet\cdots\bullet}_{m_2}\mid\cdots\mid\underbrace{\bullet\cdots\bullet}_{m_n}$ で表す。$n+k-1$ 個の位置のうち玉の位置を選べば列が決まる。つまり、$k$ 多重集合を数えることは、方程式 $m_1+\dots+m_n=k$ の $\mathbb{N}$ の解を数えることと同じである。各 $m_i\ge1$ の解は、$m_i-1$ に替えると $\binom{k-1}{n-1}$ 個である($n\ge1$、$k\ge1$)。これは台が $X$ 全体である多重集合の個数である。

順序を区別する順序を区別しない
重複を許す$n^k$(列)$\binom{n+k-1}{k}$(多重集合)
重複を許さない$n(n-1)\cdots(n-k+1)$(順列)$\binom{n}{k}$(部分集合)

4 つの数え方の位置づけは 場合の数の数え方の体系 にある。

多重集合の母関数

$n\ge0$、$X=\{1,\dots,n\}$ とする。形式的冪級数として
$$\sum_{k\ge0}\left(\!\!\binom{n}{k}\!\!\right)t^k=(1+t+t^2+\cdots)^n=\frac{1}{(1-t)^n}$$
が成り立つ。さらに、各元 $i$ の重複度を集合 $B_i\subset\mathbb{N}$ に制限した $k$ 多重集合の個数は、$\prod_{i=1}^n\bigl(\sum_{b\in B_i}t^b\bigr)$ の $t^k$ の係数である。

$\prod_{i=1}^n\bigl(\sum_{b\in B_i}t^b\bigr)$ を展開すると、各因子から項 $t^{m_i}$($m_i\in B_i$)を 1 つずつ選んだ積 $t^{m_1+\dots+m_n}$ の和になる。$t^k$ の係数は、各 $i$ で $m_i\in B_i$ かつ $m_1+\dots+m_n=k$ となる $(m_1,\dots,m_n)$ の個数であり、これは重複度を制限した $k$ 多重集合の個数である(各 $k$ で $m_i\le k$ だから和は有限である)。すべての $B_i$ を $\mathbb{N}$ にとれば 1 つ目の等式を得る。2 つ目の等式は $(1-t)(1+t+t^2+\cdots)=1$ による。$\square$

一般二項定理で $(1-t)^{-n}=\sum_k\binom{-n}{k}(-t)^k$ と展開して比べると、$\left(\!\!\binom{n}{k}\!\!\right)=(-1)^k\binom{-n}{k}$ が得られる。多重集合の数え上げは、部分集合の数え上げで $n$ を $-n$ に替えたものになっている。$B_i=\{0,1\}$ とすると $(1+t)^n$ で、部分集合の個数 $\binom nk$ に戻る。

単項式の個数

$n$ 個の変数の $k$ 次の単項式は $k$ 多重集合と 1 対 1 に対応するので、$\binom{n+k-1}{k}$ 個ある。変数 $x,y,z$ の $2$ 次の単項式は $x^2,y^2,z^2,xy,yz,zx$ の $\binom{4}{2}=6$ 個である。これは $k$ 次の斉次多項式のなす空間の次元であり、対称代数の $k$ 次の部分の次元でもある。

部分多重集合の個数

有限多重集合 $M$ の部分多重集合は、各 $x$ で $0,1,\dots,M(x)$ から値を選ぶので、$\prod_{x}(M(x)+1)$ 個ある。大きさ $j$ のものの個数は $\prod_x(1+t+\dots+t^{M(x)})$ の $t^j$ の係数である(thm-ms-gf)。ex-ms-primes の対応では、これは約数の個数の式である。$12$ の約数は $(2+1)(1+1)=6$ 個で、$\{\!\{2,2,3\}\!\}$ から選ぶ $j$ 個の元の組の個数 $1,2,2,1$($j=0,1,2,3$)は、素因数の個数が $j$ の約数の個数である。

小さい元への置き換えは止まる

順序のある集合の上の多重集合には、「ある元を、それより小さい有限個の元に置き換える」操作が考えられる。元の個数は増えてよいのに、順序が無限下降列をもたなければ、この操作は必ず有限回で止まる。

多重集合の置き換え

$(S,<)$ を半順序集合とする($<$ は狭義の順序)。$S$ 上の有限多重集合 $M,N$ について、$N$ の元 $x$ を 1 個取り除き、$x$ より小さい有限個($0$ 個でもよい)の元 $y_1,\dots,y_r$ を加えて $M$ が得られるとき、すなわち
$$M=(N\setminus\{\!\{x\}\!\})+\{\!\{y_1,\dots,y_r\}\!\},\qquad x\in\operatorname{supp}N,\quad y_j< x$$
となるとき、$M$ は $N$ の置き換えであるといい、$M\triangleleft N$ と書く。

置き換えの列は止まる

$(S,<)$ を、無限下降列 $x_0>x_1>x_2>\cdots$ をもたない半順序集合とする。このとき、$S$ 上の有限多重集合の無限列 $M_0\triangleright M_1\triangleright M_2\triangleright\cdots$ は存在しない。

無限列 $M_0\triangleright M_1\triangleright\cdots$ があるとして矛盾を導く。ラベル付きの根付き木 $T$ を、列に沿って順に作る。
はじめに、根 $r$ と、$M_0$ の元を重複度の回数だけとった子を置く。子のラベルはその元である。木の頂点のうち根以外のものには「処理済み」か「未処理」の印を付け、はじめはすべて未処理とする。$M_i$ が未処理の頂点のラベルの多重集合に等しい、という状態を保つ。
$M_{i+1}$ が $M_i$ の元 $x$ を $y_1,\dots,y_r$ に置き換えたものとする。ラベル $x$ の未処理の頂点 $v$ を 1 つ選び、処理済みにし、$v$ の子としてラベル $y_1,\dots,y_r$ の未処理の頂点を加える。未処理の頂点のラベルの多重集合は $M_{i+1}$ になる。
こうして全部の段を合わせた木 $T$ を作る。各頂点の子は有限個である。また、段ごとに別の頂点が処理済みになるので、$T$ の頂点は無限個ある。Kőnigの補題により、$T$ には根から出る無限の枝がある。枝の上の根以外の頂点のラベルを順に読むと、作り方から子のラベルは親のラベルより小さいので、$S$ の無限下降列が得られる。これは仮定に反する。$\square$

$S$ が整礎関係の意味で整礎な半順序集合なら無限下降列はないので、thm-ms-well-founded が使える。とくに $S=\mathbb{N}$ でよい。

袋の中の自然数

袋に自然数を有限個入れる。1 回の手番で数を 1 つ取り出し、それより小さい自然数を好きな個数だけ($0$ 個でもよい)入れる。たとえば
$$\{\!\{3,1\}\!\}\triangleright\{\!\{2,2,2,2,1\}\!\}\triangleright\{\!\{2,2,2,1,1,1,0\}\!\}\triangleright\cdots$$
数の個数はいくらでも増やせるが、thm-ms-well-founded により、どんな手順でも有限回で袋は空になる。しかし、手番の回数に前もって決まる上界はない。$\{\!\{1\}\!\}$ から $\{\!\{0,\dots,0\}\!\}$($0$ が $m$ 個)に移ると、そのあとちょうど $m$ 手で終わるので、最初の袋だけでは手番の回数は決まらない。

$M$ が $N$ から有限回($1$ 回以上)の置き換えで得られるとき $M\prec N$ と書く。$(S,<)$ に無限下降列がなければ $\prec$ は狭義半順序である。推移性は定義から明らかで、$M\prec M$ なら同じ置き換えを繰り返して無限列ができるからである。これを多重集合順序(multiset ordering)という。

全順序のときの比較

$S$ を全順序集合とする。有限多重集合 $M,N$ の元を大きい順に並べた列をそれぞれ $(a_1,\dots,a_p)$、$(b_1,\dots,b_q)$ とする。$M\prec N$ であることは、$M$ の列が $N$ の列より辞書式に小さいこと、すなわち、次のどちらかが成り立つことと同値である。

  1. ある $j$ について、$i< j$ で $a_i=b_i$ であり、$a_j< b_j$ である。
  2. $p< q$ で、$i\le p$ で $a_i=b_i$ である。

要点:1 回の置き換えは列を辞書式に小さくする。逆に、列が最初に違う元を残りの小さい元に置き換えれば $M$ に届く。

詳しい証明を開く

$M$ が $N$ の元 $x$ の置き換えであるとする。$x$ より大きい元の重複度は変わらず、$M(x)=N(x)-1$ であり、加わる元は $x$ より小さい。$N$ の列で $x$ が最後に現れる位置を $j$ とすると、$i< j$ で $a_i=b_i$ である。$M$ の列は $j-1$ 項で終わる(2 の場合)か、$a_j< x=b_j$ である(1 の場合)。辞書式の比較は推移的なので、有限回の置き換えでも同じである。

逆に 1 が成り立つとき、$N$ の $b_j$ を $a_j,\dots,a_p$(どれも $a_j$ 以下で、$b_j$ より小さい)に置き換え、次に $b_{j+1},\dots,b_q$ を大きい順に $1$ 個ずつ $0$ 個の元に置き換えると $M$ になる。2 が成り立つとき、$b_{p+1},\dots,b_q$ を $1$ 個ずつ $0$ 個の元に置き換えると $M$ になる。$\square$

thm-ms-well-founded の仮定は外せない。

外す条件反例成り立たなくなること
$S$ に無限下降列がない$S=\mathbb{Z}$、$\{\!\{0\}\!\}\triangleright\{\!\{-1\}\!\}\triangleright\{\!\{-2\}\!\}\triangleright\cdots$置き換えの列が止まる
多重集合が有限である$S=\mathbb{N}$、$M_i$ を $\{i,i+1,\dots\}$ の指示関数とし、$i$ を $0$ 個の元に置き換える置き換えの列が止まる
加える元が $x$ より真に小さい$S=\mathbb{N}$、$y_j\le x$ を許すと $\{\!\{0\}\!\}$ を $\{\!\{0\}\!\}$ に置き換え続けられる置き換えの列が止まる

2 行目では $\lvert M_i\rvert$ が定義されない。thm-ms-well-founded の証明では、$M_0$ が有限であることが根の子の有限性に使われている。この順序は、手続きがいつか止まることを示すのに使う。「大きい部分が減り、小さい部分はいくら増えてもよい」という形なら止まると言えるからである。

補足

多重集合の定義には流儀の差がある。Sta12 §1.2 は、$\sum_x\nu(x)< \infty$ である $\nu\colon S\to\mathbb{N}$ と集合 $S$ の組として有限多重集合を定義する。この記事は台が無限のものも多重集合とよぶ。台 $A$ と写像 $A\to\{1,2,\dots\}$ の組として定める流儀もあるが、$A$ の外の元の重複度を $0$ と読めば同じ情報である。重複度に $\infty$ や無限基数を許す流儀もあり、そのとき def-ms-ops の差はそのままでは使えない。
「$S$ の元の重複を許す $k$ 個の組合せ」(重複組合せ)は、$k$ 多重集合のことである(Sta12 §1.2、p. 25)。thm-ms-count の証明の対応 $a_i=b_i+i-1$ と、thm-ms-gf の 1 つ目の等式、式 $\left(\!\!\binom{n}{k}\!\!\right)=(-1)^k\binom{-n}{k}$ は同書の pp. 25–26 にある。
有限集合を底にとれば、多重集合の全体は $\mathbb{N}^n$ である。つまり、包含は $\mathbb{N}^n$ の成分ごとの順序、和はベクトルの和である。$\mathbb{Z}$ に値をとる場合に広げると 自由アーベル群になり、差が常に定義できる。ex-ms-primes では有理数の素因数分解、すなわち負の指数を許すことに対応する。

関連項目

参考文献

[1]
Richard P. Stanley, Enumerative Combinatorics, Volume 1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, 2012, §1.2(pp. 25–26、多重集合の定義、$k$ 多重集合、部分多重集合の個数、式 (1.20)・(1.21))。頁は著者公開版(2011-07-15)の頁

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する