# Creating a combinations with unique sets

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

• 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

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.
• 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
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}$.