解釈と表示
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/26 09:19 UTC 版)
相異なる（つまり区別可能な）n 個の元からなる集合 E = {x1, x2, …, xn}から重複を許して k-元を選ぶ組合せ（k-重複組合せ）とは、E から連続して k 個の元を選ぶ方法であって、選んだ k 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて k 個の元からなる非順序組が得られる（この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる）。そこで元 xi を選ぶ回数（零回でもいい）を f(xi) と書けば、k 個の元を選ぶことは制約条件 f(x1) + f(x2) + … + f(xn) = k で表せるから、 定義 ― 位数（濃度）n の有限集合 E に関する k-重複組合せとは、E から {0, 1, …, k} への写像 f: E → {0, 1, …, k} で条件 ∑ x ∈ E f ( x ) = k {\displaystyle \sum _{x\in E}f(x)=k} を満たすものを言う。 集合 E = {x1, x2, … , xn}に全順序関係 x1 < x2 < … < xn を入れて考えるとき、E に関する k-重複組合せは、以下のような非減少（つまり広義の増大） k-順序組 ( x 1 , … , x 1 ⏟ f ( x 1 ) elements , x 2 , … , x 2 ⏟ f ( x 2 ) elements , … , x n , … , x n ⏟ f ( x n ) elements ) ( ∑ i f ( x i ) = k ) {\displaystyle (\underbrace {x_{1},\ldots ,x_{1}} _{f(x_{1}){\text{ elements}}},\underbrace {x_{2},\ldots ,x_{2}} _{f(x_{2}){\text{ elements}}},\ldots ,\underbrace {x_{n},\ldots ,x_{n}} _{f(x_{n}){\text{ elements}}})\quad (\sum _{i}f(x_{i})=k)} に対応付けられる。逆に、E の元からなる非減少 k-組 (a1, a2, … , ak), つまり a1 ≤ a2 ≤ … ≤ ak を満たすものは、E の各元に対してそれがこの k-組に現れる回数を割り当てることにより、写像 f: E → {0, 1, …, k}; を定める。これが f(x1) + f(x2) + … + f(xn) = k を満たすことは明らかであり、従って f は E に関する k-重複組合せである。 従って、E に関する k-重複組合せ全体の成す集合と {1, 2, …, k} から E への広義単調増大写像全体の成す集合との間に全単射が存在する。
※この「解釈と表示」の解説は、「重複組合せ」の解説の一部です。
「解釈と表示」を含む「重複組合せ」の記事については、「重複組合せ」の概要を参照ください。
- 解釈と表示のページへのリンク
