Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.