Conditioned to rationality

At Uncertain Principles and Unqualified Offerings there has been talk about how students in disciplines where the numbers come with units seem to be conditioned to expect numbers of order unity. (And so are professional scientists, who deal with this by defining appropriate units.)

Mathematicians, of course, don't have this luxury. But we are conditioned to think, perhaps, that rational numbers are better than irrational ones, that algebraic numbers are better than transcendental ones (except maybe π and e), and so on. In my corner of mathematics (discrete probability/analysis of algorithms/combinatorics), often sequences of integers a(1), a(2), ... arise and you want to know approximately how large the nth term is. For example, the nth Fibonacci number is approximately φⁿ/5^1/2, where φ = (1+5^1/2)/2 is the "golden ratio". The nth Catalan number (another sequence that arises often) is approximately 4ⁿ/(π n³)^1/2. In general, "many" sequences turn out to satisfy something like

a(n) ~ p qⁿ (log n)^r n^s

where p, q, r, and s are constants. There are deep reasons for this that can't fully be explained in a blog post, but have to do with the fact that a(n) often has a generating function of a certain type. What's surprising is that while p and q are often irrational, r and s are almost never irrational, at least for sequences that arise in the "real world". Furthermore, they usually tend to be "simple" rational numbers -- 3/2, not 26/17. If you told me some sequence of numbers grows like πⁿ I'd be interested. If you told me some sequence of numbers grows like n^π. I'd assume I misheard you. Of course, there's the possibility of sampling bias -- I think that the exponents tend to be rational because if they weren't rational I wouldn't know what to do! They do occur -- for example, consider the Hardy-Ramanujan asymptotic formula for the number of partitions p(n) of an integer n:

p(n) ~ exp(π (2n/3)^1/2)/(4n √3)).

I know this exists, but it still just looks weird.

(This is an extended version of a comment I left at Uncertain principles.)

Best-seller impatiemment attendu

From "Quelques contributions au carrefour de la géométrie, de la combinatoire et des probabilités", by Nicolas Pouyanne:

"Dans leur best-seller impatiemment attendu [28], P. Flajolet et R. Sedgewick offrent un développement approfondi de la méthode symbolique en analyse
combinatoire, auquel on pourra se référer."

That is, "In their impatiently awaited best-seller [28], P. Flajolet and R. Sedgewick offer a detailed development of the symbolic method in combinatorial analysis, to which one will be able to refer."

I don't laugh often while reading mathematics, but this made me laugh, because I am among those impatiently awaiting this book. I've seen citations to Flajolet and Sedgewick's book Analytic Combinatorics in things written as long ago as 1998 or so; Amazon.com says the book will be out on December 31, 2008, and the publisher, Cambridge University Press says December 2008. It can be downloaded from Flajolet's web site.

Edited, January 22, 2009: my copy of this book arrived yesterday.