直訳すると「星と棒の方法」となりますが,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-1C
r=
n+r-1C
n-1と同じになります.例えば上の②の場合のいくつかをstars and barsで表すと次のようになります。
(0,0,4)=||★★★★
(1,0,3)=★||★★★
(1,1,2)=★|★|★★
(4,0,0)=★★★★||
2本の仕切りの左側がりんご,間がみかん,右側がバナナと決めておけば,すべて同じ★で表してもいいわけです.
n+r-1C
rは簡単に
nH
rと表します.この場合はn=3,r=4なので,
3H
4=
3+4-1C
4=
6C
4=
6C
2=15と計算できます.
日本の参考書等では★の代わりに○がよく使われていますから,circles and barsといってもいいかも知れません.
①の場合は,まず各種類から1個ずつ選んでおいて,残りのr-n個を②の場合と同様に考えます.すなわち,
nH
r-n=
3H4-3=
3H1=
3C
1=3で求められます.
以上をまとめると,
①全種類から少なくとも一つは選ぶ場合
nH
r-n
②選ばない種類があってもいい場合
nH
r=
n+r-1C
r=
n+r-1C
n-1
さて上の果物の問題は,方程式x+y+z=4の整数解の組の個数を求める問題といえます.
①は正の整数解の組の個数を求める場合で,(x,y,z)の組合せは
3H4-3=3通りです.
②は負でない整数解の組の個数を求める場合で,(x,y,z)の組合せは
3H
4=15通りです.
これらの数の組をmultiset(多重集合)といいます.
②の場合,
nH
rと表しますが,binomial coefficient(二項係数)
nC
rを$\binom{n}{r}$と書くときは,
nH
rを$\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(同類項)の種類の数が重複組合せになります.
nH
rのHはこのhomogeneousの頭文字から来ています.
(例)x,y,zでできる4次の項
(0,0,4)=||★★★★→z
4
(1,0,3)=★||★★★→xz
3
(1,1,2)=★|★|★★→xyz
2
(4,0,0)=★★★★||→x
4
<Reference>
Multichoose
http://mathworld.wolfram.com/Multichoose.html