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.

  • $\begingroup$ I am not sure I understand what a k-combination or a k-permutation is. $\endgroup$ – Qiaochu Yuan Jul 25 '10 at 16:39
  • $\begingroup$ 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. $\endgroup$ – Harun Šiljak Jul 25 '10 at 16:59
  • $\begingroup$ Have you looked at Knuth's Volume 4 fascicle 3, in particular exercise 39 in section $\endgroup$ – András Salamon Jul 25 '10 at 20:22
  • $\begingroup$ @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? $\endgroup$ – Harun Šiljak Jul 25 '10 at 21:26
  • 1

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.