Given a multiset $M = \{ 1^{a_1} , 2^{a_2} ,\ldots , k^{a_k} \}$ where $N = \sum_j a_j$

$f(M, r)$ denotes the number of permutations of the multiset $M$ that have exactly $r$ strongly outstanding elements $$ f(M, r) = (\binom{N}{a_1} - \binom{N - 1}{a_1 - 1}) f(M/1^{a_1},r) + \binom{N - 1}{a_1 - 1} f(M/1^{a_1}, r-1) $$

Is there a closed form expression for this 'Stirling numbers of first kind over multiset' recursion?

I know that there is a closed form expression for $F_M(x) = \sum_rf(M,r)x^r$ which is the sum over all possible $r$ (but I want closed form expression for only a paritcular $r$).

[Encountered this when reading: http://www.math.upenn.edu/~wilf/website/LRMaxima.pdf ]


The formula given in the reference isn't exactly a "closed form"... and getting the coefficient of $x^r$ from it looks daunting.

  • $\begingroup$ that formula given in the reference is generating function. But what i needed is for a particular 'r' or sum for values of r in a given range, say [a, b]. $\endgroup$ – user92 Feb 11 '14 at 17:16

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.