普通生成函数的系数提取

把两个有限多项式相乘时,乘积中 xn 的系数来自所有满足 i + j = n 的项 aibj。调节 n,观察卷积对角线如何给出 [xn]A(x)B(x)。

[x^n] A(x)B(x) = Σ a_i b_j, i+j=n

选择 n,看乘积中的 xn

也可以点击下方乘积系数或矩阵单元切换 n
3
0 ≤ n ≤ 10
参与相加的项
[x^3] A(x)B(x)
0
乘积多项式的各项系数

卷积矩阵

同一条对角线上的单元格满足 i + j = n,它们的和就是目标系数

先展开

A(x)B(x) 中每一项来自 aixi 与 bjxj 的乘积,指数相加得到 xi+j

再收集

要找 xn 的系数,只收集所有 i + j = n 的乘积 aibj

这就是卷积

系数序列相乘时,乘积系数 cn = a0bn + a1bn-1 + ... + anb0