多项式展开的项数计算。假设
f ( x ) = ( x 1 + n 2 + . . . + x n ) k f(x) = (x_1+n_2+...+x_n)^k f(x)=(x1+n2+...+xn)k
求不同的项数目,例如 x 1 k x_1^k x1k, x 2 k x_2^k x2k和 x 1 1 x 2 k − 1 x_1^1x_2^{k-1} x11x2k−1是不同的项。
用排列组合的知识,一共有两个步骤。
选定变量
x i k x_i^k xik次幂的项数可以看作是从 [ x 1 , x 2 , . . . , x n ] [x_1, x_2, ...,x_n] [x1,x2,...,xn]中选择一变量,一共 n n n个选择。 x i a x j k − a x_i^ax_j^{k-a} xiaxjk−a是选择两项, n ∗ ( n − 1 ) 2 frac{n*(n-1)}{2} 2n∗(n−1), 依次类推每m个变量组成的单项式可以有 C n m C_n^m Cnm种选择。
分配每个变量的幂
在选定变量之后,就需要指定次幂。假设我们已经选定 m m m个变量, m m m个变量幂的和为 k k k。用插挡板的办法得到,在 k k k个小球中插入 m − 1 m-1 m−1个挡板将其划分为 m m m个区间,每个区间的值就是对应变量的次幂,也就是 k − 1 k-1 k−1个位置中选择 m − 1 m-1 m−1个位置,共有 C k − 1 m − 1 C_{k-1}^{m-1} Ck−1m−1种划分办法。
合起来, f ( x ) = ( x 1 + n 2 + . . . + x n ) k f(x) = (x_1+n_2+...+x_n)^k f(x)=(x1+n2+...+xn)k项数公式表示为
∑ i = 1 k C n i C k − 1 i − 1 sum_{i=1}^{k} C_n^iC_{k-1}^{i-1} i=1∑kCniCk−1i−1
Python实现
from functools import reducefrom operator import muldef combination(n, k): if k == 0 or k == n: return 1 dividend = reduce(mul, (i for i in range(n-k+1, n+1))) divisor = reduce(mul, (i for i in range(1, k+1))) return dividend/divisordef nums_of_polynomial(n, k): # n是变量数, k是次幂 total = 0 for i in range(1, k+1): total += combination(n, i)*combination(k-1, i-1) return int(total)