论坛 › 难题征解 › 一个计数问题

mathe 发表于 2008-5-12 19:56:27

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

medie2005 发表于 2008-5-12 20:02:34

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

mathe 发表于 2008-5-12 21:16:35

先给个程序，计算第到199项，用HugeCalc:#if 1
    #define _Test_HI
    #define integer CHugeInt
#else
    #define _Test_HX
    #define integer CHugeIntX
#endif

#define MAX_N200
integer a;

int main(int argc, char* argv[])
{
    int i,j;
    int k;
    a=1;
    a=1;
    a=3;
    printf("s=1\ns=3\n");
    for(i=5;i<MAX_N;i++){
      integer s(0);
      for(j=2;j<=i-1;j++){
            s+=a*a;
      }
      for(j=3;j<=i-3;j++){
            s+=2*a*a;
      }
      for(j=2;j<=i-2;j++){
            s+=a*a;
      }
      for(j=3;j<=i-4;j++){
            for(k=3;j+k<=i-1;k++){
                s+=a*a*a;
            }
      }
      s+=a;
      a=s;
      printf("f[%d]=%s\n",i,s.GetStrA(FS_NORMAL));
    }

    return 0;
}...
f=11098388607679049922784856861174712980445135599410805814343936736168586799658634862065119439605655074298721447133533462171951086295291460040
f=59475002686299682112461821904032700964129061579974910593128350973093786015287678376730106305411105851387244504428968884408342547739488696840
f=318732125980056493100949536723645898194002586243433747563670398525797268090081459278049422828315128412975229310568707272894999874690598185840

mathe 发表于 2008-5-12 21:22:05

原帖由 medie2005 于 2008-5-12 20:02 发表 http://images.5d6d.net/dz60/common/back.gif
题目要求公式,这个可以用生成函数来做,但是,不一定可以解出来.
呵呵,生成函数我不太会.谁要是会的话,做做看能不能解出来.如果解不出,求个渐进解也可以.
生成函数前面的链接里面有，有了这个结果，验证一下是很简单的

mathe 发表于 2008-5-12 22:19:39

f=231266893393026464995178230974940141719885668328008586021281799022066498502376256035657167205644776336603283727663662064557277595133908791690550554899156279948682461229493762192868136335830880275690304074310930012430103756390842890446202610175363631665621603026390278350908567042095135944749163145184739094845402956510183027756539036228578215413170479931074942246216459521135241357435058821196260239957324489109358564841270112799596585299696048223690581318771252786477638996500389699284169609254935863872653096748740665135612005485931627323893684152924782424098776736795217269179990844888746324985616453257321857108114429304156567254086094608174150783540695708400905151396317061672596369752794679046299855034116506765626955200

mathe 发表于 2008-5-13 08:24:03

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=1090602909089746111452104751154266485030146921711692771816176083878832474715609893383166693863218771066630553737202122470242937794758640406495004220350860926534452318037389226696604405548578300761713002768555803533600784623097553107142903334081304341697106538947184244115776961753412805577426844543190681119050427288677202255672849495111046581297958157824122279162723042261650136121571956358198924502343324719451312110134500502172201913562722817640375622604514902606497097316158635709815186977446555093809702430605027277643328886576562636392331957086949011065720685302156965766125890689011709279256490640865482972551031789762377927870778907174912007316248904523055222368326366395025722520606677046900919857113357161963718006503948666486374378885230529616849762686631980137265765928912298825824542942910253574643093995403756857469333768093909958970880659560073249777613241210185452494206659231660395372705153630998226970896845576101674432825443981055196279705713168155022528777938793043561111655291910784157131277724943038104627889142138597517797894587523019090587695226358242113256386084413438901776129239634706672017247398861514986881781891592964907257615153604736340012803898537332346643407277068768989466233748340816015275799135228944056186922189385339541523411412703302381149525395998324500161915438547082932777945344346215397201507635690814837925851956283096597174234960387144153436981963995618828717030857766210307308986518239850453260129942590814752000

gxqcn 发表于 2008-5-13 08:46:45

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

medie2005 发表于 2008-5-13 08:56:55

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

mathe 发表于 2008-5-13 09:04:40

生成函数可以设
$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 发表于 2008-5-13 12:54:16

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

查看完整版本: 一个计数问题