多重集合(multiset)とは、集合 $X$ の各元に重複度とよぶ自然数を割り当てる写像 $M\colon X\to\mathbb{N}$ のことで、同じ元を何個含むかまで区別する、順序のない集まりである。大きさ $k$ の有限多重集合は $X^k$ の対称群の軌道と 1 対 1 に対応し、$n$ 元集合の上には $\binom{n+k-1}{k}$ 個ある。素因数の集まり、多項式の根、行列の固有値、整数の分割はどれも多重集合である。和・合併・共通部分・差が重複度ごとに定まるが、部分多重集合の束には一般に補元がなく、集合の等式がそのまま成り立つとは限らない。
集合では、同じ元を 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$ 上の多重集合とする。
$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})$ である。
多重集合は、有限列の順序を忘れたものとしても定義できる。対称群 $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:$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$ であるという式である。
軌道の大きさは列によって違う。ここを見落とすと数え間違いになる。
$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$ 上の多重集合とする。
要点:どの等式も、すべての $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\}\!\}$ である。
また、部分多重集合の全体には一般に補元がない。
$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$)。
$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$ に戻る。
有限多重集合 $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 回の置き換えは列を辞書式に小さくする。逆に、列が最初に違う元を残りの小さい元に置き換えれば $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 では有理数の素因数分解、すなわち負の指数を許すことに対応する。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する