Welcome to MathOverflow

Question

0

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

flag	asked May 31 2010 at 16:30 khuss 3●2

	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 2010 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 2010 at 16:41

Gerry Myerson · Accepted Answer · 2010-06-02 04:11:27Z UTC

0

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://www.research.att.com/~njas/sequences/A001839 and the notes there also give references to the general case.

edited Jun 2 2010 at 4:11

answered Jun 1 2010 at 0:21

Gerry Myerson
15.7k●1●47●87

	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 2010 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 2010 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 2010 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 2010 at 23:50

khuss · Answer 2 · 2010-06-02 04:42:51Z UTC

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.

Brian · Answer 3 · 2012-12-30 03:08:52Z UTC

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.

Creating a combinations with unique sets

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.