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

My math skills are a bit rusty, I've run into this problem which is I'm sure a classic variation of combinatorics (please name it if so).

Given a set of N items to choose from, choose R (nCr), but there are a fixed number of repetitions allowed and then no more. For instance, 6 items (a,b,c,d,e,f), choose 6, 2 repeats allowed:

valid answers:

a,a,b,b,c,d
a,a,a,b,b,c
a,b,a,b,a,c   [edit: repeats don't have to be contiguous]
a,a,a,c,b,b   [edit: repeats don't have to be adjacent to each other]

invalid:

a,a,b,b,c,c

not sure (zero or one repeat may be allowed, but I don't know yet):

a,b,c,d,e,f
a,a,a,a,a,a
a,a,a,a,b,c
share|improve this question
    
You should try to improve the wording of your question: I don't think this is what most people would call the number of repetitions. –  Thierry Zell Nov 9 '10 at 14:04
add comment

1 Answer 1

Suppose we have n elements, we want to generate r elements (without order), and want exactly k elements to be repeated.

We can separate the result into a part containing all the repeated elements (the repeating part) and all the rest (the non-repeating part). Suppose the repeating part is of length m. There are $\binom{n}{k}$ ways to choose the distinct elements in the repeating part. Each of them appears at least twice, and the other m−2k elements are arbitrary, so can be chosen in $\binom{m-k-1}{k-1}$ ways. There are $\binom{n-k}{r-m}$ possible choices for the non-repeating part.

Putting it all together:

$\binom{n}{k} \sum_{m=2k}^r \binom{m-k-1}{k-1} \binom{n-k}{r-m}$

If you want to allow less repeating elements, just sum over k as well.

share|improve this answer
    
I'm trying to absorb this and it seemed I may not have stated that repeats don't have to be contiguous in the problem, does your solution still hold? –  harschware Jul 20 '10 at 3:05
    
I think so, you can punch in some numbers and check. –  Yuval Filmus Jul 23 '10 at 4:30
add comment

Your Answer

 
discard

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

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