View Question
Q: Solving for a minimum number of combinations ( Answered ,   7 Comments )
 Question
 Subject: Solving for a minimum number of combinations Category: Science > Math Asked by: demeralda-ga List Price: \$30.00 Posted: 15 Sep 2004 12:49 PDT Expires: 15 Oct 2004 12:49 PDT Question ID: 401669
 ```I'm slow in math so bear with me. :) Alright, first of all, I have a list of adjectives (in this example, 140), which must be grouped into increments of 20. (The same for my solution, I am only interested in 120, 140, 160, 180, 200, etc.) For each increment of 20, I will assign a letter: A, B, C, etc. So I am dealing with 140 different adjectives, which is 7 lists of 20, ABCDEFG. I know that I can come up with a solution by hand where I have uniquely paired each of the 7 (ABC, ABD, ABE, etc.) In doing this, I come up with 35 possible ways to combine these 7 lists. What I am trying to do, however, is simply to make sure that every list gets the same exposure in as few expressions as possible. The rules are: - Each letter must appear the same number of times - Each 2-way combination (AB, BD, etc.) must occur the same number of times - I always want fewer exposures So, in this 140, 7 list of 20, ABCDEFG scenario, I can minimize the unique combinations to that of 7: ABC, ADE, AFG, BDF, BEG, CEF, CDG. In this solution, each letter is seen the same number of times (3 times), and each combination of letters occurs only once (AB, AC, AD.... EG, FG all pair only once). In some solutions, each combination may need to occur several times, BUT each combination must always be seen the SAME number of times. So, if this is the solution for 140, is there a rule/program/formula for solving for 200, 220, 240?``` Clarification of Question by demeralda-ga on 15 Sep 2004 13:20 PDT ```I'm sorry, I think I forgot one very important point! I'm trying to solve for combinations of 3.``` Request for Question Clarification by mathtalk-ga on 15 Sep 2004 20:14 PDT ```Hi, demeralda-ga: Please see my Comment below. If I have understood your Question correctly, then I could probably solve most of the specific cases you ask about. While there isn't exactly a general rule or formula that works for all sizes, enough is known about particular constructions to say for what numbers of lists a solution will exist. If you like I could post this information as an Answer, along with specific solutions for some smallish sizes like 9 lists. regards, mathtalk-ga```
 Subject: Re: Solving for a minimum number of combinations Answered By: mathtalk-ga on 16 Sep 2004 00:33 PDT Rated:
 ```Hi, demeralda-ga: The smallest possible designs that you're asking about (each pair of points appears but once) are called Steiner triple systems. Here's a link which gives the basic result about when they exist: [Steiner Triple System -- from MathWorld] http://mathworld.wolfram.com/SteinerTripleSystem.html These are special cases of balanced incomplete block designs, namely those for which the block size is 3 and the number of times each distinct pair appears is 1. There are a number of notations used, but it will be convenient to refer to these as (v,3,1)-designs. The general notation is: (v,k,?)-designs where v = number of points (or lists in your application), k = size of each block (which is 3 in your application), ? = number of times each disinct pair appears (1 is minimal). The theorem proved by T. P. Kirkman in 1847 is that (v,3,1)-designs exist exactly when the remainder of v divided by 6 is either 1 or 3: v ? 1,3 mod 6 So the most minimal designs exist only for 7 (which you know about) and 9 (which we'll show in a moment; it's given in the link above), and then for every multiple of 6 added to either 7 or 9. v = 7,9,13,15,19,21,25,... A solution for 9 points or lists is unique (up to rearranging the points) and where the solution you found is called the Fano plane, this is called an affine plane: {{a,b,c},{d,e,f},{g,h,i}, {a,d,g},{b,e,h},{c,f,i}, {a,e,i},{b,f,g},{c,d,h}, {a,f,h},{b,d,i},{c,e,g}} This will seem less mysterious if you compare the triples shown to the rows, columns, and (wrap-around) diagonals of this 3x3 array: a b c d e f g h i Thus exactly one "line" through every pair of (distinct) points. While the solutions for v = 7,9 are essentially unique (up to "isomorphism"), the number of nonisomorphic solutions grows rapidly. For v = 13 there are just two different solutions, then for v = 15 there are 80! Here's one way to construct a solution for v = 13. Consider these two blocks: {0,1,4} and {0,2,8} Now for each non-zero "residue" modulo 13, we add (mod 13) to each entry in both blocks to get two more blocks. The result is a collection of 26 "triples" that form a (13,3,1)-design: {{0,1,4},{0,2,8},{1,2,5},{1,3,9},{2,3,6},{2,4,10}, {3,4,7},{3,5,11},{4,5,8},{4,6,12},{5,6,9},{5,7,0}, {6,7,10},{6,8,1},{7,8,11},{7,9,2},{8,9,12},{8,10,3}, {9,10,0},{9,11,4},{10,11,1},{10,12,5},{11,12,2},{11,0,6}, {12,0,3},{12,1,7}} This construction is an example of using the method of differences. What makes it tick is that every possible nonzero difference 1-12 is produced when two values from the same one of our two "initial" blocks are subtracted mod 13. By virtue of this every pair of points appears in some block. Here's a quick sketch of a way to construct a (15,3,1)-design. Take the nonzero binary 4-bit words as your points: { 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 } and define a triple of this points {X,Y,Z} whenever: X xor Y = Z It's a property of the "exclusive or" operation that the above is equivalent to saying either X xor Z = Y or Y xor Z = X, so that these triples form well-defined subsets of size 3 (blocks). Now let's back up and consider what our options are for other values: v = 6, 8, 10, 11, 12 For some general results on balanced incomplete block designs, see the introductory sections of: [On the Existence of (v, 5, 1)-BIBDs by Clayton Smith] http://www.argilo.net/papers/bibd.pdf In particular Lemma 3 tells us that each point in a (v,k,?)-design will appear exactly: (v - 1) r = ? ------- (k - 1) times, ie. a whole number of times (the same number for each point), and will require this many blocks (the number of points, times how many appearance each makes, divide by the size of a block): b = vr/k Now for v = 6 and k = 3, we need ? even to get a whole number. The smallest possibility is ? = 2, so that each point appears r = 5 times. The number of blocks is then b = 6*5/3 = 10. One such (6,3,2)-design is this collection of ten blocks: {{a,b,c},{a,c,d},{a,d,e},{a,e,f},{a,b,f}, {b,d,e},{b,c,e},{b,f,d},{c,d,f},{c,e,f}} in which you can check each symbols appears five times and each distinct pair twice. That's still better than the complete block design on v = 6 points, which requires 20 blocks. However for v = 8 we cannot do better (with k = 3) than taking the complete block design. To see why, first look at the relationship on number of times r that each point appears: (v - 1) r = ? ------- = ? * (7/2) (k - 1) so again ? will need to be even. But also count the number of blocks: b = vr/k = r * (8/3) which implies that r must be divisible by 3. That requires (from above) that ? is divisible by 3 as well as 2, i.e. ? must be at least 6. And ? = 6 gives us just the 56 blocks of the complete block design. For v = 10 we already know that we need at least ? = 2. The following example shows this is possible, albeit using a bit different technique than what you might have expected! So far our examples have not used the same _triple_ more than once. In other words all our blocks were different. This next example of a (10,3,2)-design contains some _repeated_ blocks. However every distinct pair appears just twice among all the 30 blocks: {{1,2,3},{1,2,4},{1,3,4},{2,3,4}, {1,5,6},{1,5,7},{1,6,7},{5,6,7}, {1,8,9},{1,8,10},{1,9,10},{8,9,10}, {2,5,8},{2,5,8},{2,6,9},{2,6,9}, {2,7,10},{2,7,10},{3,5,10},{3,5,10}, {3,6,8},{3,6,8},{3,7,9},{3,7,9}, {4,5,9},{4,5,9},{4,6,10},{4,6,10}, {4,7,8},{4,7,8}} Despite the repeated blocks this is considerable better than the complete block design, which for v = 10 requires 120 blocks. For the construction of this particular example, see here: [Pairwise balanced designs] http://www.math.mun.ca/~davidm/4341/pbd.pdf The analysis we did before by counting how many times r that each point appears and how many blocks b there are (which must both be whole numbers) tells us this about the remaining cases v = 11,12: If v = 11, then ? must be at least 3. If v = 12, then ? must be at least 2. I'll need to do some further research to find designs of this types however. regards, mathtalk-ga``` Clarification of Answer by mathtalk-ga on 01 Oct 2004 07:55 PDT ```Hi, demeralds-ga: Here are a few more designs in which you may have an interest. I've labelled the points beginning with 0. These are among a large number of 2-designs cataloged at this Web site: [Database at DesignTheory.org] http://www.designtheory.org/database/ The first design has triples from 10 points in which every pair appears twice (and each point is used 9 times), but unlike my earlier example, this one has no repeated "blocks" (all the blocks are different): { 0, 1, 2 } { 0, 1, 3 } { 0, 2, 3 } { 0, 4, 5 } { 0, 4, 6 } { 0, 5, 7 } { 0, 6, 8 } { 0, 7, 9 } { 0, 8, 9 } { 1, 2, 3 } { 1, 4, 5 } { 1, 4, 9 } { 1, 5, 8 } { 1, 6, 7 } { 1, 6, 8 } { 1, 7, 9 } { 2, 4, 6 } { 2, 4, 9 } { 2, 5, 7 } { 2, 5, 8 } { 2, 6, 7 } { 2, 8, 9 } { 3, 4, 7 } { 3, 4, 8 } { 3, 5, 6 } { 3, 5, 9 } { 3, 6, 9 } { 3, 7, 8 } { 4, 7, 8 } { 5, 6, 9 } Here's a design on 11 points in which every pair appears 3 times among the "blocks" of three (triples), and no repeats among the blocks: { 0, 1, 3 } { 0, 1, 4 } { 0, 1, 7 } { 0, 2, 5 } { 0, 2, 7 } { 0, 2,10 } { 0, 3, 9 } { 0, 3,10 } { 0, 4, 5 } { 0, 4, 6 } { 0, 5, 9 } { 0, 6, 8 } { 0, 6,10 } { 0, 7, 8 } { 0, 8, 9 } { 1, 2, 4 } { 1, 2, 5 } { 1, 2, 8 } { 1, 3, 6 } { 1, 3, 8 } { 1, 4,10 } { 1, 5, 6 } { 1, 5, 7 } { 1, 6,10 } { 1, 7, 9 } { 1, 8, 9 } { 1, 9,10 } { 2, 3, 5 } { 2, 3, 6 } { 2, 3, 9 } { 2, 4, 7 } { 2, 4, 9 } { 2, 6, 7 } { 2, 6, 8 } { 2, 8,10 } { 2, 9,10 } { 3, 4, 6 } { 3, 4, 7 } { 3, 4,10 } { 3, 5, 8 } { 3, 5,10 } { 3, 7, 8 } { 3, 7, 9 } { 4, 5, 7 } { 4, 5, 8 } { 4, 6, 9 } { 4, 8, 9 } { 4, 8,10 } { 5, 6, 8 } { 5, 6, 9 } { 5, 7,10 } { 5, 9,10 } { 6, 7, 9 } { 6, 7,10 } { 7, 8,10 } Finally here is a design on 12 blocks in which every pair appears twice, but this design does have repeated blocks: { 0, 1, 2 } { 0, 1,11 } { 0, 2, 7 } { 0, 3, 6 } { 0, 3, 9 } { 0, 4, 8 } { 0, 4, 8 } { 0, 5, 7 } { 0, 5,10 } { 0, 6, 9 } { 0,10,11 } { 1, 2, 3 } { 1, 3, 8 } { 1, 4, 7 } { 1, 4,10 } { 1, 5, 9 } { 1, 5, 9 } { 1, 6, 8 } { 1, 6,11 } { 1, 7,10 } { 2, 3, 4 } { 2, 4, 9 } { 2, 5, 8 } { 2, 5,11 } { 2, 6,10 } { 2, 6,10 } { 2, 7, 9 } { 2, 8,11 } { 3, 4, 5 } { 3, 5,10 } { 3, 6, 9 } { 3, 7,11 } { 3, 7,11 } { 3, 8,10 } { 4, 5, 6 } { 4, 6,11 } { 4, 7,10 } { 4, 9,11 } { 5, 6, 7 } { 5, 8,11 } { 6, 7, 8 } { 7, 8, 9 } { 8, 9,10 } { 9,10,11 } regards, mathtalk-ga```
 demeralda-ga rated this answer: and gave an additional tip of: \$10.00 `mathtalk is the best, I hope I can bug him for more answers in the future!`

 Subject: Re: Solving for a minimum number of combinations From: sigfpe-ga on 15 Sep 2004 16:17 PDT
 ```Does the number 20 actually have anything to do with this problem? You talk about increments of 20 but when you list you give your list of combinations ABC, ADE, ... it doesn't seem like 20 has anything to do with it. It seems we're just looking at combinations from a set of 7 letters. Is this correct?```
 Subject: Re: Solving for a minimum number of combinations From: demeralda-ga on 15 Sep 2004 17:29 PDT
 ```In the example that was satisfactorily "solved", there were 7 sets of 20. Yes, 20 must always be used. Therefore, when I want to solve for 160, I'll have 8 sets of 20, meaning ABCDEFGH, and still trying to solve for a 3 letter combination (ABC, ABD, ABE...FGH, so forth). I want to be able to arrive at this solution for any time I add another increment of 20. Somehow I doubt there is, but if I could even make it to 240 (which is typically the largest data set I'm working with), it would be good. So for 240, I'll have 12 sets of 20, ABCDEFGHIJKL, and still trying to find the minimum number of outcomes of three letter combinations, and still satisfying the earlier stated rules. I hope that clarifies a bit.```
 Subject: Re: Solving for a minimum number of combinations From: mathtalk-ga on 15 Sep 2004 19:58 PDT
 ```Hi, demeralda-ga: I think the point sigfpe-ga is making is the same thought that struck me in reading your "solution" to the 140 adjectives case. The real constraints appear to have to do with using 7 lists, not 140 adjectives. You decided to use 20 as the size of a list, so clearly the factor of 20 has a significance to you. But in terms of the properties of the solution, what you are describing is known in the "math biz" as the Fano plane (or configuration): an arrangement of seven points into seven "lines", with each "line" containing three points and each point lying on three "lines", and any two "lines" intersecting in exactly one point. Your Question can then be interpreted to ask if there are similar configurations involving 6, 8, 9, 10, etc. lists where a list plays the role of a point in such designs. Letting each list (point) be represented by a different symbol, if you wish. Each "combination of 3" is a subset of size 3 of this set of symbols (lists or points). Taking all possible combinations of (say) seven things 3 at a time gives 35, as you noticed. This is known as a "complete block design" because it includes all possible combinations. Sometimes, as you've seen, it is possible to come up with a smaller collection of combinations which satisfies the conditions: 1) every symbol (list or point) appears the same number of times 2) every pair of distinct symbols appears the same number of times These are known as pairwise-balanced incomplete block designs, often abbreviated BIBD. Many generalizations of these kinds of designs have been proposed and studied, and they play an important role in the design of experiments which involve more than one variable or "factor". There is no rule or formula which simply gives one all the possible solutions, but for the fairly small numbers you are considering the solutions are all known. This area of mathematics (generally speaking) is combinatorics. regards, mathtalk-ga```
 Subject: Re: Solving for a minimum number of combinations From: demeralda-ga on 15 Sep 2004 20:19 PDT
 ```I'd say that is pretty much an answer. Yes, you're right, the 20 is irrelevant, what you are saying is correct, the number of sets (6, 7, 8... up to 12) and their solution is all I'm really interested in. You say for such small numbers, the combinatorics already has the answer out there somewhere. Where would I find a decent reference source for this? Thank you, you clarified what I could not.```
 Subject: Re: Solving for a minimum number of combinations From: demeralda-ga on 15 Sep 2004 20:22 PDT
 ```Sorry, I missed your clarification question from above. Yes, if you would post it as the answer (up to 9, as you stated) that would be fabulous. If you can do 10-12, which is my uppermost limit, I'd be happy to pay extra, since I haven't a clue how much work it takes. Just let me know. Thanks a ton, you sure helped!```
 Subject: Re: Solving for a minimum number of combinations From: demeralda-ga on 16 Sep 2004 10:25 PDT
 ```Let me know if you discover 11 and 12... your example for 10 already saved me a ton of headache. I'll be happy to post it as a new question, if that helps. I'll put the same price on it, too :) Thanks again!```
 Subject: Re: Solving for a minimum number of combinations From: demeralda-ga on 01 Oct 2004 09:19 PDT
 ```Thank you so much for remembering my problem! Now I'm *really* impressed! Please let me know if there's a way that I can offer you an additional tip, or if I should post it as a new question so you can answer. I'm very grateful, indeed. demeralda-ga```