What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I
arXiv:1808.08449
Abstract
For enumerative problems, i.e. computable functions f from N to Z, we define the notion of an effective (or closed) formula. It is an algorithm computing f(n) in the number of steps that is polynomial in the combined size of the input n and the output f(n), both written in binary notation. We discuss many examples of enumerative problems for which such closed formulas are, or are not, known. These problems include (i) linear recurrence sequences and holonomic sequences, (ii) integer partitions, (iii) pattern-avoiding permutations, (iv) triangle-free graphs and (v) regular graphs. In part I we discuss problems (i) and (ii) and defer (iii)--(v) to part II. Besides other results, we prove here that every linear recurrence sequence of integers has an effective formula in our sense.
arXiv commentMore precise discussion of Wilf's definitions of an "answer". References added (especially Shallit's lecture, Cobham, Edmonds, Wright)
References in corpus (12)
- On the Quantum Density of States and Partitioning an Integer
- Class polynomials for nonholomorphic modular functions
- Efficient implementation of the Hardy-Ramanujan-Rademacher formula
- Overview of some general results in combinatorial enumeration
- Complexity problems in enumerative combinatorics
- A method of finding the asymptotics of q-series based on the convolution of generating functions
- Compositions into Powers of : Asymptotic Enumeration and Parameters
- Counting Matrices that are Squares
- Powers of Euler's q-Series
- Simple proofs and expressions for the restricted partition function and its polynomial part
- Semiclassical analysis of distinct square partitions
- Counting Cliques in Finite Distant Graphs