Combinatorial Systems and Newton Iteration

Abstract

We consider combinatorial structures defined by fixed point equations, and want to efficiently compute enumeration sequences and numerically evaluate generating functions, in order to derive uniform random samplers for these structures. We show that combinatorial iteration of structures can be lifted to the level of generating functions and numerical evaluation; and we present a Newton iteration that computes the first n coefficients with arithmetic complexity O(n log n) and is also transferred? to a numerical iteration that converges to the value of the? generating function at every point inside the disk of convergence.? (This is a joint work with Carine Pivoteau and Bruno Salvy.)