多重集合
簡単な例で言えば、偶数の集合 2Z = {2n | n は整数} と 4 の倍数の集合 4Z = {4n | n は整数} の和集合はもちろん偶数の集合だが、2Z ∪ 4Z = {x | x = 2n または x = 4m (n, m は整数)} の右辺には 4 の倍数が 2 回ずつ現れている。
↑ この記法は(特に添字集合が明らかであるとして省略するとき)数列を表す慣習的な記法 {an} と紛らわしい。
↑ 二項係数が初等組合せ論において組合せ (choose) に関係することのアナロジーで、多重集合係数を "multichoose" と呼ぶこともある。しかし、二項係数の場合と異なり、多重集合係数に対する組合せ論的な多項式展開定理(いわば「多重集合定理」)は知られていない。またそのため、多項定理に現れる多項係数(これは多重集合係数とは直接的には関係ない)と混同の虞は無いであろう。
二項係数との類似性を見るために、上記の式の分子に上昇階乗冪を用いて ((nk)) = n⁄k! と書けば、二項係数が下降階乗冪を用いて (nk) = n⁄k! と書かれることとの対比は明瞭である。
一般化された二項係数を
( n k ) = n ( n − 1 ) ( n − 2 ) ⋯ ( n − k + 1 ) k ! {\displaystyle {n \choose k}={n(n-1)(n-2)\cdots (n-k+1) \over k!}}
において n が非負整数とは限らず、負の整数、整数でない実数、実数でない複素数などとすることによって定義することができる(k = 0 ならば空積となるからこの係数の値は 1 であるものと約束する)。この意味において、n-元集合から得られる k-元部分多重集合の総数は
( ( n k ) ) = ( − 1 ) k ( − n k ) {\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}}
と書ける。
たとえば、二つの文字 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} とも記す。
新たに添字を導入して
{ a 1 ( 1 ) , a 1 ( 2 ) , ... , a 1 ( m ( a 1 ) ) , a 2 ( 1 ) , a 2 ( 2 ) , ... , a 2 ( m ( a 2 ) ) , ... } {\displaystyle \{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 \}}
などのように同じ元を区別すれば、通常の集合として扱うこともできる。また、各値に対して、同じ値を持つ項は有限個であるような族 (bi)i∈I に対して、同じ元からなる多重集合を {bi}i∈I で表すことがある。