During a lecture I gave on Catalan numbers, I pointed out that that it
is possible to give a continuum number of combinatorial
interpretations of these numbers. See the solution to (f$^5$) on
page 54 of <http://math.mit.edu/~rstan/ec/catadd.pdf>. After the lecture
someone from the audience (I don't know who) asked me if one can give
*more* than a continuum number of combinatorial interpretations. For
instance, for each subset of $\mathbb{R}$ can one give a different
combinatorial interpretation? Can anyone shed some light on this
question?



Lots of combinatorial interpretations of Catalan numbers
For a genuine answer, one needs a genuine definition of what counts as a combinatorial interpretation. One needs to exclude silly things like the following "interpretation $X$" for any set $X$ of real numbers: The number of pairs $(p,X)$ where the first component $p$ is a proper sequence of $2n$ parentheses and the second component is the fixed $X$. Although I haven't read all of the usual combinatorial interpretations of the Catalan numbers, I conjecture that they are all covered by the following set-up and that the set-up will look reasonable to combinatorialists.


Fix a countably infinite collection of non-sets, which I'll call "atoms", and build an analog of the cumulative hierarchy of set theory over these atoms, but build only finite sets and don't iterate transfinitely. That is, let $V\_0$ be the set of atoms, and let $V\_{n+1}$, for each natural number $n$, be the union of $V\_0$ with the collection of all finite subsets of $V\_n$. Thus, $V\_1$ consists of atoms and finite sets of atoms, $V\_2$ consists of atoms and finite sets of (atoms and finite sets of atoms), etc. By a "combinatorial entity", I'll mean any element of the union of all the $V\_n$'s. Note that standard codings from set theory allow you to represent, as combinatorial entities, any finite tuple of combinatorial entities, any function mapping a finite set of combinatorial entities to other combinatorial entities, etc. Von Neumann's coding also lets you represent each natural number as a combinatorial entity. Then by a "Catalan interpretation", I mean a function assigning to each natural number $n$ a combinatorial entity whose cardinality is the $n$-th Catalan number. 


If you buy this definition, then there are only continuum many Catalan interpretations, because there are only countably many combinatorial entities. If you don't buy this definition, tell me what you would buy.


