## Combinations of multisets with finite multiplicities

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2010 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 2010 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 2010 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 2010 at 21:26
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8890790343284607, "perplexity_flag": "middle"}