7.01i, 7.01j - Selections with constraints

7.01i, 7.01j - Selections with constraints

Choose groups whose members must satisfy quotas, minimum requirements or restrictions on who may serve together. You will multiply choices from separate categories, use complements for “at least”, and organise several simultaneous constraints into disjoint cases.

Selections with a fixed composition

Four men and four women are available for a panel of two men and two women. Two particular man–woman pairs cannot serve together. Is it enough to count the panels forbidden by each pair and subtract both counts? A panel containing both pairs would then be subtracted twice. We will find a count that keeps every case separate.

Begin with a simpler restriction: a group must contain a specified number from each of two disjoint categories. Choose the members from one category, then choose the members from the other. Neither category gives the members different jobs or positions.

You already know

nCr{}^nC_r counts unordered selections of rr distinct members from nn. Multiply successive choices; add disjoint alternative cases. A count of selections is an integer, whereas a probability requires a further division by a total count.

The selections from the two categories combine uniquely into the final group, so the multiplicative principle applies.

Selecting from disjoint categories

From disjoint groups of sizes aa and bb, the number of selections containing exactly rr from the first and ss from the second is

aCr bCs{}^aC_r\,{}^bC_s

Here 0≤r≤a0\le r\le a and 0≤s≤b0\le s\le b, and the final selection has no order.

Not in the formula booklet: learn it.

The individual combination formula is in the booklet; deciding which choices to multiply is the modelling step.

Worked example 1: a team with two quotas

Question. A group contains 66 men and 55 women. Calculate the number of teams consisting of 33 men and 22 women.

Plan. Select the men and women separately, then multiply.

choices of men=6C3=20unordered selectionchoices of women=5C2=10unordered selectionteams=20×10=200each men’s group pairs with every women’s group\begin{aligned} \text{choices of men}&={}^6C_3=20 &&\text{unordered selection}\\ \text{choices of women}&={}^5C_2=10 &&\text{unordered selection}\\ \text{teams}&=20\times10=200 &&\text{each men's group pairs with every women's group} \end{aligned}

Why this step? A team requires both choices. Adding 20+1020+10 would count groups of men or groups of women, rather than complete teams.

Answer. 200200 teams.

Check. Each team determines exactly one selected men's group and one selected women's group, so no team has been counted twice.

The next example changes only the number of men required. The pool and the women's quota remain the same.

Worked example 2: changing one quota

Question. From the same 66 men and 55 women, calculate the number of teams consisting of 44 men and 22 women.

Plan. Replace the men's combination and keep the women's choice unchanged.

teams=6C4 5C2meet both quotas=15×10=150evaluate\begin{aligned} \text{teams}&={}^6C_4\,{}^5C_2 &&\text{meet both quotas}\\ &=15\times10=150 &&\text{evaluate} \end{aligned}

Why this step? The question fixes the composition, so choosing any six of the eleven people would include teams with the wrong numbers of men and women.

Answer. 150150 teams.

Check. Choosing four of six men is equivalent to choosing the two men left out, so 6C4=6C2=15{}^6C_4={}^6C_2=15.

The categories must be genuinely disjoint for this simple product to describe distinct people.

Watch out

If categories overlap, such as “pianists” and “violinists”, separately choosing from each may select the same person twice. Identify the overlap and split into appropriate cases before multiplying.

For disjoint categories, one factor per quota is a clear and complete method.

Minimum requirements and complements

“At least” describes several possible compositions. Count them as disjoint cases, or subtract the simpler unwanted cases from the unrestricted total.

For a four-person group, “at least one experienced member” permits one, two, three or four experienced members. Its complement is the single case “no experienced members”. The best route depends on how many terms each approach needs.

Selection by complement

For a finite collection of possible selections,

number satisfying the condition=total number−number failing the condition\text{number satisfying the condition} =\text{total number}-\text{number failing the condition}

The satisfactory and failing cases must be disjoint and exhaust all possibilities.

Not in the formula booklet: learn it.

For more than one excluded composition, add the excluded counts only when those cases are disjoint.

Worked example 3: at least one experienced member

Question. Five experienced members and four novices are available. Calculate the number of four-person teams with at least one experienced member.

Plan. Count all four-person teams and subtract the all-novice team.

all teams=9C4=126choose any four of nineno experienced member=4C4=1all four novicesrequired teams=126−1=125use the complement\begin{aligned} \text{all teams}&={}^9C_4=126 &&\text{choose any four of nine}\\ \text{no experienced member}&={}^4C_4=1 &&\text{all four novices}\\ \text{required teams}&=126-1=125 &&\text{use the complement} \end{aligned}

Why this step? The forbidden event has one composition, whereas directly counting the permitted teams would require four compositions.

Answer. 125125 teams.

Check. The permitted counts are 5×4+10×6+10×4+5=20+60+40+5=1255\times4+10\times6+10\times4+5=20+60+40+5=125, according to whether the team has one, two, three or four experienced members.

The next example changes only the minimum, from one experienced member to two. There are now two excluded compositions.

Worked example 4: at least two experienced members

Question. From the same five experienced members and four novices, calculate the number of four-person teams with at least two experienced members.

Plan. Exclude teams with zero or one experienced member.

zero experienced=4C4=1all novicesone experienced=5C1 4C3=20choose the other three as novicesrequired teams=9C4−1−20exclude both disjoint cases=105evaluate\begin{aligned} \text{zero experienced}&={}^4C_4=1 &&\text{all novices}\\ \text{one experienced}&={}^5C_1\,{}^4C_3=20 &&\text{choose the other three as novices}\\ \text{required teams}&={}^9C_4-1-20 &&\text{exclude both disjoint cases}\\ &=105 &&\text{evaluate} \end{aligned}

Why this step? “At least two” includes two, three and four; its complement is “at most one”, rather than “exactly one”.

Answer. 105105 teams.

Check. Directly: 5C24C2+5C34C1+5C4=60+40+5=105{}^5C_2{}^4C_2+{}^5C_3{}^4C_1+{}^5C_4=60+40+5=105.

Choose whichever version has fewer clear, non-overlapping terms.

Watch out

Wrong: using 5C24C2{}^5C_2{}^4C_2 alone for “at least two experienced members”. That counts exactly two. Add the three- and four-experienced cases, or use the full complement.

Limits on one category also limit the other, because the team size is fixed.

Required and excluded members

A required member is already selected; an excluded member is removed from the available pool.

For example, if a five-person team must include AA, choose only the other four members. Do not give AA an extra position in the team: membership has no order. If two people must both be present, fix both before choosing the rest.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account