How do I calculate the number of combinations where a specified number of elements are not repeated?

My maths is very rusty. I am looking to calculate how many unique combinations I can draw from a given set of names.

I understand the formula $\frac{n!}{(n-r)!(r)!}$ will give me the number of unique combinations of $r$ elements from the set with $n$ elements, where all combinations will contain at least $1$ different element.

What if I wanted to specify the minimum number of elements that had to be different?

For example, the number of combinations of $6$ names I could draw from $36$ names = $\frac{36!}{30!\,6!}=1,947,792$

Every combination would have at least 1 name different to every other combination. How do I work out the number of combinations if I wanted at least 2 or 3 names in every combination to be different.

Names in the set are unique and can't be repeated.

Thank you.

• I am not sure but may be the Polard Rho algorithm may help in some sense: en.wikipedia.org/wiki/Pollard%27s_rho_algorithm – al-Hwarizmi Mar 27 '13 at 6:03
• Just to clarify - are you asking for how many combinations can be constructed when each combination can only share so many names, such as the classic case of 7 choose 3 with no pairs repeating: {123,145,167,246,257,347,356} (also known as the Fano plane)? – Glen O Mar 27 '13 at 6:22
• This is confused. The combinations your formula counts are combinations without repetition: all of the elements in the selection must be different. (If you wanted to allow the same element to appear more than once in a combination, then the formula would have to be $\frac{(n+r-1)!}{(n-1)!r!}$, but you say "Names in the set are unique and can't be repeated".) But then what do you mean by "if I wanted at least 2 or 3 names in every combination to be different"? All names already must be different. – Marc van Leeuwen Mar 27 '13 at 6:24
• One possible interpretation is that if you have chosen one cobination, you want other combinations to differ in at last 2 places. But that is not well defined, it is like asking "How many people live in this country if one only counts those that live at least 5 km apart?", it just insn't clear about which collection exactly you are talking. – Marc van Leeuwen Mar 27 '13 at 6:27
• Sorry to confuse everybody. I did say I was rusty! @GlenO - yes, i wanted to calculate all sets of 6 names where no more than a given number of names are the same. In the example I attempted to provide I meant how many sets of 6 names can I draw from 36 names where no more than 4 names are the same in any two sets. – Clair.Gibbon Mar 27 '13 at 8:27

The idea of the Hamming distance between each of your sets of six names would be useful. Each of your sets of six names would be considered a string of length $n=6$ from an alphabet set with $q=36$ elements.
By specifying a minimum number of elements to be different, you are specifying the minimum Hamming distance $d$ between each of the strings. There is then an upper bound to the number of possible strings that are at least $d$ apart from each other, given by the Hamming Bound, but it is not always achievable, as mentioned by Glen.