從n個元素中有重復地取r個,不計其順序,則不同的取法有C(r,n+r-1)種
很多教材都僅僅給出了公式,但是沒有給出這個公式的證明,這里就給出一種證明,由于本人的語言表述能力欠佳,因此在闡述時顯得十分羅嗦,希望大家能提出意見.
事實上,若將n個元素看做n個盒子,r看作r個同質(zhì)的球,則相當于:
把r個同樣的球放入n個順次排列的盒子,求不計放球順序的放法種數(shù)
把0看作是盒子,1看做是球;
由于球必須放在盒子中,規(guī)定某個0位之前,到上一個0位為止的1的個數(shù),表示該盒子中裝的球數(shù):
則有重復排列數(shù)要求,
在n個0中放入r個1
這樣,就相當于(n-1)個0和r個1的排列數(shù),即(n+r-1)!/n!*(r-1)!
比如:
1110100011111110 (1110 | 10 | 0 | 0 | 11111110) 是n=5,r=11 的一種具體情形
表示第一個盒子裝3個球,因為第一個0前有3個1
第二個盒子裝1個球,因為第二個0到第一個0間有1個1
第三個盒子裝0個球,因為第三個0到第二個0間有0個1
第四個盒子裝0個球,因為第四個0到第三個0間有0個1
第五個盒子裝7個球,因為第屋個0到第五個0間有7個1
詳細一點的解釋是:
若規(guī)定這樣的字段:
1.每個字段可能含有若干個1
2.0代表字段的結束
3.若一個字段只含0不含1,稱之為空字段.
其中,設:
r 為1的個數(shù)
n 為0的個數(shù),也就是字段的數(shù)量(因為0是結束字符,有多少的結束字符就有多少個字段)
則
字符串1100100 表示 110 | 0 | 10 | 0 ,其中r=3,n=4
字符串0101010 表示 0 | 10 | 10 | 10 ,同樣有r=3,n=4
又如 0011010100 表示 0 | 0 | 110 | 10 | 10 | 0 ,其中r=4,n=6
若規(guī)定 110 | 0 | 10 | 0 表示:
第一個元素取2次,第二個元素取0次,第三個元素取1次,第四個元素取0次
則同樣 0 | 10 | 10 | 10 表示:
第一個元素取0次,第二個元素取1次,第三個元素取1次,第四個元素取1次
又如?0 | 0 | 110 | 10 | 10 | 0 表示:
第一個元素取0次,第二個元素取0次,第三個元素取2次,第4個元素取1次,表示第五個元素取1次,第六個元素取1次
則要在n個元素中有重復地取出r個,即是求按上述規(guī)則組成的字段,能排列成多少中不同的字符串.由于字符串的結尾總是0,故相當于(n-1)個0和r個1的組合,即(n+r-1)!/n!*(r-1)!
實際上,這也相當于求方程 X1+X2+...+Xn=r 的自然數(shù)解的個數(shù).