多重集合の数え上げ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/12 05:35 UTC 版)
「重複組合せ」も参照 濃度 n の有限集合から元をとって作られる濃度 k の多重集合の総数は多重集合（係）数 (multiset coefficient, multiset number) と呼ばれる。この数はしばしば二項係数と似せて ((nk)) と書かれる 多重集合係数の値は ( ( n k ) ) = ( n + k − 1 k ) = ( n + k − 1 ) ! k ! ( n − 1 ) ! = n ( n + 1 ) ( n + 2 ) ⋯ ( n + k − 1 ) k ! {\displaystyle {\begin{aligned}\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{aligned}}} で明示的に与えることができる。ただし、二番目の式は二項係数としての表示である（多重集合を別に定義することを嫌って二項係数としてのみ書く文献も多い）であり、このような多重集合の総数は濃度 n + k − 1 の集合内の k-元部分集合の総数に等しい。二項係数との類似性を見るために、上記の式の分子に上昇階乗冪を用いて ((nk)) = nk⁄k! と書けば、二項係数が下降階乗冪を用いて (nk) = nk⁄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}} と書ける。
※この「多重集合の数え上げ」の解説は、「多重集合」の解説の一部です。
「多重集合の数え上げ」を含む「多重集合」の記事については、「多重集合」の概要を参照ください。
- 多重集合の数え上げのページへのリンク
