2
$\begingroup$

I am wondering what sequences of integers there are, that are known to grow polynomially, are non-negative, monotone but lacks a combinatorial interpretation.

By combinatorial interpretation, they are given by counting some discrete class of objects, (say lattice points in a polytope, Young tableaux, lattice paths, etc).

For example, the function $k \mapsto c^{k\lambda}_{k\mu,k\nu}$ where $c$ is the Littlewood-Richardson coefficient, $\lambda,\mu,\nu$ are partitions, and $k\geq0$ is an integer, is a sequence that satisfies all above properties, but it has a combinatorial description.

Replace $c$ with the more general Kronecker coefficients, and we obtain a sequence of integers that satisfy all listed properties, and it is one of the big unsolved problems in combinatorial representation theory to give a combinatorial description of the Kronecker coefficients.

Another non-example is the super-Catalan numbers, $$C(m,n) = \frac{(2m)!(2n)!}{(m+n)!m!n!}$$ which lacks a combinatorial description in general, and is non-negative, integer and monotone for each fixed $m$. However, the growth is not polynomial (the case $m=1$ corresponds to 2 times the usual Catalan numbers).

Of course, there are many sequences of numbers above, so to clarify, I mean sequences that belong to some natural family, parametrized by some auxiliary parameter(s), for example partitions, as above.

$\endgroup$
2
  • $\begingroup$ The nth Kronecker coefficient is actually the number of ways you can draw a ball from an urn containing k balls, where k is the nth Kronecker coefficient. $\endgroup$
    – Arthur B
    Sep 26, 2014 at 13:54
  • $\begingroup$ @ArthurB: A combinatorial interpretation may not lead to bottomless recursions :). Also, it should be obvious from the interpretation that the sequence is non-negative and integral. $\endgroup$ Sep 26, 2014 at 14:00

0

Your Answer

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