### Monday April 8, 2001

**Speaker**: Michael Kleber

**Title**: A fast-growing tree

**Abstract**:

Question: How many integer sequences of length n are there which always
increase but never more than double?

These numbers grow very quickly -- for n=20 there are
989,901,541,366,810,465,070,950,556,260,422,637,919,176 of them.
Counting them in the obvious way would take time exponential in n. I'll
share a clever observation (of mine) to calculate the answer in time
polynomial in n, and another clever observation (of Donald Knuth's) to
estimate the asymptotics.