Schröder's problems and scaling limits of random trees

Jim Pitman, Douglas Rizzolo

Published 2011-07-09, updated 2013-09-22Version 2

In a classic paper Schr\"oder posed four combinatorial problems about the number of certain types of bracketings of words and sets. Here we address what these bracketings look like on average. For each of the four problems we prove that a uniform pick from the appropriate set of bracketings, when considered as a tree, has the Brownian continuum random tree as its scaling limit as the size of the word or set goes to infinity.