Combinations of multisets with finite multiplicities

2010-07-25T12:32:19Z

The question may be of little interest to most people here on MathOverflow, but after browsing a pile of books in combinatorics, I had to ask it somewhere:

What are the most efficient formulae for calculating the number of $k$-combinations (and $k$-permutations) of multisets with finite multiplicities (i.e. combinations and permutations with repetition, but with restrictions on the number of repetition)?

I know that generating functions are often used for solving this kind of problems, but there has been a number of formulae used for such counting, such as Percy MacMahon's one ($m_i$ denotes multiplicities of $n$ different elements in the multiset):

$$C(k;m_{1},m_{2},\ldots,m_{n})=\sum_{p=0}^{n}(-1)^{p}\sum_{1\le i_{1}\le i_{2}\le\cdots\le i_{p}\le n}{n+k-m_{i_{1}}-m_{i_{2}}-\ldots-m_{i_{p}}-p-1 \choose n-1}$$

Are you aware of other formulae for it, or useful references in literature?

EDIT: Clearing up the statement: a $k$-combination means simply picking $k$ elements from the multiset (order not important). $k$-permutation is basically the same, but order is important. In the example above, the multiset is ${ m_1\cdot a_1,m_2\cdot a_2,\ldots m_n\cdot a_n}$, $a_i$ being the elements, $m_i$ being the multiplicities.

Combinations of multisets with finite multiplicities - MathOverflow

Combinations of multisets with finite multiplicities