一个计数问题

mathe

$O(n^3)$次乘法的复杂度，数值计算还是简单的。

medie2005

题目要求公式,这个可以用生成函数来做,但是,不一定可以解出来. 呵呵,生成函数我不太会.谁要是会的话,做做看能不能解出来.如果解不出,求个渐进解也可以.

mathe

先给个程序，计算第到199项，用HugeCalc:

1. #if 1
2. #define _Test_HI
3. #define integer CHugeInt
4. #else
5. #define _Test_HX
6. #define integer CHugeIntX
7. #endif
9. #define MAX_N 200
10. integer a[MAX_N];
12. int main(int argc, char* argv[])
13. {
14. int i,j;
15. int k;
16. a[2]=1;
17. a[3]=1;
18. a[4]=3;
19. printf("s[3]=1\ns[4]=3\n");
20. for(i=5;i<MAX_N;i++){
21. integer s(0);
22. for(j=2;j<=i-1;j++){
23. s+=a[j]*a[i+1-j];
24. }
25. for(j=3;j<=i-3;j++){
26. s+=2*a[j]*a[i-j];
27. }
28. for(j=2;j<=i-2;j++){
29. s+=a[j]*a[i-j];
30. }
31. for(j=3;j<=i-4;j++){
32. for(k=3;j+k<=i-1;k++){
33. s+=a[k]*a[j]*a[i+2-j-k];
34. }
35. }
36. s+=a[i-2];
37. a[i]=s;
38. printf("f[%d]=%s\n",i,s.GetStrA(FS_NORMAL));
39. }
41. return 0;
42. }

复制代码

... f[197]=11098388607679049922784856861174712980445135599410805814343936736168586799658634862065119439605655074298721447133533462171951086295291460040 f[198]=59475002686299682112461821904032700964129061579974910593128350973093786015287678376730106305411105851387244504428968884408342547739488696840 f[199]=318732125980056493100949536723645898194002586243433747563670398525797268090081459278049422828315128412975229310568707272894999874690598185840

mathe

原帖由 medie2005 于 2008-5-12 20:02 发表 题目要求公式,这个可以用生成函数来做,但是,不一定可以解出来. 呵呵,生成函数我不太会.谁要是会的话,做做看能不能解出来.如果解不出,求个渐进解也可以.

生成函数前面的链接里面有，有了这个结果，验证一下是很简单的

mathe

f[999]=231266893393026464995178230974940141719885668328008586021281799022066498502376256035657167205644776336603283727663662064557277595133908791690550554899156279948682461229493762192868136335830880275690304074310930012430103756390842890446202610175363631665621603026390278350908567042095135944749163145184739094845402956510183027756539036228578215413170479931074942246216459521135241357435058821196260239957324489109358564841270112799596585299696048223690581318771252786477638996500389699284169609254935863872653096748740665135612005485931627323893684152924782424098776736795217269179990844888746324985616453257321857108114429304156567254086094608174150783540695708400905151396317061672596369752794679046299855034116506765626955200

mathe

zgg__给定的链接里面有个公式计算很好用: $5n(n+1) * a(n) = 11n(2n-1) * a(n-1) + 3(3n-2)(3n-4) * a(n-2)$ 其中$a(n)$表示n+2边形的划分数目 用这个可以比较快速的计算比如: f[2000]=1090602909089746111452104751154266485030146921711692771816176083878832474715609893383166693863218771066630553737202122470242937794758640406495004220350860926534452318037389226696604405548578300761713002768555803533600784623097553107142903334081304341697106538947184244115776961753412805577426844543190681119050427288677202255672849495111046581297958157824122279162723042261650136121571956358198924502343324719451312110134500502172201913562722817640375622604514902606497097316158635709815186977446555093809702430605027277643328886576562636392331957086949011065720685302156965766125890689011709279256490640865482972551031789762377927870778907174912007316248904523055222368326366395025722520606677046900919857113357161963718006503948666486374378885230529616849762686631980137265765928912298825824542942910253574643093995403756857469333768093909958970880659560073249777613241210185452494206659231660395372705153630998226970896845576101674432825443981055196279705713168155022528777938793043561111655291910784157131277724943038104627889142138597517797894587523019090587695226358242113256386084413438901776129239634706672017247398861514986881781891592964907257615153604736340012803898537332346643407277068768989466233748340816015275799135228944056186922189385339541523411412703302381149525395998324500161915438547082932777945344346215397201507635690814837925851956283096597174234960387144153436981963995618828717030857766210307308986518239850453260129942590814752000

gxqcn

这个问题原本是在 CSDN 上提出的，但尚未得到有价值的回复； 转到本坛后，很快就从公式推导、算法分析到程序设计一条龙地全面完成， 体现了本论坛的专业。

medie2005

呵呵，mathe给出的方法对计算来说确实很方便． 我现在的疑问是是否存在精确表示n边形的划分数目的公式（而不是递推式）？ 这个可以解生成函数来求，但是，我不太会生成函数，所以，还请mathe看看能不能解出来． 如果解不出来，求一个渐进公式也可以．

mathe

生成函数可以设 $F(x)=x^2+f(3)x^3+...+f(n)x^n+...$ 根据前面我给出的递推式可以得出: $F(x) = {F(x)^2}/x + 2 (F(x)-x^2)^2 + F(x)^2 + {(F(x)-x^2)^3}/{x^2}$ 所以 $x F^2 + 3x^2 F^2-4x^4 F + 2x^4 + F^3 - 3x^2F^2+3x^4F-x^6 -x^2F＝0$ 或者$F(x)^3 + xF(x)^2 -x^2(x^2+1)F(x) +x^4(2-x^2)=0$ 不过生成函数我不觉得有很大的意义

shshsh_0510

zgg的链接不是很清楚了吗？ 隐式的递推mathe已经应用过 显示的如： $a(n)=sum_{k=0}^{[n/2]}1/(n+1)*C_{2*n-k}^{n+k}*C_{n+k}^k$ medie2005还有啥不明白呢？