Stars and Bars Method

直訳すると「星と棒の方法」となりますが，combination with repetition（重複組合せ）の問題，別名multichoose problemまたはstars and bars problemと呼ばれる問題を解く方法です．

例えばりんご，みかん，バナナの3種類が多数ある中から4個を選ぶとします．すると（りんご、みかん、バナナ）の数の組合せは、
①全種類から少なくとも一つは選ぶ場合
(1,1,2),(1,2,1),(2,1,1)
の3通りあります．
②選ばない種類があってもいい場合
(0,0,4),(0,1,3),(0,2,2),(0,3,1),(0,4,0),
(1,0,3),(1,1,2),(1,2,1),(1,3,0),
(2,0,2),(2,1,1),(2,2,0),
(3,0,1),(3,1,0),
(4,0,0)
の15通りと急に多くなります．

種類や選ぶ個数が多くなったらどうするか．ここでstars and bars methodを使います．n種類のものが多数ある中からr個を選ぶとしましょう．

②の場合から先に考えます．これは，r個の★とn-1個の仕切り｜（たて棒）を一列に並べる場合の数，すなわち「2種類の同じものを含む順列」n+r-1Cr=n+r-1Cn-1と同じになります．例えば上の②の場合のいくつかをstars and barsで表すと次のようになります。
(0,0,4)=||★★★★
(1,0,3)=★||★★★
(1,1,2)=★|★|★★
(4,0,0)=★★★★||
2本の仕切りの左側がりんご，間がみかん，右側がバナナと決めておけば，すべて同じ★で表してもいいわけです．n+r-1Crは簡単にnHrと表します．この場合はn=3,r=4なので，3H4=3+4-1C4=6C4=6C2=15と計算できます．

日本の参考書等では★の代わりに○がよく使われていますから，circles and barsといってもいいかも知れません．

①の場合は，まず各種類から1個ずつ選んでおいて，残りのr-n個を②の場合と同様に考えます．すなわち，nHr-n=3H4-3=3H1=3C1=3で求められます．

以上をまとめると，
①全種類から少なくとも一つは選ぶ場合
nHr-n
②選ばない種類があってもいい場合
nHr=n+r-1Cr=n+r-1Cn-1

さて上の果物の問題は，方程式x+y+z=4の整数解の組の個数を求める問題といえます．
①は正の整数解の組の個数を求める場合で，(x,y,z)の組合せは3H4-3=3通りです．
②は負でない整数解の組の個数を求める場合で，(x,y,z)の組合せは3H4=15通りです．
これらの数の組をmultiset（多重集合）といいます．

②の場合，nHrと表しますが，binomial coefficient（二項係数）nCrを$\binom{n}{r}$と書くときは，nHrを$\left(\!\binom{n}{r}\!\right)$と書きます．以上をまとめて式で表すと次のようになります．$$ _n H_r =\left(\!\binom{n}{r}\!\right)= _{n+r-1} C_r=\binom{n+r-1}{r}=\left( n-1, r \right)!=\frac{(n+r-1)!}{(n-1)!r!}$$途中の式$\left( n-1, r \right)!$は，multinomial coefficient（多項係数）の2項の場合の表し方で，多項係数の場合は次の式になります．$$\left(n_{1},n_{2},\cdot\cdot\cdot,n_{k}\right)!=\frac{(n_{1}+n_{2}+\cdot\cdot\cdot+n_{k})!}{n_{1}!n_{2}!\cdot\cdot\cdot n_{k}!}$$
因みに，次数が等しい項だけでできている多項式をhomogeneous polynomial（同次多項式または斉次多項式）といい、このlike term（同類項）の種類の数が重複組合せになります．nHrのHはこのhomogeneousの頭文字から来ています．
（例）x,y,zでできる4次の項
(0,0,4)=||★★★★→z⁴
(1,0,3)=★||★★★→xz³
(1,1,2)=★|★|★★→xyz²
(4,0,0)=★★★★||→x⁴

<Reference>
Multichoose
http://mathworld.wolfram.com/Multichoose.html