一个计数问题

medie2005

我要的并不仅仅是一个结果.
我要的是通过解生成函数,求得的a(n)的表达式的过程.(如果解不出,渐进解也可以接受).

shshsh_0510

噢，是个爱学习的
我记得第一次看到这个好像是在卢开澄的那本“组合数学”吧，你找找看

mathe

渐近式也挺难的。
我发现对于任意正实数$C$，对于充分大的n,必然有$f(n)<C*5.4^n$.
但是对于任意$t<5.4$,那么对于充分大的n,必然有$f(n)>C*t^n$
也就是增长速度略低于$C*5.4^n$

zgg___

当n趋于无穷时，a(n+1)/a(n)=27/5。

zgg___

我们可以看到：当n趋于无穷时，递推公式就变成了5*a(n)=22*a(n-1)+27a(n-2)，
如果假设此时a(n)成为等比数列c*d^n，那么有5*d^2=22*d+27，所以d=27/5。
即：当n趋于无穷时，a(n+1)/a(n)=27/5。
但是此时的c好像很难求，猜想当n趋于无穷时，c=a(n)/(27/5)^n趋于0。

zgg___

渐进式貌似为：$c*n^(-3/2)(27/5)^n$。看看能不能求出系数c来。

mathe

原帖由 zgg___ 于 2008-5-13 17:03 发表
渐进式貌似为：$c*n^(-3/2)(27/5)^n$。看看能不能求出系数c来。

如何得出$n^{-3/2}$

zgg___

是蒙的，先用1/n和1/n^2，代入递推公式求极限，发现指数介于之间，然后就中着了，呵呵。

mathe

$27^2(n^2+n)(c_0+{c_1}/n+{c_2}/n^2+{c_3}/n^3+...)=27*11*(2n^2-n)*(c_0+{c_1}/n+{c_1}/n^2+{c_1}/n^3+{c_2}/n^2+2{c_2}/n^3+{c_3}/n^3+...)+15(9n^2-18n+8)(c_0+{c_1}/n+2{c_1}/n^2+4{c_1}/n^3+{c_2}/n^2+4{c_2}/n^3+{c_3}/n^3+...)$
这个式子谁来化简一下，计算出c1,c2,c3?

mathe

zgg__的结论应该是正确的。不过计算比较难。