"MultiCatalan numbers"

Question

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

@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. — მამუკა ჯიბლაძე, Oct 14 '13 at 10:48
Some of the references cited in response to the earlier MO question, "Higher-dimensional Catalan numbers?," might help... — Joseph O'Rourke, Oct 14 '13 at 11:20
You read Section 6 of Loday's paper on inversion of power series and facets of associahedra, i.e. Stasheff polytopes? — Tom Copeland, Oct 14 '13 at 13:45
@TomCopeland Yes, it is all there, except these quotients of multinomials are not explicitly mentioned. Loday mentioned an operadic proof, do you know where one can find it? Alas, nobody can ask him about it anymore... — მამუკა ჯიბლაძე, Oct 14 '13 at 14:58
Here is another related post that I found here: Why do polytopes pop up in Lagrange inversion? — მამუკა ჯიბლაძე, Oct 14 '13 at 15:08
Follow link to a "Short Note on Lagrange Inversion" in OEIS A134685 for inversion for Taylor series, or e.g.f.s. The indexing is shifted since I kept the linear term unspecified. Converting the formula in those notes to the coefficients for a power series, or o.g,f., gives a formula, I think, is identical to your multinomial, noting that 2(n-1)-e(1) in my formula is 2 k_1+ + 3 k_2. + ... in your multinomial and n in my formula is k_1 + 2 k_2 + ... in yours. — Tom Copeland, Oct 14 '13 at 23:22
So explicit expressions for the coefficients are given in the OEIS entries, which match your expression after reindexing and simplifying. — Tom Copeland, Oct 14 '13 at 23:32
@TomCopeland Thanks, I've seen it, and yes, I agree it is given there. Still some mystery remains, do you agree? — მამუკა ჯიბლაძე, Oct 28 '13 at 21:24
That's why I posed the question "Why do polytopes pop up ,..?" — Tom Copeland, Oct 29 '13 at 01:52
Re-reading this I realized I did not explain why I was not satisfied with these comments already. Well, first these were comments rather than answers :) But more importantly, in none of the given links and references the numbers in question were explicitly given as a result of "unexpected" divisibility of multinomial coefficients... — მამუკა ჯიბლაძე, Mar 16 '14 at 06:30

score 12 · Accepted Answer · answered Oct 14 '13 at 17:58

12

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

answered Oct 14 '13 at 17:58

Ira Gessel

16,246

Perfect, thanks! I believe this is the reference – მამუკა ჯიბლაძე Oct 28 '13 at 21:25
The reference that says nothing about associahedra, the Catalan, nor super-Catalan numbers. – Tom Copeland Mar 02 '22 at 06:24

score 2 · Answer 2 · answered Oct 24 '14 at 09:53

2

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.

answered Oct 24 '14 at 09:53

Tom Copeland

9,937

1

See also Domb and Barrett, "Enumeration of ladder graphs" for some historical notes. (An inviscid Hopf-Burgers differential equation is introduced.) – Tom Copeland Dec 26 '14 at 23:15

"MultiCatalan numbers"

2 Answers2

Linked