Take the 2-minute tour ×

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,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]



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

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

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

Your Answer


