Monday April 8, 2001

Speaker: Michael Kleber

Title: A fast-growing tree


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.