{VERSION 2 3 "DEC ALPHA UNIX" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 " " 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 272 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "cou rier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE " " 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 } {PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } } {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 256 55 "ASYMPTOTICS OF THE STIRL ING NUMBERS\n OF THE SECOND KIND" }}{PARA 19 "" 0 "" {TEXT 257 27 "Bru no Salvy & John Shackell" }}{PARA 256 "" 0 "" {TEXT -1 12 "January 199 8" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 256 "We \+ show how computer algebra can be used to compute automatically the asy mptotics of the Bell numbers and of the average value and variance of \+ the number of parts in a partition. This worksheet details the computa tions involved in Section 3 of our article " }{TEXT 258 54 "Symbolic A symptotics: Multiseries of Inverse Functions" }{TEXT -1 185 ", availab le as INRIA Research Report #3264, 1997. The starting point for all th ese asymptotic expansions is the bivariate generating function of the \+ Stirling numbers of the second kind:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "F:=exp(u*(exp(x)-1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG-%$expG6#*&%\"uG\"\"\",&-F&6#%\"xGF*!\"\"F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "series(F,x);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#+1%\"xG\"\"\"\"\"!%\"uG\"\"\",&F'#F%\"\"#*$F'F+F*\"\"#, (F'#F%\"\"'F,F**$F'\"\"$F/\"\"$,*F'#F%\"#CF,#\"\"(F6F1#F%\"\"%*$F'F:F5 \"\"%,,F'#F%\"$?\"F,#F%\"\")F1#\"\"&F6F;#F%\"#7*$F'FCF>\"\"&-%\"OG6#F% \"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "The coefficient of " } {XPPEDIT 18 0 "u^k*x^n" "*&)%\"uG%\"kG\"\"\")%\"xG%\"nGF&" }{TEXT -1 58 " in this series is the Stirling number of the second kind " } {XPPEDIT 18 0 "S[n,k]" "&%\"SG6$%\"nG%\"kG" }{TEXT -1 12 " divided by \+ " }{XPPEDIT 18 0 "n!" "-%*factorialG6#%\"nG" }{TEXT -1 65 ". These num bers count the number of partitions of the set \{1,...," }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 5 "\} in " }{XPPEDIT 18 0 "k" "I\"kG6\"" } {TEXT -1 7 " parts." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "For funct ions with a fast growth at infinity, like many functions related to " }{XPPEDIT 18 0 "F" "I\"FG6\"" }{TEXT -1 719 ", the asymptotic behaviou r of the Taylor coefficients can be computed by the saddle-point metho d. This method relies on using an integral along a closed contour in t he complex plane chosen in such a way as to pass through a special poi nt called the saddle-point. The integral is concentrated in the neighb orhood of the saddle-point and good asymptotic estimates are obtained \+ from a local expansion there. However, in these applications, the sadd le-point is defined implicitly by an equation and only an asymptotic e xpansion of it is available. This introduces technical difficulties in the manipulation of the expansions. This worksheet explores how our a lgorithm for asymptotic inversion applies in such circumstances." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "We first load our experimental imp lementation" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "read `/expor t/salvy/Alcom/97/Lib/asympt_inv/load.mpl`;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 314 "Sufficient conditions for deriving an asymptotic expansi on by the saddle-point method have been given by Harris and Schoenfeld . These conditions are satisfied by all the generating functions we co nsider in this worksheet. The following procedure (which can be skippe d in a first reading) takes as input a function " }{XPPEDIT 18 0 "f(x) " "-%\"fG6#%\"xG" }{TEXT -1 117 ", the associated saddle-point equatio n, an asymptotic scale (see below) and computes the asymptotic expansi on of the " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 25 "th Taylor coef ficient of " }{XPPEDIT 18 0 "f(x)" "-%\"fG6#%\"xG" }{TEXT -1 4 " as " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 48 " tends to infinity in term s of the saddle-point." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 507 " harris_schoenfeld:=proc(f,x,R,nofR,nbterms,scale)local A, B, Bb, Cc, F , i, m, u, compo;A:=diff(log(f),x);for i to 2*nbterms do B[i]:=normal( x^i/i!*diff(A,[x$(i-1)])) od;Bb:=x*diff(B[1],x)/2;for i to 2*nbterms-2 do Cc[i]:=normal(-(B[i+2]+(-1)^i/(i+2)*B[1])/Bb) od;F[0]:=1;for i to \+ nbterms-1 do F[i]:=(-1)^i/sqrt(Pi)*add(GAMMA(m+i+1/2)/m!*add(mul(Cc[u] ,u=compo),compo=combinat[composition](2*i,m)),m=1..2*i)od;tower(subs([ x=R,n=nofR],f/2/sqrt(Pi)/sqrt(Bb)/x^n*add(normal(F[i]/Bb^i),i=0..nbter ms-1)),scale)end:" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 31 "Asymptotics of the Bell numbers" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "The Bell n umbers " }{XPPEDIT 18 0 "B[n]" "&%\"BG6#%\"nG" }{TEXT -1 18 " are the \+ sum over " }{TEXT 270 1 "k" }{TEXT -1 25 " of the Stirling numbers " } {XPPEDIT 18 0 "S[n,k]" "&%\"SG6$%\"nG%\"kG" }{TEXT -1 30 ". Their gene rating function is" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "f:=su bs(u=1,F);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG-%$expG6#,&-F&6#% \"xG\"\"\"!\"\"F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 139 "Alternative ly, since these numbers count the number of partitions of a set, this \+ generating function and the numbers can be obtained using " } {HYPERLNK 17 "combstruct" 2 "combstruct" "" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "G:=\{P=Set(Set(Atom,card>0))\}:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "combstruct[gfsolve](G,label led,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"PG6#%\"xG-%$expG6#,& -F*F'\"\"\"!\"\"F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Here are th e first numbers:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "series( f,x,20);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#+M%\"xG\"\"\"\"\"!F%\"\"\" F%\"\"##\"\"&\"\"'\"\"$#F*\"\")\"\"%#\"#8\"#I\"\"&#\"$.#\"$?(\"\"'#\"$ x)\"%S]\"\"(#\"#B\"$C#\"\")#\"%25\"&!G<\"\"*#\"%RY\"'_^9\"#5#\"&>E#\"( g0L\"\"#6#\"((f8U\"*+;+z%\"#7#\")PWkF\"++3-Fi\"#8#\")h'\\a*\",+c9*eV\" #9#\"*4-%\"OG6#F% \"#?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 10 "or, using " }{HYPERLNK 17 "combstruct" 2 "combstruct" "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "seq(combstruct[count]([P,G,labelled],size=i),i=0..19) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "66\"\"\"F#\"\"#\"\"&\"#:\"#_\"$.#\" $x)\"%ST\"&Z6#\"'vf6\"'q&y'\"((f8U\")PWkF\"*A$**3>\"+X&eHQ\"\",Z@9![5 \",/)p['G)\"-fh!o2#o\".d]?UF$e" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "the factor 1/" }{XPPEDIT 18 0 "n!" "-%*factorialG6#%\"nG" }{TEXT -1 25 " being due to the use of " }{TEXT 269 11 "exponential" }{TEXT -1 22 " generating functions." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "The saddle-point equation we use is" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "speq:=subs(x=R,diff(log(f),x)*x)-1=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%speqG/,&*&-%$expG6#%\"RG\"\"\"F+F,F,!\"\"F,%\"n G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 118 "Then the asymptotic analysi s of the Bell numbers is classically based on the asymptotic behaviour of the saddle-point " }{XPPEDIT 18 0 "R" "I\"RG6\"" }{TEXT -1 25 " vi ewed as a function of " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 4 " as " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 19 " tends to infinity." }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 178 "From the above equation our algo rithm produces the asymptotic expansion of the saddle-point in two sta ges: first a sequence of ``exact'' information is computed by the proc edure " }{TEXT 272 6 "Invert" }{TEXT -1 30 " which also creates the sc ale " }{TEXT 271 6 "scaleR" }{TEXT -1 46 " necessary for the expansion s of functions of " }{TEXT 259 1 "R" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "r1:=Invert(lhs(speq),R,'scaleR');" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r1G6&7%,*-%#lnG6#%\"RG\"\"\"F+F,-F) 6#,&F,F,*&-%$expGF*!\"\"F+F3F3F,*(,&*$F+F3F,*$F(F3F,F,F(F,F+F,F3F,F4F2 7%-F)6#*&,&*$F1F3F,F6F,F,F+F,\"\"#F+7%\"\"!F>F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "The last argument has been assigned the correspondin g asymptotic scale:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "scal eR[list];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$-%#lnG6#%\"RG!\"\"*$F (F)*$-%$expGF'F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "In a second s tage, asymptotic information is extracted from the exact result " } {TEXT 273 2 "r1" }{TEXT -1 60 " and the scale necessary for the expans ions of functions of " }{TEXT 260 1 "n" }{TEXT -1 11 " is created" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "exp1:=multiseriesinverse([r1 ],scaleR,0,2,n,3,'scalen');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%exp1 G,*-%#lnG6#%\"nG\"\"\"-F'6#F&!\"\"*&F+F*F&F-F*-%\"OG6#*$F&!\"#F*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "Here again the variable " }{TEXT 274 6 "scalen" }{TEXT -1 52 " holds the asymptotic scale related to th e variable " }{TEXT 275 1 "n" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "scalen[list];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #7%*$-%#lnG6#-F&6#-F&6#%\"nG!\"\"*$F(F-*$F*F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "The procedure " }{TEXT 276 17 "harris_schoenfeld" } {TEXT -1 102 " written above is then able to compute the expansion of \+ the Bell numbers in terms of the saddle-point " }{TEXT 261 1 "R" } {TEXT -1 14 " in the scale " }{TEXT 262 6 "scaleR" }{TEXT -1 30 " whic h has been obtained above" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "d1:=harris_schoenfeld(f,x,R,lhs(speq),3,scaleR);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#d1G,$*4-%$expG6#-F(6#%\"RG\"\"\"-F(6#!\"\"F-%#PiG #F0\"\"#F3#F-F3*&F,F-,&F*F-*&F*F-F,F-F-F-F2-F(6#*(F,F--%#lnGF+F-F*F-F0 F,F--F(6#,(*&,&F7F-F0F-F-F;F-F-F:F0F;F-F0,(F-F-**,,*$F,\"\"$!\"$*$F,\" \"%F3F3F-F,!#=*$F,F3!#?F-,&F-F-F,F-FGF,F0F*F0#F0\"#C**,4F,!#s*$F,\"\"' !$&p*$F,\"\"&!$'pFH\"%#4\"FK\"%s>FE\"%;H*$F,\"\"(!$c\"*$F,\"\")FIFIF-F -FM!\"'F,!\"#F*F\\o#F-\"%_6F-F4" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "The result follows upon substitution of " }{TEXT 263 1 "R" }{TEXT -1 41 " by its asymptotic expansion in terms of " }{TEXT 264 1 "n" } {TEXT -1 2 " (" }{TEXT 265 4 "exp1" }{TEXT -1 88 " above). Since the l ogarithm of this expansion is easier to handle, we first compute it:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "d2:=`tower/ln`(d1,scaleR) :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "multiseries(d2,scaleR, 0,3,nops(scaleR[list]),3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*&,&\" \"\"F&*&-%#lnG6#%\"RGF&F+F&!\"\"F&-%$expGF*F&F&F+#F,\"\"#-F)6#,$*(-F.6 #F,F&F0#F&F0%#PiGF/F7F&*$F+F,F/-%\"OG6#*$F+!\"#F&*&,*#F,\"#7F&F9#\"\"$ \"\")F=#F,\"#C-F;6#*$F+!\"$F&F&F-F,F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "Hence the result by substituting the expansion of " } {XPPEDIT 18 0 "R" "I\"RG6\"" }{TEXT -1 13 " in terms of " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 24 " in this last expansion:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "substitute(d2,scaleR,exp1,scalen,3) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,.*&,(-%#lnG6#-F'6#%\"nG!\"\"*(,& *$F&F,\"\"\"F0F0F0F&F0F)F,F0-%\"OG6#*$F)!\"#F0F0F+F0F0F)#F,\"\"#*&,&*& -F'6#,$*(-%$expG6#F,F0F7#F0F7%#PiGF6FBF0F&F,F7F0F0F0F&F0FBF-F6F1F0*&,( F)#F,\"#7*&,&F/\"\"*F7F0F0F&F0#F0\"#C-F26#*$F)F,F0F0F+F,F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "The first part of this expansion is the c lassical expansion of " }{XPPEDIT 18 0 "ln(B[n]*`/`*n!)" "-%#lnG6#*(&% \"BG6#%\"nG\"\"\"%\"/GF*-%*factorialG6#F)F*" }{TEXT -1 192 " which can be found in (de Bruijn 1981, p. 108). The remaining parts reflect the use of multiseries, a recent tool which makes it possible to deal wit h indefinite cancellation in a simple way." }}}}{SECT 0 {PARA 3 "" 0 " " {TEXT -1 38 "Average number of parts in a partition" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 209 "The technique demonstrated above also applies \+ to the average number of parts in a partition, where an indefinite can cellation occurs and this exemplifies the use of multiple scales. The \+ generating function of " }{XPPEDIT 18 0 "Sum(k*S[n,k],k)" "-%$SumG6$*& %\"kG\"\"\"&%\"SG6$%\"nGF&F'F&" }{TEXT -1 4 " is" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 23 "g:=subs(u=1,diff(F,u));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG*&,&-%$expG6#%\"xG\"\"\"!\"\"F+F+-F(6#F&F+" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "The average number of parts in a p artition of a set of size " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 8 " is the " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 25 "th Taylor coeff icient of " }{XPPEDIT 18 0 "g" "I\"gG6\"" }{TEXT -1 16 " divided by th e " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 18 "th coefficient of " } {XPPEDIT 18 0 "f" "I\"fG6\"" }{TEXT -1 72 " whose asymptotics we have \+ just computed. The saddle-point equation for " }{XPPEDIT 18 0 "g" "I\" gG6\"" }{TEXT -1 4 " is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "speq2:=normal(subs(x=R,diff(log(g),x)*x)-1)=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&speq2G/*&,(*&-%$expG6#%\"RG\"\"#F,\"\"\"F.F)!\"\"F.F .F.,&F)F.F/F.F/%\"nG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "From thi s equation our algorithm produces the asymptotic expansion of the sadd le-point in two stages as before:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "r2:=Invert(op(1,speq2),R):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "exp2:=multiseriesinverse([r2],scaleR,0,2,n,3,scale n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%exp2G,*-%#lnG6#%\"nG\"\"\"-F '6#F&!\"\"*&F+F*F&F-F*-%\"OG6#*$F&!\"#F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 294 "This expansion of this new saddle-point is the same as t hat of the previous case. But this does not mean that both saddle-poin ts are equal. The difference between their asymptotic behaviours can b e obtained by working in a different scale. Here is a refined estimate for the first saddle-point:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "sp1:=multiseriesinverse([r1],scaleR,2,1,n,3,'scalezeta');" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$sp1G,*-%'RootOfG6#,(-%#lnG6#%#_ZG\" \"\"F-F.-F+6#%\"nG!\"\"F.*(F&F2,&*$F&F2F.F.F.F2-%$expG6#F&F2F.**F&!\"# ,&F5\"\"#F.F.F.F4!\"$F6F:#F2F<-%\"OG6#*$F6F=F." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "alias(zeta=%1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "sp1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,*%%zetaG\"\" \"*(F$!\"\",&*$F$F'F%F%F%F'-%$expG6#F$F'F%**F$!\"#,&F)\"\"#F%F%F%F(!\" $F*F.#F'F0-%\"OG6#*$F*F1F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 69 "and here is an estimate for the second saddle-point refined similarly" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "sp2:=multiseriesinverse([r2 ],scaleR,2,1,n,3,scalezeta);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$sp2 G,*%%zetaG\"\"\"*(,&*$F&!\"\"F'F+F'F',&F*F'F'F'F+-%$expG6#F&F+F'*(,**$ F&!\"#F+F*\"\"#\"\"$F'*$F&!\"$\"\"%F'F,F7F-F3#F+F4-%\"OG6#*$F-F7F'" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Hence the difference can be compu ted at this level of the asymptotic scale" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 58 "`multiseries/expand`(x1-x2,[x1,x2],[sp1,sp2],scalez eta,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&,&*$%%zetaG!\"\"\"\"\"F )F)F(-%$expG6#F'F(F)*(,**$F'!\"$\"\"#*$F'!\"#F3F&F1\"\"$F)F)F%F0F*F3#F )F1-%\"OG6#*$F*F0F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "or in term s of " }{XPPEDIT 18 0 "n" "I\"nG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "substitute(SERIEStoseries(\",'polynom'),scalezeta,exp 1,scalen,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*&,(-%#lnG6#%\"nG\" \"\"*&,&*$-F'6#F&!\"\"F*F*F*F*F.F*F0-%\"OG6#*$F&F0F*F*F)F0F**&,(*$F&\" \"##\"\"$F8*(,&\"\"'F*F-\"\"(F*F.F*F&F*#F0F8-F26#F*F*F*F)!\"#F*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "Thus the saddle-points differ asym ptotically by " }{XPPEDIT 18 0 "ln(n)" "-%#lnG6#%\"nG" }{TEXT 266 1 "/ " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 82 ", which could not be det ected from the asymptotic expansion in the original scale." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "In order to compute the average number o f parts in a partition, we have to divide the estimate for the " } {XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 18 "th coefficient of " } {XPPEDIT 18 0 "g" "I\"gG6\"" }{TEXT -1 25 " by the estimate for the " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 18 "th coefficient of " } {XPPEDIT 18 0 "f" "I\"fG6\"" }{TEXT -1 169 ". Since these estimates ar e given in terms of different saddle-points, the computation is more e asily done by obtaining both estimates in the same scale, which involv es " }{XPPEDIT 18 0 "zeta" "I%zetaG6\"" }{TEXT -1 42 " , and then subs tituting the estimate for " }{XPPEDIT 18 0 "zeta" "I%zetaG6\"" }{TEXT -1 13 " in terms of " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 1 "." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "estden:=substitute(d1,scale R,sp1,scalezeta,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'estdenG*(,(* ,\"\"##\"\"\"F(-%$expG6#!\"\"F*%#PiG#F.F(*&%%zetaGF*,&F*F*F2F*F*F0*$-F ,6#F2F.F)F)*0,,*$F2!\"%F(*$F2!\"$\"\"'*$F2!\"#\"#;*$F2F.\"\"*F(F*F*F+F *F(F)F/F0F1F0,&FAF*F*F*F " 0 "" {MPLTEXT 1 0 50 "n1:=harris_schoenfeld(g,x,R,op(1,speq2),3,scaleR):" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "estnum:=substitute(SERIES toseries(multiseries(n1,scaleR,2,1,nops(scaleR[list]),3),'polynom'),sc aleR,sp2,scalezeta,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'estnumG*( ,(*,\"\"##\"\"\"F(-%$expG6#!\"\"F*%#PiG#F.F(*&%%zetaGF*,&F*F*F2F*F*F0* $-F,6#F2F.F0F)*0,,*$F2!\"%F(*$F2!\"$\"#I*$F2!\"#\"#w*$F2F.\"#p\"#EF*F* F+F*F(F)F1F0,&FAF*F*F*F " 0 "" {MPLTEXT 1 0 71 "ratio:=`multiseries/e xpand`(x2/x1,[x1,x2],[estden,estnum],scalezeta,3);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%&ratioG,(-%$expG6#%%zetaG\"\"\"*&,(*$F)!\"#\"\"#*$F )!\"\"\"\"$F/F*F*,&F0F*F*F*F.#F1F/-%\"OG6#*$F&F1F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "And here is the final result in " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 48 ": the average number of parts in a partit ion of " }{XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 10 " elements:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "substitute(SERIEStoseries(ra tio,'polynom'),scalezeta,exp1,scalen,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*&,(*$-%#lnG6#%\"nG!\"\"\"\"\"*&-F(6#F'F,F'!\"#F,-%\"OG6#*$F'! \"$F,F,F*F,F,F+F,F&#F,\"\"#*(F.F,,&F+F,*$F.F+F7F,F'F0#F+F7F1F," }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 273 "This result is classical. However , it is worth noting that classical references give at best the first \+ term of the asymptotic behaviour (n/log n) and one of them is wrong by a factor of e=exp(1). This gives an idea of the difficulty of perform ing such computations by hand." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 "Variance" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "Computation of the variance leads to further cancellation. It is obtained from the gener ating function" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "h:=subs(u =1,diff(u*diff(F,u),u));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"hG,&*& ,&-%$expG6#%\"xG\"\"\"!\"\"F,F,-F)6#F'F,F,*&F'\"\"#F.F,F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "The corresponding saddle-point equation i s" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "speq3:=subs(x=R,normal (diff(log(h),x)*x))-1=n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&speq3G/ ,&*(,(!\"\"\"\"\"-%$expG6#%\"RGF**$F+\"\"#F*F*F.F*,&F+F*F)F*F)F*F)F*% \"nG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "The expansion of the sadd le-point in terms of " }{XPPEDIT 18 0 "zeta" "I%zetaG6\"" }{TEXT -1 22 " is obtained as before" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "r3:=Invert(op(1,speq3),R);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#r 3G6&7%,*-%#lnG6#%\"RG\"\"\"F+F,-F)6#,$*&,,*$-%$expGF*!\"#!\"\"*$F3F6F, F,F,*&F3F6F+F6F6*&F3F5F+F6F,F,,&F6F,F7F,F6F6F,*(,&*$F+F6F,*$F(F6F,F,F( F,F+F,F6F,F;F47%-F)6#*&,&F7F,F=F,F,F+F,\"\"#F+7%\"\"!FDF+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "sp3:=multiseriesinverse([r3],scaleR ,2,1,n,3,scalezeta);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$sp3G,*%%zet aG\"\"\"*(,&*$F&!\"\"F'!\"#F'F',&F*F'F'F'F+-%$expG6#F&F+F'*(,(*$F&!\"$ \"\"#*$F&F,F4F5F'F'F-F4F.F,#F4F5-%\"OG6#*$F.F4F'" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 45 "This leads to the following estimate for the " } {XPPEDIT 18 0 "n" "I\"nG6\"" }{TEXT -1 18 "th coefficient of " } {XPPEDIT 18 0 "h" "I\"hG6\"" }{TEXT -1 20 ", first in terms of " } {TEXT 267 1 "R" }{TEXT -1 22 " and then in terms of " }{XPPEDIT 18 0 " zeta" "I%zetaG6\"" }{TEXT -1 18 " by substituting " }{TEXT 268 1 "R" }{TEXT -1 41 " by its asymptotic expansion in terms of " }{XPPEDIT 18 0 "zeta" "I%zetaG6\"" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "n2:=harris_schoenfeld(h,x,R,op(1,speq3),3,scaleR):" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 118 "estnum2:=substitute(SERIE Stoseries(multiseries(n2,scaleR,2,1,nops(scaleR[list]),3),'polynom'),s caleR,sp3,scalezeta,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(estnum2G *(,(*,\"\"##\"\"\"F(-%$expG6#!\"\"F*%#PiG#F.F(*&%%zetaGF*,&F2F*F*F*F*F 0*$-F,6#F2F.#!\"$F(F)*0,,*$F2!\"%F(*$F2F8\"#I*$F2!\"#\"#))*$F2F.\"$0\" \"#]F*F*F+F*F(F),&FBF*F*F*F8F/F0F1F0F4F0#F.\"#[-%\"OG6#*$F4F)F*F*-F,6# F5F*-F,6#*(F2F*-%#lnGF6F*F5F*F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "From there we get the variance in terms of " }{XPPEDIT 18 0 "zeta " "I%zetaG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 95 "finalres:= `multiseries/expand`(x3/x1-(x2/x1)^2,[x1,x2,x3],[estden,estnum,estnum2 ],scalezeta,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)finalresG,&*(%%z etaG!\"\",&*$F'F(\"\"\"F+F+F(-%$expG6#F'F+F+-%\"OG6#F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "and in terms of " }{XPPEDIT 18 0 "n" "I\" nG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "substitute(SERIESt oseries(\",'polynom'),scalezeta,exp1,scalen,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,(*$-%#lnG6#%\"nG!\"#\"\"\"*(,&F*F+*$-F'6#F&!\"\"F+F+ F/F+F&!\"$F1-%\"OG6#*$F&!\"%F+F+F)F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "Again, only the first term is given in the literature. Our met hod can compute as many terms as desired, as well as the expansions of higher moments." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 10 "Conclusion " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 321 "Multiseries are specially use ful for saddle-point asymptotics that arise frequently in combinatoria l applications. Delicate expansions (that lead to errors in the techni cal literature) can be handled automatically. Such a process is specia lly useful for moment computations that involve minute saddle-point pe rturbations." }}}}}{MARK "12 0 0" 10 }{VIEWOPTS 1 1 0 1 1 1803 }