2
$\begingroup$

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics.

I am quiet curious as how to asymptotically estimate the number of objects of size at most n.

Suppose for example that I specified a combinatorial class $A$. I also computed its generating function $A(z)=\sum\limits_n a_n z^n$. Therefore, studying the singularities of $A(z)$ yields an asymptotic estimate of the coefficient $a_n$, that represents the number of objects of size n.

How can I asymptotically estimate the number of objects of size at most $n$ ($\sum\limits_{k=0}^{n} a_n$)? Ideally, I would seek a combinatorial interpretation that would let me re-use the generating function $A(z)$, but I am drying up! Any thoughts?

$\endgroup$
2
$\begingroup$

If $A(z)$ is the generating function of the class $A$, then $$[z^n] {A(z) \over 1-z} $$ is the number of objects in the class $A$ at most $n$. (Recall $1/(1-z) = 1 + z + z^2 + \cdots$ and think about how multiplication of formal power series works.) You can then use the techniques of Flajolet and Sedgewick's book to get the asymptotics.

$\endgroup$
0
$\begingroup$

Indeed, it does the trick!

B(z) = $A(z) \times \sum\limits_n z^n = \sum\limits_{n} \sum\limits_{k = 0}^n a_k z^n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.