#In Loving memory of Philippe FLAJOLET #(Dec. 1, 1948- March 22, 2011) Digits:=20: Help:=proc(): print(`Test1(a,N) , Test2(a,b,n) `): print(`Shar(N) , GuessAsy(L,a), s(z,N)`): end: #Test1(a,N): inputs a real number and outputs #the ratio of the coeff. of z^n in (1-z)^(-a) #by n^(a-1)*Gamma(a) for n from 1 to N Test1:=proc(a,N) local f,z,L: f:=(1-z)^(-a): f:=taylor(f,z=0,N+1): L:= [seq(coeff(f,z,i),i=1..N)]: L:= evalf([seq(L[i]/i^(a-1)*GAMMA(a),i=1..N)]): end: #Test2(a,b,N): inputs a real number and outputs #the ratio of the coeff. of z^n in #(1-z)^(-a)*(-log(1-z)/z)^b #by n^(a-1)/Gamma(a)*log(n)^b for n from 1 to N Test2:=proc(a,b,N) local f,z,L: f:=(1-z)^(-a)*((-log(1-z))/z)^b: f:=taylor(f,z=0,N+1): L:= [seq(coeff(f,z,i),i=1..N)]: L:= evalf([seq(L[i]/i^(a-1)*GAMMA(a)/log(i)^b,i=1..N)]): end: #Test3(N): tests example 2 in P. Flajolet's ICM 2002 paper Test3:=proc(N) #Homework end: #f(z)=P(z)/Q(z) iff f(z)*P(z)-Q(z)=0 #Shar(N) the first N Catalan Numbers #f(z)=1+z*f(z)^2 Shar:=proc(N) local f,i,i1,z: f:=1: for i from 1 to N do f:=1+z*f^2: f:=add(coeff(f,z,i1)*z^i1,i1=0..N): od: [seq(coeff(f,z,i),i=1..N)]: end: #GuessAsy(L,a): guess beta such that #L[i+1]/L[i]/a^n tends to n^(beta) #C*(n^beta) ~ M[n] #log(C)+ beta*log(n)=log(M[n]) GuessAsy:=proc(L,a) local i,L1,M,x: M:=evalf([seq(L[i]/a^i,i=1..nops(L)-1)]): L1:=[ seq( [ evalf(log(n)),evalf(log(M[n]))], n=1..nops(L)-1)]: coeff(CurveFitting[LeastSquares](L1,x),x,1): end: #s(z,N): the first N terms of the Maclaurin #series of s(z) in Flajolet's 1985 paper, bottom of p. 7 s:=proc(z,N) local k,i,NS: NS:=0: for k from 1 to N/2 do NS:=NS+ taylor(z^(2*k+1)/(1-2*z+z^(k+1)),z=0,N+1): od: NS: end: