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. ...

$\endgroup$
  • 3
    $\begingroup$ Google OEIS A133437 and see the Loday reference. $\endgroup$ – Tom Copeland Oct 14 '13 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$ – მამუკა ჯიბლაძე Oct 14 '13 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 Oct 14 '13 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 Oct 14 '13 at 13:45
  • 1
    $\begingroup$ That's why I posed the question "Why do polytopes pop up ,..?" $\endgroup$ – Tom Copeland Oct 29 '13 at 1:52
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.

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
  • 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 Dec 26 '14 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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