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

I have been struggling with this problem and hope someone could help. I am trying a variation of non-repetitive combination scenario. I can use the formula n!/r!x(n-r)! to find non-repetitive combinations of size "r" from "n" numbers. However, these combination have repeating elements.

For example:

I have 9 letters - A, B, C, D, E, F, G, H, I I want to find unique sets of three letters such as:

A B C D E F G H I A D G B E H C F I B E G

etc

If I use the standard non-repetitive combination, I might get sets like A B C, A B D, A B E . In this case A and B are repeated in all sets.

Following are my questions: - How to calculate the number of combinations as described above? - How to calculate the available combinations if we allow k repeating elements. Example. For a combination of 4 elements, we set the k to 2. This means A B C D, A B E F are allowed but not A B C D and A B C E.

I read a ton of materials on combinations and permutations but none of them seem to be covering this scenario.

I would really appreciate if you can give some pointers and direction.

Thanks

share|improve this question
1  
It's not entirely clear to me what you are after, but I suspect you are groping towards the idea of a block design: en.wikipedia.org/wiki/Block_design . –  Robin Chapman May 31 '10 at 16:35
    
Try formulating in terms of the Hamming distance, as used in coding theory. en.wikipedia.org/wiki/Hamming_distance . Writing strings of 0s and 1s (with just three 1s) differing in all but two places, is probably clearer. You presumably want an example of such a "code". –  Charles Matthews May 31 '10 at 16:41

4 Answers 4

up vote 1 down vote accepted

I have deleted what was here as it was based on a misunderstanding of the problem. My current understanding of the problem is that, given positive integers $k\le n$ one wants the largest number of $k$-element subsets of an $n$-element subset, no two intersecting in more than one element. This has indeed been studied as part of coding theory. In the language of coding theory, we want the biggest binary code of length $n$, all codewords being of weight $k$, the code having minimal distance $2k-2$. The case $k=3$ is discussed at http://oeis.org/A001839 and the notes there also give references to the general case.

share|improve this answer
    
Yes. I am realizing it is a partitioning problem as I do more Google searches. Could you tell me how you reached on this formula. Also, if you know of any good reference documents for partitioning scenarios, please share. Thanks –  khuss Jun 1 '10 at 4:44
    
There are 9-choose-3 ways of getting the first subset, 6-choose-3 ways to get the second, 3-choose-3 ways to get the third, but the order of the subsets doesn't matter, so divide by the number of permutations of three objects, 3-factorial. –  Gerry Myerson Jun 1 '10 at 6:01
    
I guess this is not the solution I am looking for. I am trying to create sets that are truly unique - which means if you compare any two sets, the maximum number of common elements between them would be 1. Going back to the original example, if the letters are A, B, C, D, E, F, G, H, I the unique sets would be: ABC, DEF, GHI, ADG, BEH, CFI, AEI, BDI, CDH and CEG If I use the formula that you have given, I end up with much bigger possible combinations. I need to do this for thousands for records that's why I am looking for a general formula. Thanks for the help. –  khuss Jun 1 '10 at 14:17
    
Clearly, I didn't understand your question. So you want as many 3-element subsets as possible, each pair intersecting in at most one element. Consider $\matrix{a&b&c\cr d&e&f\cr g&h&i\cr}$ and take the rows, columns, and diagonals, including broken diagonals; abc, def, ghi, adg, beh, cfi, aei, bfg, cdh, ceg, bdi, afh (you had most but not all of these). In general, you want the largest number of $r$-element subsets of an $n$-element set, no two intersecting in more than one element, right? I think "combinatorial designs" might be the search phrase (and it is an MO-type question after all). –  Gerry Myerson Jun 1 '10 at 23:50

Yes. You captured it beautifully. Thanks Gerry! I didn't think it as a geometrical problem, which is very interesting. Now, I need to figure out if there is any standard way to generate these combinations for a very large set of numbers - let us say 1000 numbers. I imagine if I can solve it for small set, it could be scaled for a large set. Also, I need to find if there is any mathematical equation to calculate the number of possible sets that have at most one intersecting element.

share|improve this answer
    
If you follow the links at the sequences site, I think you'll find there are formulas for $r\le4$ but only estimates for $r\ge5$. Anyway, if you're happy with my answer, I think the usual thing to do is to click the check mark next to it. –  Gerry Myerson Jun 2 '10 at 5:26

I know this is an old thread, but I'm looking for the same exact algorithm. Unfortunately the ATT research link is broken. I was wondering if anyone had a new link, or has ideas on a solution. In my example, I have x people that I want to schedule 3 at a time, and no two people can be in a set together more than once. The diagonals example above works well for 9 people, but not sure if it will work for 12 or 15 people.

share|improve this answer
    
oeis.org/A001839 –  Brendan McKay Dec 30 '12 at 4:55

Whilst this may be a re-statement of Gerry Myerson's answer, the Frankl-Wilson theorem, or more explicitly in this case the Ray-Chaudhury-Wilson theorem, gives (asymptotically tight) bounds for these sorts of questions.

More explicitly if you want to choose a family $A$ of $r$ sets from a set of size $n$, and we want that for all $x,y \in A$, $|x \cup y| \in L$ where $L \subset \{0,1 \ldots r-1\}$ and $|L|=s$ then we can bound $|A| \leq {n \choose s}$.

So in particular if you want the intersection size to be less that $k$ you can take $L=\{0,1, \ldots , k\}$ and see that your family has size at most ${n \choose k}$.

share|improve this answer
    
It's not clear to me what bound your approach gives for the number of 3-element subsets of a 9-element set, no two intersecting in more than one element. How does it compare to 12? –  Gerry Myerson Oct 29 '13 at 23:15

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.