Higher-dimensional Catalan numbers? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T12:37:49Z http://mathoverflow.net/feeds/question/81473 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers Higher-dimensional Catalan numbers? Joseph O'Rourke 2011-11-21T01:24:31Z 2011-11-22T14:16:08Z <p>One could imagine defining various notions of higher-dimensional Catalan numbers, by generalizing objects they count. For example, because the Catalan numbers count the triangulations of convex polygons, one could count the tetrahedralizations of convex polyhedra, or more generally, triangulations of polytopes. Perhaps the number of triangulations of the $n$-cube are similar to the Catalan numbers? Or, because the Catalan numbers count the number of below-diagonal monotonic paths in an $n \times n$ grid, one could count the number of monotonic paths below the "diagonal hyperplane" in an $n \times \cdots \times n$ grid.</p> <p>I would be interested in references to such generalizations, which surely have been considered&mdash;I am just not looking under the right terminology. I would be particularly grateful to learn of generalizations that share some of the Catalan number's ubiquity. Thanks for pointers!</p> http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81474#81474 Answer by David Speyer for Higher-dimensional Catalan numbers? David Speyer 2011-11-21T01:54:35Z 2011-11-21T01:54:35Z <p>The closest thing I can think of to what you want is <a href="http://arxiv.org/abs/1001.5437" rel="nofollow">triangulations of even dimensional cyclic polytopes.</a> These are nice because, unlike triangulations of the cube, they all use the same number of simplices. See the above linked paper for more.</p> <p>There are a number of other important generalizations of Catalan numbers, but these are the only ones I would particularly call higher-dimensional.</p> http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81476#81476 Answer by Gjergji Zaimi for Higher-dimensional Catalan numbers? Gjergji Zaimi 2011-11-21T03:00:20Z 2011-11-21T23:45:51Z <p>When you count the number of positively directed paths from $(0,0,\dots,0)$ to $(n,n,\dots,n)$ that lie in the region $x_d\le x_1+\cdots+x_{d-1}$, you can project to the plane $(x_d,x_1+\cdots+x_{d-1})$ and find that you need the number of planar paths from $(0,0)$ to $(n,n(d-1))$ which stay above the line $x=y$, and which have $n$ vertical steps of each color {1,...,d-1}. So the answer comes to be $$\left(\binom{nd}{n}-\binom{nd}{n-1}\right)\binom{n(d-1)}{n,\dots,n}=\frac{n(d-2)+1}{n(d-1)+1}\frac{(nd)!}{(n!)^d}.$$ See also <a href="http://mathoverflow.net/questions/1960/dyck-paths-on-rectangles" rel="nofollow">this previous question</a> for enumerating lattice paths below a line.</p> <p>On the other hand, one way to interpret Catalan numbers as lattice paths below the diagonal is to look at it as counting the number of standard Young tableaux of shape $(n,n)$. So a natural generalization is for example the number of standard Young tableaux of shape $(n,n,\dots,n)$. This corresponds to the region $x_1\le x_2\le\cdots\le x_d$, and can be counted using the hook-length formula. See my answer <a href="http://mathoverflow.net/questions/74908/generalizing-the-catalan-number-enumerative-combinatorics/74913#74913" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81477#81477 Answer by Bruce Westbury for Higher-dimensional Catalan numbers? Bruce Westbury 2011-11-21T04:54:02Z 2011-11-21T04:54:02Z <p>I am interested in nested sequences of Dyck paths. I rotate your picture and think of a Dyck path as a sequence of steps $(1,1)$ and $(1,-1)$ which stays above $y=0$. A <em>nested sequence</em> is a sequence of $k$ Dyck paths such that if <code>$1\le i&lt;j\le k$</code> then the $i$-th path is never above the $j$-th path. I don't know of any interpretation in terms of polytopes.</p> http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81562#81562 Answer by Timothy Foo for Higher-dimensional Catalan numbers? Timothy Foo 2011-11-22T00:41:27Z 2011-11-22T00:41:27Z <p>This is not really an answer, but I'm just wondering if there are generalizations (in $2$-dimensional setting) of the form: number of paths from $(0,0)$ to $\left(n,\left\lfloor mn \right\rfloor\right)$ that stay below the line $y=mx$? And would that have other interpretations?</p> http://mathoverflow.net/questions/81473/higher-dimensional-catalan-numbers/81602#81602 Answer by Romeo for Higher-dimensional Catalan numbers? Romeo 2011-11-22T12:11:26Z 2011-11-22T14:16:08Z <p>Two papers that both address your question along similar lines are:</p> <p>(1) <em>Free n-category generated by a cube, oriented matroids, and higher Bruhat orders</em> by Karpranov and Voevodsky and </p> <p>(2) <em>Arrangements of hyperplanes, higher braid groups and higher Bruhat orders</em> by Manin and Schechtman</p> <p><em>Maps between higher Bruhat orders and higher Stasheff-Tamari posets</em> by H. Thomas serves as a follow-up and fills in in some of the details, but has a different flavor. </p> <p>Briefly, paper (1) defines (among other things) a poset $S(n,k), 0 \leq k \leq n$, with $|S(n,2)|$ equal to the $n^{th}$ Catalan number. The objects of this poset are defined in 3 ways (and shown to be equivalent): combinatorially (via cyclic polytopes), as "homotopies of homotopies" and as elements of "the free $(n-k)$-category on the $n$-simplex". </p> <p>So if you like these definitions and think they are natural, $|S(n,k)|$ for $k >2$ gives you "higher dimensional" Catalan numbers.</p> <p>Paper (2) does something nice, too, but I can't remember what. </p>