Question

组合数学高手请进 计算多重集S={2a1,∞a2,...,∞ak}的r组合的个数

Answer 1

考虑方程x1+x2+...+xk=r.0<=x1<=2.0<=xi.2<=i的非负整数解的个数.
假定x1已知，可把
x1+x2+...+xk=r .0<=x1<=2.0<=xi.2<=i
写为：

x2+...+xk=r-x1 .0<=x1<=2.0<=xi.2<=i
记ai=x(i+1)+1 0<=xi.1<=i<=k-1
有：
a1+a2+a3+...+a(k-1)=r-x1+k-1
方程解的个数问题等于把r-x1+k-1个相同的球分到k-1个不同盒子,且每个盒子至少有一个球的方法数。用隔板法
有C(r-x1+k-1-1,k-1-1)=C(r-x1+k-2,k-2)。
又0<=x1<=2，则总共有：
C(r+k-2,k-2)+C(r-1+k-2,k-2)+C(r-2+k-2,k-2)=

C(r+k-2,k-2)+C(r+k-3,k-2)+C(r+k-4,k-2)

种方法，即原问题答案

追问

没看太明白！

追答

实在不行你考虑它的生成函数，生成函数你应该懂吧？

上面问题的生成函数是：

对后者表达式进行泰勒展开：

一些现在使用的组合数我给出定义：

这里取n=r，就得到我上面写的结果。

不懂再问吧。