重複組み合わせ

デジタル大辞泉

ちょうふく‐くみあわせ〔‐くみあはせ〕【重複組（み）合（わ）せ】

読み方：ちょうふくくみあわせ

n個のものから、同じものを何回でも取ることを許して、r個取る組み合わせ。その総数は_nH_rと表され、_nH_r＝_n＋r−1C_r＝（n＋r−1）!/（n−1）!r!となる。

ウィキペディア

重複組合せ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/28 03:18 UTC 版)

数学の一分野である組合せ論における重複組合せ（ちょうふくくみあわせ、じゅうふくくみあわせ、英: combination with repetition, multi-choose; 重複選択、"Stars and bars"）とは、取り出した元の並びは考慮しないが、（通常の（非重複）組合せと異なり）同じ元を複数取り出すことが許される「組合せ」を言う。例えば、（通常の）サイコロを10回投げるとき、各出目が何回目に振ったときに出たものか考えなければ、サイコロの出目の「組合せ」となるが、各面のうちには複数回現れるものが存在することになる（たとえば、出目 2 が1回、4 が3回、5 が2回、6 が4回であるときがその一例である）。

解釈と表示

区別可能な n個の元からなる集合 E = {x₁, x₂, …, x_n} から重複を許して k-元を選ぶ組合せ（k-重複組合せ）とは、E から連続して k 個の元を選ぶ方法であって、選んだ k 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて k 個の元からなる非順序組が得られる（この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる）。そこで元 x_i を選ぶ回数（零回でもいい）を f(x_i) と書けば、k 個の元を選ぶことは制約条件 f(x₁) + f(x₂) + … + f(x_n) = k で表せるから、

定義 ― 位数（濃度）n の有限集合 E に関する k-重複組合せとは、E から {0, 1, …, k} への写像 f: E → {0, 1, …, k} で条件

${\displaystyle \textstyle \sum \limits _{x\in E}f(x)=k}$

ポータル 数学