# Why is a general formula for Kostka numbers “unlikely” to exist?

In reference to Stanley's Enumerative Combinatorics Vol. 2: right after he has defined Kostka numbers (section 7.10), he mentions that it is unlikely that a general formula for $K_{\lambda\mu}$ exists, where $K_{\lambda\mu}$ is the number of semistandard Young tableaux of shape $\lambda$ and type $\mu$ with $\lambda\vdash n$ and $\mu$ a weak composition of $n$. Why? In particular, is this an expression of something rigorous, and if so, what?

-
Might be related to mathoverflow.net/questions/18597/… – draks ... Feb 2 '12 at 7:51

This is a really good question, the kind of question I think about from time to time. The problem with this question is that it is so much imprecise, it is basically open ended. Here are some variations on the way to make question precise.

1) By a "general formula" you mean a product of some kind of factorials. This is rather uninteresting, since it's unclear what those factorials would be. Kostka numbers tend to be chaotic, so I am sure you can find relatively small partitions with annoying large prime factors. What do you do next? One can also ask about asymptotic results which don't allow this, in the flavor of de Bruijn (see Section 6). But again there are too many choices to consider, and none are really enlightening.

2) There is a formal notion of #P-completness, a computational complexity class, loosely corresponding to hard counting problems (see WP). It is known that Kostka numbers are #P-complete (see this paper). This means that computing Kostka numbers in full generality is just as hard as computing the number of 3-colorings in graphs. 3SAT solutions, etc.

3) Continuing with the theme "formula" as a polynomial algorithm. Such "formulas" do exist in special cases then. For example, if the number of rows in both partitions is fixed, Kostka numbers become the number of integer points in a finite dimensional polytope (see e.g. this nice presentation), which can be computed in polynomial time (see this book).

4) Alternatively, there is a rather weak notion of "formula" due to Wilf (see here, by subscription). Roughly, he asks for the algorithm which is asymptotically faster than trivial enumeration. But then one can use the "inverse Kostka numbers" which have their own combinatorial interpretation (see here), which are similar but perhaps slightly faster to compute. Since Wilf only asks for a little better than trivial bound, one can compute the whole matrix of Kostka numbers which has sub-exponential size p(n), while Kostka numbers are exponential under mild conditions.

Hope this helps.

-
+1 nice. I have a related problem here. My question now is concerning eq.$(*)$: can it be efficiently evaluated if $m_\lambda=\left(1,0,0,\dots ,0\right)^T$? – draks ... Jul 13 '12 at 17:48