0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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 . $\endgroup$
    – Robin Chapman
    May 31, 2010 at 16:35
  • $\begingroup$ 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". $\endgroup$
    – Charles Matthews
    May 31, 2010 at 16:41

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user6491
    Jun 2, 2010 at 4:42
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jun 2, 2010 at 5:26
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Oct 29, 2013 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.