7
$\begingroup$

Could anyone provide a reference for the following (sort of) generalization of Catalan numbers: the multinomial coefficient $$ \binom{2k_1+3k_2+4k_3+...}{k_1+2k_2+3k_3+...,k_1,k_2,k_3,...} $$ is divisible by $k_1+2k_2+3k_3+...+1$.

Denoting the quotient by $C(k_1,k_2,k_3,...)$, one may call these the multiCatalan numbers. They definitely must appear somewhere in combinatorics, but I could not find any reference.

The reason I am sure these numbers must be known is that, for example: $(-1)^{k_1+k_2+...}C(k_1,k_2,...)$ is the coefficient at $x_1^{k_1}x_2^{k_2}\cdots$ of the composition inverse of the formal power series $t+x_1t^2+x_2t^3+...$;
$C(k_1,k_2,...)$ is the number of faces of the Stasheff polytope $S_{k_1+k_2+...}$ of shape $S_1^{k_1}\times S_2^{k_2}\times\cdots$ (here for convenience I have redenoted by $S_n$ the standard $K_{n+1}$; so $S_1$ is a point, $S_2$ a segment, $S_3$ a pentagon, etc.);
hence they also enumerate certain kinds of trees, etc., etc. ...

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ Google OEIS A133437 and see the Loday reference. $\endgroup$
    – Tom Copeland
    Commented Oct 14, 2013 at 10:13
  • $\begingroup$ @TomCopeland Thanks a lot for that. It is certainly to the point and certainly provided lots of additional information to me. However I must say (so far) I could not find explicit appearance of the above numbers there. It is also true that just unwinding the particular case of the Lagrange inversion gives these numbers, so this gives a proof of the divisibility. But I also wanted to explicitly refer to a place where these numbers actually appear. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 14, 2013 at 10:48
  • 1
    $\begingroup$ Some of the references cited in response to the earlier MO question, "Higher-dimensional Catalan numbers?," might help... $\endgroup$
    – Joseph O'Rourke
    Commented Oct 14, 2013 at 11:20
  • $\begingroup$ You read Section 6 of Loday's paper on inversion of power series and facets of associahedra, i.e. Stasheff polytopes? $\endgroup$
    – Tom Copeland
    Commented Oct 14, 2013 at 13:45
  • 1
    $\begingroup$ That's why I posed the question "Why do polytopes pop up ,..?" $\endgroup$
    – Tom Copeland
    Commented Oct 29, 2013 at 1:52

2 Answers 2

Reset to default
12
$\begingroup$

An early reference is W. T. Tutte, The number of planted plane trees with a given partition. Amer. Math. Monthly 71 (1964) 272–277.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Perfect, thanks! I believe this is the reference $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 28, 2013 at 21:25
  • $\begingroup$ The reference that says nothing about associahedra, the Catalan, nor super-Catalan numbers. $\endgroup$
    – Tom Copeland
    Commented Mar 2, 2022 at 6:24
2
$\begingroup$

If you reduce the partition arrays associated with these numbers, you get the face polynomials of the Stasheff associahedra or their simplicial duals, depending on the ordering. These are the vintage Kirkman-Cayley numbers of the late 1800's:

$$ K(n,k) = \frac{1}{k+1} \binom{n-3}{k} \binom{n+k-1}{k}\;.$$

Kirkman asserted they were the number of dissections of convex polygons in 1857, and Cayley gave the correct proof in 1890. See G. Gaiffi.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ See also Domb and Barrett, "Enumeration of ladder graphs" for some historical notes. (An inviscid Hopf-Burgers differential equation is introduced.) $\endgroup$
    – Tom Copeland
    Commented Dec 26, 2014 at 23:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .