首页 > 其他分享 >从n个不同元素中有放回的取出r个且不计顺序,有多少种不同的取法?

从n个不同元素中有放回的取出r个且不计顺序,有多少种不同的取法?

时间:2023-06-14 14:01:49浏览次数:41  
标签:le 放回 个且 元素 取法 取出 aligned 棍子 苹果

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\)时,可能有以下分割方式:

\[O|OO|O|O \]

这时,棍子将苹果分为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\)

标签:le,放回,个且,元素,取法,取出,aligned,棍子,苹果
From: https://www.cnblogs.com/NonName/p/17479993.html

相关文章