,
n_1, n_2, \cdots, n_k
是每种元素的重复度 ,
该 多重集的
r
组合数 , 是 不定方程
x_1 + x_2 + \cdots + x_k = r
的非负整数解..., 非全排列
k^r , \ \ r\leq n_i
可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N= C(k + r - 1, r)
上述的 多重集
r
组合数
C(k + r...y
的次幂 , 如
a_1
元素的取值个数是
0
到
n_1
, 则该项对应的 生成函数项是 从
y
的
0
次幂 , 到
y
的
n_1
次幂 相加 ; 构成项
(...1 + y + \cdots + y^{n_1})
;
将所有元素的上述 生成函数项 乘到一起 , 就构成上述生成函数 ;
按照多项式乘法 , 多重集中取
r
个元素 ,
从第一个因式
(1 +...y^{r}
, 即
y^{x_1}y^{x_2}\cdots y^{x_k} = y^{r}
, 相当于指数
x_1 + x_2 + \cdots + x_k = r
, 也就是不定方程的非负整数解