August 2nd, 2011

beartato phd

(no subject) is an astonishing list of over a hundred questions in enumerative combinatorics whose answer is "the Catalan Numbers".

Skimming through it, I found one I hadn't heard of that I like:

How many distinct terms are there in the product a(a+b)(a+b+c)(a+b+c+d)... ?

The first few polynomials you get out are:

a (1 term)
a^2 + ab (2 terms)
a^3 + 2a^2b + ab^2 + a^2c + abc (5 terms)
a^4 + 3a^3b + 3a^2b^2 + 2a^3c
+ 4a^2bc + ab^3 + 2ab^2c
+ a^2c^2 + abc^2 a^3d
+ 2a^2bd + ab^2d + a^2cd
+ abcd (14 terms)

I wonder if there's a natural noninjective mapping from permutations on n things to size-n binary trees that accounts for the sometimes-bigger-than-1 coefficients in these polynomials.