从n
个不同元素中有放回的取出r
个且不计顺序,有多少种不同的取法?
答案是:\(C_{n+r-1}^r\)
解析
因为是有放回地取出,所以同一个元素可能会被取多次,并且取出的元素是不计顺序的,那么如果我们设\(x_i\)为第\(i\)个元素被取出的次数,问题就被转化为:
\[\begin{aligned} x_1+x_2+\cdots +x_n=r\\ x_i\ge0,1\le i\le n \end{aligned} \]求以上\((x_1,x_2,\dots,x_n)\)解的个数。
注意到\(x_i\ge 0\),这时对答案的求解仍然不是很直观。如果再进行一次转化:
\[(x_1+1)+(x_2+1)+\cdots+(x_n+1)=r+n \]如果设\(y_i=x_i+1\),那么问题再一次转化:
\[\begin{aligned} y_1+y_2+\cdots +y_n=r+n\\ y_i>0,1\le i\le n \end{aligned} \]求\((y_1,y_2,\dots,y_n)\)解的个数
注意到,\(y_i>0\)
此时问题相当于,有r+n
个苹果摆成一行,我们用小棍子将它们分割为n个部分,每个部分必须有苹果。比如说用O
代表苹果,|
代表棍子,那么当\(n=4,r=1\)时,可能有以下分割方式:
这时,棍子将苹果分为4个部分,分别为1,2,1,1,那么此时,\((1,2,1,1)\)就是\((y_1,y_2,y_3,y_4)\)的一组解
所以,n+r
个苹果,有n+r-1
个空隙,我们要将这一排苹果分为n
个部分,那么需要n-1
个棍子,也就是从n+r-1
个空隙中选择n-1
个去插棍子,此时方案数为\(C_{n+r-1}^{n-1}\),也就是\(C_{n+r-1}^r\)