# Combinations of multisets with finite multiplicities

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.

• I am not sure I understand what a k-combination or a k-permutation is. – Qiaochu Yuan Jul 25 '10 at 16:39
• Oh, sorry for not making it clear: a $k$-combination means simply picking k terms 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. – Harun Šiljak Jul 25 '10 at 16:59
• Have you looked at Knuth's Volume 4 fascicle 3, in particular exercise 39 in section 7.2.1.4? – András Salamon Jul 25 '10 at 20:22
• @András: looking it right now - but I don't see how a formula for combinations I'm looking for could directly follow from a formula for partitions given there? – Harun Šiljak Jul 25 '10 at 21:26
• – მამუკა ჯიბლაძე Sep 15 '15 at 17:27

In addition to the OP's 2011 paper with Ž. Jurić:

A New Formula for the Number of Combinations of Permutations of Multisets
Applied Mathematical Sciences, Vol. 5, 2011, no. 18, 875-881

there is a paper by Thomas Wieder, also in 2011:

Generation of All Possible Multiselections from a Multiset
CSCanada Progress in Applied Mathematics, Vol. 2, No. 1, 2011, pp. 61-66

which approaches counting the $k$-combinations of a multiset (sub-multisets of a multiset) in terms of "selection matrices" (similar to contingency tables).

In addition to the references cited in these two papers, Frank Ruskey's 2003 work-in-progress Combinatorial Generation has Sec. 4.5.1 with algorithms based on representing $k$-combinations as weak compositions with restricted parts.