重複組合せのソースを表示

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

== 解釈と表示 ==
区別可能な {{mvar|n}}個の元からなる[[集合]] {{math2|1=''E'' = {{mset|''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}''}}}} から重複を許して {{mvar|k}}-元を選ぶ組合せ（{{mvar|k}}-重複組合せ）とは、{{mvar|E}} から連続して {{mvar|k}} 個の元を選ぶ方法であって、選んだ {{mvar|k}} 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて {{mvar|k}} 個の元からなる非順序組が得られる（この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した[[多重集合]]となる）。そこで元 {{mvar|x{{sub|i}}}} を選ぶ回数（零回でもいい）を {{math|''f''(''x''{{sub|''i''}})}} と書けば、{{mvar|k}} 個の元を選ぶことは制約条件 {{math2|1=''f''(''x''{{sub|1}}) + ''f''(''x''{{sub|2}}) + … + ''f''(''x{{sub|n}}'') = ''k''}} で表せるから、
{{math theorem|定義|位数（濃度）{{mvar|n}} の有限集合 {{mvar|E}} に関する''' {{mvar|k}}-重複組合せ'''とは、{{mvar|E}} から {{math2|{0, 1, …, ''k''} }}への写像 {{math2|''f'': ''E'' → {0, 1, …, ''k''} }}で条件
:<math>\textstyle\sum\limits_{x\in E}f(x)=k</math>
を満たすものを言う。
}}

集合 {{math2|1=''E'' = {{mset|''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}''}}}} に[[全順序]]関係 {{math2|''x''{{sub|1}} < ''x''{{sub|2}} < … < ''x{{sub|n}}''}} を入れて考えるとき、{{mvar|E}} に関する {{mvar|k}}-重複組合せは、以下のような[[単調写像|非減少（つまり広義の増大）]] {{mvar|k}}-[[順序組]]
:<math>(\underbrace{x_1, \cdots, x_1}_{f(x_1) \text{ elements}}, \underbrace{x_2, \cdots, x_2}_{f(x_2) \text{ elements}}, \cdots, \underbrace{x_n, \cdots, x_n}_{f(x_n) \text{ elements}})\qquad (\textstyle\sum\limits_i f(x_i)=k)</math>
に対応付けられる。逆に、{{mvar|E}} の元からなる非減少 {{mvar|k}}-組 {{math|(''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|k}}'')}}, つまり
:{{math2|''a''{{sub|1}} ≤ ''a''{{sub|2}} ≤ … ≤ ''a{{sub|k}}''}}
を満たすものは、{{mvar|E}} の各元に対してそれがこの {{mvar|k}}-組に現れる回数を割り当てることにより、写像 {{math2|''f'': ''E'' → {0, 1, …, ''k''} }}を定める。これが  
:{{math|1=''f''(''x''{{sub|1}}) + ''f''(''x''{{sub|2}}) + … + ''f''(''x{{sub|n}}'') = ''k''}}
を満たすことは明らかであり、従って {{mvar|f}} は {{mvar|E}} に関する {{mvar|k}}-重複組合せである。

従って、{{mvar|E}} に関する {{mvar|k}}-重複組合せ全体の成す集合と {{math2|{1, 2, …, ''k''} }}から {{mvar|E}} への広義単調増大写像全体の成す集合との間に[[全単射]]が存在する。

== 重複組合せの総数 ==
{{main|{{仮リンク|多重集合係数|en|Multiset coefficient}}}}
{{math theorem|定理<ref>{{MathWorld |urlname=Multichoose |title=Multichoose}}</ref>|正整数 {{mvar|n}} に対して {{mvar|n}}個の元からなる集合に関する {{mvar|k}}-重複組合せの総数を {{math|H{{su|p=''n''|b=''k''}}}} と書けば、
:<math>\text{H}_k^n = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!~(n-1)!}</math>
（すなわち、{{math2|''n'' + ''k'' &minus; 1}} 個の元に関する {{mvar|k}}-[[組合せ (数学)|組合せ]]の総数）に等しい。
}}
{{math proof|title=証明 1（漸化式を用いる方法）|drop=yes|1=
{{math|1=''E'' = {{mset|''x''{{sub|1}}, ''x''{{sub|2}}, …, ''x{{sub|n}}''}}}} とする。{{mvar|E}} に関する元 {{math|''x''{{sub|1}}}} を含まない {{mvar|k}}-重複組合せは、{{math2|{{mset|''x''{{sub|2}}, … , ''x{{sub|n}}''}}}} に関する {{mvar|k}}-重複組合せであるからその総数は {{math|{{su|H|''k''|''n''&minus;1}}}} である。一方、{{math|''x''{{sub|1}}}} を（少なくとも1つ）含む {{mvar|k}}-重複組合せは、{{mvar|E}} に関する任意の {{math|''n'' &minus; 1}}-重複組合せに {{math|''x''{{sub|1}}}} を1つ付け加えることで得られるから、その総数は {{math|H{{su|p=''n''|b=''k''&minus;1}}}} である。これら2つで {{mvar|E}} に関する {{mvar|k}}-重複組合せは全て数え上げられるから、任意の {{math2|''n'' > 1}} および {{math2|''k'' > 0}} に対して[[漸化式]]
:<math>\text{H}^n_k = \text{H}^n_{k-1} + \text{H}^{n-1}_k</math>
が成り立つ<ref name="Esch"/>。任意の非負整数 {{mvar|k}} に対して {{math2|1=H{{su|p=1|b=''k''}} = 1}} および正整数 {{mvar|n}} に対して {{math2|1=H{{su|p=''n''|b=0}} = 1}} に注意すれば、{{math2|''n'' + ''k''}} に関する帰納法により所期の結果を得る。
}}
{{math proof|title=証明 2（単調増大列に帰着する方法）|drop=yes|1=
{{math2|1=''E'' = {{mset|1, 2, …, ''n''}}}} としても[[一般性を失わない]]。{{mvar|E}} に関する {{mvar|k}}-重複組合せを、{{math2|''a''{{sub|1}} ≤ ''a''{{sub|2}} ≤ … ≤ ''a{{sub|k}}''}} なる非減少 {{mvar|k}}-組と看做すとき、これは
: {{math2|1=''b''{{sub|1}} = ''a''{{sub|1}} + 0, ''b''{{sub|2}} = ''a''{{sub|2}} + 1,  …, ''b{{sub|k}} = a{{sub|k}}'' + ''k'' &minus; 1}}
と置いて得られる {{mvar|k}}組を考えることにより、集合 {{math2|{1, 2, …, ''n'' + ''k'' – 1} }}に関する狭義単調増大 {{mvar|k}}-組 {{math2|''b''{{sub|1}} < ''b''{{sub|2}} < … < ''b{{sub|k}}''}} と一対一に対応する<ref>{{Cite book |author=A. Bégyn |author2=G. Connan |author3=R. Leroy |editor=[[Dunod]] |title=Mathématiques Méthodes et Exercices [[BCPST]] {{1re}} année |url={{google books|id=bXyoAAAAQBAJ|pg=226|plainurl=yes}} |volume=2 |year=2013 |page=226}}</ref>。後者は {{math2|''n'' + ''k'' &minus; 1}} 個の元から重複を許すことなく {{mvar|k}}個の元を選ぶ[[組合せ (数学)|組合せ]]に[[全単射|一対一対応]]するから、その総数 ({{math2|1== H{{su|p=''n''|b=''k''}}}}) は[[二項係数]]
:<math>\binom{n+k-1}{k}</math>
で与えられる。
}}
{{math proof|title=証明 3（特定の元が現れる回数を数える方法）|drop=yes|1= 
証明 1 と同様に{{仮リンク|2通りに数える論法|fr|double dénombrement}}<ref>Démonstration tirée de {{Cite book |first1=P.|last1=Louquet |first2=A. |last2=Vogt |editor=[[Armand Colin]] |title=Probabilités, Combinatoire, Statistiques |year=1971}}</ref>による。

{{mvar|n}} 個の元からなる集合 {{mvar|E}} に関する {{mvar|k}}-重複組合せ {{math|H{{su|p=''n''|b=''k''}}}} 個を（元の並びとして）全て書き出すと、その一覧には {{mvar|E}} の元が {{math|''k'' × H{{su|p=''n''|b=''k''}}}} 個現れることになる。{{mvar|E}} の元は対称的に現れるから、各々は {{math|''k'' × H{{su|p=''n''|b=''k''}} / ''n''}} 回現れる。(1)

そこで {{mvar|E}} の元の一つを {{mvar|x}} と書いて、以下それが現れる回数を計算する。
* 全部で {{math|H{{su|p=''n''|b=''k''}}}} 個ある重複組合せのうちで {{mvar|x}} を（1つでも）含むものの数は  {{math|H{{su|p=''n''|b=''k''&minus;1}}}} である。実際、{{mvar|x}} を1つ取り除いた残りは（重複度込みで、順番を無視して）{{math2|''k'' &minus; 1}} 個の元だが、それは（{{mvar|x}} は重複することができるから、選択肢からは除かれず）{{mvar|E}} の任意の元から選べる。{{mvar|x}} を少なくとも1つ含む重複組合せが {{math|H{{su|p=''n''|b=''k''&minus;1}}}} 個あるということは、{{mvar|x}} が少なくとも {{math|H{{su|p=''n''|b=''k''&minus;1}}}} 個は既に現れてることを保証する。(2) 
* 全部で {{math|{{subsup|H|''k''&minus;1|''n''}}}} 個ある少なくとも一つ {{mvar|x}} を含む重複組合せの各々から元 {{mvar|x}} を1つ取り除くと、残りは（重複度を込めて）{{math|''k'' &minus;1}} 個の元（これらの元の各々はもはや重複するとは限らない）だから、そのような組合せの一覧には {{math|(''k'' – 1) × {{subsup|H|''k''–1|''n''}}}} 個の {{mvar|E}} の元が現れる。{{mvar|E}} の各元（特に {{mvar|x}}）は対称的に現れるから、{{mvar|x}} は {{math2|(''k'' &minus; 1) × H{{su|p=''n''|b=''k''&minus;1}} / ''n''}} 回生じる (3). 

2通りに数えた方法を比較すると (1) = (2) + (3) であるから
:<math>\frac{k}{n} \text{H}^n_k = \text{H}^n_{k-1} + \frac{k-1}{n} \text{H}^n_{k-1}</math>
となり、整理すれば
:<math>\text{H}^n_k = \frac{n+k-1}{k} \text{H}^n_{k-1}</math>
を得る。{{math2|1=H{{su|p=''n''|b=0}} = 1}} に注意すれば、{{mvar|k}} に関して帰納的に所期の式を得る。
}}
{{math proof|title=証明 4（組分けに帰着する方法）|drop=yes|1=
{{main|{{仮リンク|マルと仕切りの論法|en|Stars and bars (combinatorics)}}}}
{{mvar|n}} 個の元を {{math|1, 2, …, ''n''}} として、{{mvar|k}}-重複組合せを、{{math|1}} を{{math|''k''{{sub|1}}}} 個、{{math|2}} を {{math|''k''{{sub|2}}}} 個、と以下同様に（{{math2|1=''k''{{sub|1}} + ''k''{{sub|2}} + … + ''k{{sub|n}}'' = ''k''}} となるように取って）作るものとすれば、これは以下のように {{mvar|k}} 個のマル "●" と{{math|''n'' &minus; 1}} 個の仕切り "{{!}}" の並び
: {{underset|{{math|''k''{{sub|1}}}} 個|●…●}} {{!}} {{underset|{{math|''k''{{sub|2}}}} 個|●…●}} {{!}} … {{!}} {{underset|{{mvar|k{{sub|n}}}} 個|●…●}}
で一対一に表すことができる。ここで {{mvar|k}} 個のマルは互いに区別できないし、{{math2|''n'' &minus; 1}} 個の仕切り棒も互いに区別不能であるから、このような「表示」の総数 ({{math|1== H{{su|p=''n''|b=''k''}}}}) は {{math2|''n'' + ''k'' &minus; 1}} 個の元の[[重複置換]]の総数であり、これは[[多項係数]]
:<math>\binom{n+k-1}{k,\,n-1} = \frac{(n+k-1)!}{k!~(n-1)!}</math>
で与えられる<ref name="Esch">{{Cite book |title=Mathématique pour économistes et gestionnaires|auteur=Louis Esch |editor=[[De Boeck]] |url={{google books|id=do0OLK5v-L8C|page=21|plainurl=1}} |year=2010}}</ref>。あるいはまた、{{mvar|k}}個のマルの入る「場所」を {{math2|''n'' + ''k'' &minus; 1}} 箇所から選ぶと考えれば、証明 2 と同様に二項係数
:<math>\binom{n+k-1}{k}</math>
によっても数えられる<ref>{{Cite book |author=Dany-Jack Mercier |editor=Publibook |title=L'épreuve d'exposé au [[CAPES]] mathématiques |url={{google books|id=3gZkWHnhOZoC|page=65|plainurl=1}} |year=2004 |page=65}}</ref>。
}}
重複組合せの総数を計算する最も効果的で単純な方法は、非重複組合せの総数を計算する方法を用いることである（[[組合せ (数学)]]を参照）。実際、上で述べたように {{mvar|n}}個の元から重複を許して {{mvar|k}}個の元を選ぶ組合せの総数は、{{math2|''n'' + ''k'' &minus; 1}} 個の元から {{mvar|k}}個の元を重複を許さずに選ぶ組合せの総数に等しい。

;上昇階乗冪による表現
: 重複組合せの総数は、区別のある {{mvar|n}}個の箱に”区別のない” {{mvar|k}}枚のカードを入れる（1つの箱に複数枚入れてもよい）ときの場合の数である。まず、区別のある {{mvar|n}}個の箱に”区別のある” {{mvar|k}}枚のカードを入れる場合の数を求める。ただし箱の中のカードの相対的な位置も区別して数える。１枚目のカードの入れ方は {{mvar|n}} 通り、2枚目は1枚目のカードの上下どちらに入れるかの選択肢も増えるので入れ方は {{math|''n'' + 1}} 通り、3枚目はさらに選択肢が増え {{math2|''n'' + 2}} 通り。結局 {{mvar|k}} 枚の入れ方の総数は上昇階乗冪 <math>n^\overline{k}=n(n+1)(n+2)\cdots(n+k-1)</math> である。これは重複組合せの総数に {{mvar|k}} 枚のカードの順列の総数 {{mvar|k!}} をかけたものに等しいので、重複組合せの総数は <math>n^\overline{k}/k!</math> である。（組合せの総数が下降階乗冪を用いて <math>n^\underline{k}/k!</math> となるのと対をなしている。）

== その他の重複組合せに同値な数え上げ ==
{{math|H{{su|p=''n''|b=''k''}}}} は[[多変数多項式]]に関する全次数 {{mvar|k}} の単位単項式（つまり係数 {{math|1}} の単項式）の総数に等しい。

同様に {{math|H{{su|p=''n''|b=''k''}}}} は[[シュヴァルツの定理]]（偏微分は微分する変数の順番に依らず等しい）の成立する {{mvar|C{{sup|k}}}}級の {{mvar|n}}変数函数に対する {{mvar|k}}階偏導函数の総数に等しい（順番を考慮する必要があるときには {{mvar|n{{sup|k}}}} 通りである）。

== 出典 ==
{{脚注ヘルプ}}
{{Reflist|2}}

== 関連項目 ==
{{Div col}}
* [[重複置換]]
* [[組合せ (数学)]]
* [[写像12相]]
* [[重複順列]]
* [[順列]]
* [[置換 (数学)]]
{{Div col end}}

== 外部リンク ==
* {{高校数学の美しい物語|1101|重複組合せの公式と例題（玉，整数解の個数）}}
* {{Cite web |author=Michel Hort |title=Nombre de combinaisons et d’arrangements avec répétitions limitées |url=https://archive.wikiwix.com/cache/index2.php?url=http%3A%2F%2Fwww.le-triangle-et-ses-calculs.ch%2Findex_repetitions_limitees.php#federation=archive.wikiwix.com&tab=url |accessdate=2024-06-28}}

{{Portal|数学}}
{{DEFAULTSORT:ちようふくくみあわせ}}
[[Category:組合せ論]]
[[Category:数学に関する記事]]