Rational and algebraic series in combinatorial enumeration
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2008
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908557098614784 |
|---|---|
| author | Bousquet-Mélou, Mireille |
| author_facet | Bousquet-Mélou, Mireille |
| contents | Let A be a class of objects, equipped with an integer size such that for all n the number a(n) of objects of size n is finite. We are interested in the case where the generating fucntion sum_n a(n) t^n is rational, or more generally algebraic. This property has a practical interest, since one can usually say a lot on the numbers a(n), but also a combinatorial one: the rational or algebraic nature of the generating function suggests that the objects have a (possibly hidden) structure, similar to the linear structure of words in the rational case, and to the branching structure of trees in the algebraic case. We describe and illustrate this combinatorial intuition, and discuss its validity. While it seems to be satisfactory in the rational case, it is probably incomplete in the algebraic one. We conclude with open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0805_0588 |
| institution | arXiv |
| publishDate | 2008 |
| record_format | arxiv |
| spellingShingle | Rational and algebraic series in combinatorial enumeration Bousquet-Mélou, Mireille Combinatorics 05A15, 68Q45 Let A be a class of objects, equipped with an integer size such that for all n the number a(n) of objects of size n is finite. We are interested in the case where the generating fucntion sum_n a(n) t^n is rational, or more generally algebraic. This property has a practical interest, since one can usually say a lot on the numbers a(n), but also a combinatorial one: the rational or algebraic nature of the generating function suggests that the objects have a (possibly hidden) structure, similar to the linear structure of words in the rational case, and to the branching structure of trees in the algebraic case. We describe and illustrate this combinatorial intuition, and discuss its validity. While it seems to be satisfactory in the rational case, it is probably incomplete in the algebraic one. We conclude with open questions. |
| title | Rational and algebraic series in combinatorial enumeration |
| topic | Combinatorics 05A15, 68Q45 |
| url | https://arxiv.org/abs/0805.0588 |