Combinations of multisets with finite multiplicities - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T21:33:15Z http://mathoverflow.net/feeds/question/33273 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33273/combinations-of-multisets-with-finite-multiplicities Combinations of multisets with finite multiplicities Harun Šiljak 2010-07-25T12:32:19Z 2010-08-01T08:20:19Z <p>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:</p> <p>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)?</p> <p>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):</p> <p>$$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}$$</p> <p>Are you aware of other formulae for it, or useful references in literature? </p> <p>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.</p>