The case of maps: recursive program derived from ODE
> | # Returns the generating polynomial of ROOTED maps with n edges
# with u/z marking vertices/faces # Computation coefficient by coefficient from the non-shifted ODE: # (not optimized, a variant of Newton iteration could probably be used instead) mapsEdges:= proc(n) option remember: if n<1 then return 0: else eval(subs(Theta(t)=a*t^(2*n)/4/n+add(mapsEdges(k)*t^(2*k)/4/k,k=1..n-1),bigODEmaps)): factor(series(%,t=0,2*n+10)): coeff(%,t,2*n-1): return factor(solve(%,a)): fi; end: |
> | # example: 3 edges
mapsEdges(3); |
(3.2.1) |
> | # Uses the previous one to compute maps by edges and genus
# (not optimal AT ALL for small genus since all genera are computed for each size) mapsEdgesGenus:= proc(n,g) option remember: if n<1 then return 0: else expand(subs(u=u/s,z=z/s,mapsEdges(n)*s^(n+2))): # print(%); return factor(coeff(%,s,2*g)); fi; end: |
> | # example: 5 edges, genus 2
mapsEdgesGenus(5,2); |
(3.2.2) |
> | # more economic variant that uses the ODE and truncates all terms of genus <= g at each step
# returns the generating polynomial of maps with n edges and genus AT MOST g # with u/z marking vertices/faces mapsEdgesGenusBounded:= proc(n,g) option remember: if n<1 then return 0: else eval(subs(Theta(t)=a*t^(2*n)/4/n+add(mapsEdgesGenusBounded(k,g)*t^(2*k)/4/k,k=1..n-1),bigODEmaps)): factor(series(%,t=0,2*n+10)): coeff(%,t,2*n-1): factor(solve(%,a)): expand(subs(u=u/s,z=z/s,mapsEdges(n)*s^(n+2))): return factor(add(coeff(%,s,h),h=0..2*g)); fi; end: |
> | # example: 3 edges, genus AT MOST 2
mapsEdgesGenusBounded(5,2); |
(3.2.3) |
> | # Uses the previous function to compute maps by edges and genus
# (only inferior genera are computed in all intermediate calculations - should be much faster than mapsEdgesGenus for small genus) mapsEdgesGenusFaster:= proc(n,g) option remember: if n<1 then return 0: else expand(subs(u=u/s,z=z/s,mapsEdgesGenusBounded(n,g)*s^(n+2))): return factor(coeff(%,s,2*g)); fi; end: |
> | # example: 3 edges, genus 2
mapsEdgesGenus(7,2); mapsEdgesGenusFaster(7,2); # note: it also gives the same answer as the direct recurrence (!) HngW(7,2); HHng(7,2); |
(3.2.4) |