I would like to know if there is a formula for generating a number of combinations without replacement that exclude certain items.  For example, list of 13 different types of fruits of which 6 would be generated for each list.  However, certain items cannot appear together in the list. For example, bananas and apples can't be in the same list.
in Other Math Topics by

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.

1 Answer

A more important and meaningful question would be to ask if there is a reliable mathematical approach. Sometimes, but not always, a formula is the result of such an approach. I wouldn’t expect there to be a single formula, but rather a set of formulae to be used logically and systematically by thinking the problem through.

The first formula is one which determines the number of combinations given a set of items to choose from, and then selecting a certain number of these items. 

Suppose the list, or set X, of all items has size n and the two selection lists, List 1 and List 2, have equal size m. It’s clear that n≥2m. Then we come to the number of mutually exclusive items, size p≥2, for a set E of such items.

Start with nCr which is the number of combinations of r items chosen from a set of n objects. The calculation is n(n-1)(n-2)...(n-r+1)/(r(r-1)...(2)(1)). This can be written as a formula: n!/(r!(n-r)!). For example, the number of combinations of selecting 6 objects from a set of 13 is 13!/(6!7!)=13×12×11×10×9×8/(6×5×4×3×2×1)=1716.

To form two lists with NO exclusions (p=0), there are (nCm)((n-m)Cm) combinations. For example with n=13 and m=6 this is 13C6×7C6=12,012. For n=16 and m=6 it’s 16C6×10C6=1,681,680.

So one approach could be to calculate the no-exclusions figure then subtract the exclusion combinations. So next we look at the exclusions. We need to produce a set of exclusive combinations from the simple list of items that can’t appear together in the same list. So we remove these items from the main set, leaving n-p items. Now let’s use some set notation. X={x1 x2 ... xn}, and E={e1 e2 ... ep}, where these e elements also reside in X. Now we define set Y=X-E, which has size n-p, and consists of all items in X that are not also in E.

Next we start to build the exclusion combination set, S. We take a pair of elements from E, say e1 and e2, and then we combine these with m-2 elements of Y. We do this for all possible pairs of elements in E and m-2 elements from Y. We can work out pC2 × (n-p)C(m-2), where pC2 applies to E and (n-p)C(m-2) applies to Y. Then we calculate pC3 × (n-p)C(m-3) for sets of 3 elements in E, and so on up to pCp (all of E)=1 and (n-p)C(m-p).

For example: n=13, m=6, p=3 gives us 3C2×10C4+1×10C3=630+120=750. So the size of S is 750 in this case.

For n=16, m=6, p=4 we get 4C2×12C4+4C3×12C3+12C2=3,916 as the size of S.

Let’s take a simple example and apply what we have so far.

A SIMPLE CASE

X={a b c d e f g}, E={b d}, so n=7 and p=2. S={abd bcd bde bdf bdg} and the size of S=pC2×(n-p)C(m-2)=2C2×5C1=5 (2C2=1); Y=X-E={a c e f g} has a size of n-p=5. Lists 1 and 2 are to have 3 items each, so m=3.

Set of lists: Q is the set of all possibilities for List 1. The combinations are referred to as combos.

Q={abc abd abe abf abg acd ace acf acg ade adf adg aef aeg afg bcd bce bcf bcg bde bdf bdg bef beg bfg cde cdf cdg cef ceg cfg def deg dfg efg} (7C3=35 combos)

Next, we remove excluded combinations (the ones marked with strikethrough) and redefine Q as Q-S➝Q:

Q={abc abe abf abg acd ace acf acg ade adf adg aef aeg afg bce bcf bcg bef beg bfg cde cdf cdg cef ceg cfg def deg dfg efg} (30 combos)

For each combo in Q we need to work out a set of List 2 combos. First we ignore excluded combos, but mark them with strikethrough:

abc: {def deg dfg efg}  adg: {bce bcf bef cef}  cde: {abf abg afg bfg}

abe: {cdf cdg cfg dfg}  aef: {bcd bcg bdg cdg}  cdf: {abe abg aeg beg}

abf: {cde cdg ceg deg}  aeg: {bcd bcf bdf cdf}  cdg: {abe abf aef bef}

abg: {cde cdf cef def}  afg: {bcd bce bde cde}  cef: {abd abg adg bdg}

acd: {bef beg bfg efg}  bce: {adf adg afg dfg}  ceg: {abd abf adf bdf}

ace: {bdf bdg bfg dfg}  bcf: {ade adg aeg deg}  cfg: {abd abe ade bde}

acf: {bde bdg beg deg}  bcg: {ade adf aef def}  def: {abc abg acg bcg}

acg: {bde bdf beg def}  bef: {acd acg adg cdg}  deg: {abc abf acf bcf}

ade: {bcf bcg bfg cfg}  beg: {acd acf adf cdf}  dfg: {abc abe ace bce}

adf: {bce bcg beg ceg}  bfg: {acd ace ade cde}  efg: {abc abd acd bcd}

When the 20 marked ones are removed we are left with 100 combinations of List 1 with List 2. Half of these are duplicates, in that List 1 and List 2 are simply interchanged; for example, List 1=abc and List 2=def may be regarded as the same as List 1=def and List 2=abc. If this is the way combinations are to be measured then there are only 50 unique combinations.

I hope this gives you some idea of how to approach the problem.

by Top Rated User (1.1m points)

Related questions

1 answer
asked Mar 10, 2013 in Statistics Answers by anonymous | 743 views
Welcome to MathHomeworkAnswers.org, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!

Most popular tags

algebra problems solving equations word problems calculating percentages math problem geometry problems calculus problems math fraction problems trigonometry problems rounding numbers simplifying expressions solve for x order of operations probability algebra pre algebra problems word problem evaluate the expression slope intercept form statistics problems factoring polynomials solving inequalities 6th grade math how to find y intercept equation of a line sequences and series algebra 2 problems logarithmic equations solving systems of equations by substitution dividing fractions greatest common factor square roots geometric shapes graphing linear equations long division solving systems of equations least to greatest dividing decimals substitution method proving trigonometric identities least common multiple factoring polynomials ratio and proportion trig identity precalculus problems standard form of an equation solving equations with fractions http: mathhomeworkanswers.org ask# function of x calculus slope of a line through 2 points algebraic expressions solving equations with variables on both sides college algebra domain of a function solving systems of equations by elimination differential equation algebra word problems distributive property solving quadratic equations perimeter of a rectangle trinomial factoring factors of a number fraction word problems slope of a line limit of a function greater than or less than geometry division fractions how to find x intercept differentiation exponents 8th grade math simplifying fractions geometry 10th grade equivalent fractions inverse function area of a triangle elimination method story problems standard deviation integral ratios simplify systems of equations containing three variables width of a rectangle percentages area of a circle circumference of a circle place value solving triangles parallel lines mathematical proofs solving linear equations 5th grade math mixed numbers to improper fractions scientific notation problems quadratic functions number of sides of a polygon length of a rectangle statistics zeros of a function prime factorization percents algebra 1 evaluating functions derivative of a function equation area of a rectangle lowest common denominator solving systems of equations by graphing integers algebra 2 diameter of a circle dividing polynomials vertex of a parabola calculus problem perpendicular lines combining like terms complex numbers geometry word problems converting fractions to decimals finding the nth term range of a function 4th grade math greatest to least ordered pairs functions radius of a circle least common denominator slope unit conversion solve for y calculators solving radical equations calculate distance between two points area word problems equation of a tangent line multiplying fractions chemistry binomial expansion place values absolute value round to the nearest tenth common denominator sets set builder notation please help me to answer this step by step significant figures simplifying radicals arithmetic sequences median age problem trigonometry graphing derivatives number patterns adding fractions radicals midpoint of a line roots of polynomials product of two consecutive numbers limits decimals compound interest please help pre-algebra problems divisibility rules graphing functions subtracting fractions angles numbers discrete mathematics volume of a cylinder simultaneous equations integration probability of an event comparing decimals factor by grouping vectors percentage expanded forms rational irrational numbers improper fractions to mixed numbers algebra1 matrices logarithms how to complete the square mean statistics problem analytic geometry geometry problem rounding decimals 5th grade math problems solving equations with variables solving quadratic equations by completing the square simplifying trigonometric equation using identities
87,441 questions
99,039 answers
2,422 comments
16,939 users