从n个不同元素中有放回的取出r个且不计顺序，有多少种不同的取法?
阿里云国际版折扣https://www.yundadi.com |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
从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+\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+\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\)
阿里云国际版折扣https://www.yundadi.com |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |