Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

Unfortunately, the maximum number of combinations under such a restriction is not known in any closed-form manner. The topic of constructing combinations like this is the topic of Block Design. There is a theoretical maximum, but there's no guarantee that the maximum can be achieved for any particular number of chosen elements or number of elements available.

share|improve this answer

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.

share|improve this answer

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.