从m个不同元素中取n个可重复元素,为什么是C(m+n-1,m)这是一个不定方程x1+x2+...+xn=m非负整数解为C(m+n-1,m)的推论,不知道怎么来的

Question

从m个不同元素中取n个可重复元素,为什么是C(m+n-1,m)
这是一个不定方程x1+x2+...+xn=m非负整数解为C(m+n-1,m)的推论,不知道怎么来的

Answer 1

可以这样
x1+x2+...+xn=m
(x1+1)+(x2+1)+.+(xn+1)=m+n
即不定方程
y1+y2+.+yn=m+n
的正整数解的个数,
是1个挡板问题,相当于将m+n个小球放入n个盒子中,每个盒子不空,
相当于在m+n个小球间插入 n-1个挡板
即 C(m+n-1,n-1)=C(m+n-1,m)