13
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ This is not too closely related, but I have periodically wondered what one ought to mean by the claim that two interpretations of the Catalan numbers are "the same." This isn't really meaningful until I provide some extra structure of some kind so that I can tell you what it means for two such structured things to be isomorphic or not. One thing I could ask for is a group action on the set of Catalan objects of index $n$; certainly I can't ask for an $S_n$ action but thinking about, say, balanced parentheses I could at least ask for a $C_2$ action... $\endgroup$ Dec 13, 2014 at 7:37
  • $\begingroup$ @QiaochuYuan you can actually ask for a cyclic group action, this happens and is then called "cyclic sieving phenomenon" :-) $\endgroup$ Dec 13, 2014 at 19:47

1 Answer 1

18
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your answer. I realize that my question is not very precise, but your answer seems like a reasonable solution. $\endgroup$ Dec 13, 2014 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.