微分有限生成函数
mistakes
·
·
个人记录
1.整式递推
若\sum_{i=0} ^{k}q_i(p)a_{p-i}=0 则称\{q(x)\} 为 树列\{a\} 的整式递推式数列
2.微分有限生成函数
若\sum_{i=0}^{k} r(p)A^{(p-i)}=0 则称生成函数&/{A(x)/}&为一个微分有限生成函数
整式递推判定定理与性质定理
一个数列的生成函数是微分有限生成函数是该数列是整式递推数列的充分必要条件
证明
充分性：
发现若使式\sum_{i=0}^{k} r(p)A^{(p-i)}=0 变为式\sum_{i=0} ^{k}q_i(p)a_{p-i}=0 只需构造一个k次的多项式生成函数作为系数即可 故得证
必要性：
同理
定理的应用
P8354
考虑如何O(a)计算式
F_a(x)=\sum_{i=0}^a\sum_{k=i}^a(-1)^{k-i}\binom{a}{k}\binom{i+1}{k-i}x^i
F_a(x)=\sum_{i=0}^a[z^{a-i}](1+z)^a(1-z)^{i+1}x^i
记G_k(x)=(1+x)^a(1-x)^k
注意到G_k(x)是微分有限的
于是
(1-x^2)G'_k(x)=a(1-x)G_k(x)-k(1+x)G_k(x)=(a-k)G_k(x)-(a+k)xG_k(x)
\\
(i+1)g_{i+1}=(a-k)g_i-(a+k-i+1)g_{i-1}
\\
又
\\
F_a(x)=\sum_{i=0}^a[z^{a-i-1}]G_i(z)x^i
\\
F_a(x)=\sum_{i=0}^ag_{i|a-i-1}x^i
\\
又有G_{k+1}(x)=(1-x)G_k(x)
\\
于是可以先推出G_k的3项 再推出G_{k+1}的两项
\\
于是可以轻易做到O(a)