Combinations with Restrictions

In short

Many real counting problems come with conditions: a committee must include the class monitor, a team must have at least two bowlers, a hand of cards must not contain both jokers. The strategy is always the same — split into non-overlapping cases (or use complementary counting: total minus unwanted) and apply the combination formula within each case. The key techniques are forced inclusion/exclusion of specific elements, "at least one" via complement, "at most k" via case sums, and group-based selection where you draw from multiple pools.

A school cricket squad has 9 batsmen and 6 bowlers. The coach needs to pick a playing XI of 11 players, but with a restriction: the team must include at least 4 bowlers. Without any restriction, the selection would be \binom{15}{11}. With the restriction, the problem breaks into pieces — and each piece is a clean application of \binom{n}{r}.

That is the pattern of this entire article: take a restriction, translate it into cases, count each case, and add.

Forced inclusion and exclusion

The simplest restriction is "this specific item must (or must not) be in the selection."

Forced inclusion. If a particular object must be in every selection, place it aside first and then choose the remaining objects from the rest of the pool. If you need r objects from n and one specific object is always included, the count is \binom{n-1}{r-1} — you have already used up one slot and one object.

Forced exclusion. If a particular object must never appear, remove it from the pool entirely. The count becomes \binom{n-1}{r} — the same number of slots, but one fewer object to choose from.

Forced inclusion and forced exclusion partition the unrestricted count $\binom{n}{r}$ into two non-overlapping parts. Teams containing $X$ number $\binom{n-1}{r-1}$; teams without $X$ number $\binom{n-1}{r}$. Their sum is $\binom{n}{r}$ — this is exactly [Pascal's identity](/wiki/properties-of-combinations).

Multiple forced elements. If p specific objects must all be included and q other specific objects must all be excluded, place the p objects aside, remove the q objects from the pool, and choose the remaining r - p objects from the remaining n - p - q:

\binom{n - p - q}{r - p}

This formula works as long as r - p \geq 0 and n - p - q \geq r - p.

"At least one" — the complement technique

The phrase "at least one" appears in a huge fraction of exam problems. Direct counting is often messy because "at least one" breaks into many cases. The shortcut is complementary counting:

\text{(at least one)} = \text{(total)} - \text{(none)}

Suppose you are choosing 5 cards from a standard deck of 52, and you want at least one ace. The total number of 5-card hands is \binom{52}{5}. The number of hands with no aces is \binom{48}{5} (choose all 5 from the 48 non-aces). So:

\text{hands with at least one ace} = \binom{52}{5} - \binom{48}{5} = 2{,}598{,}960 - 1{,}712{,}304 = 886{,}656

The complement technique turns a multi-case problem into a two-number subtraction.

Complementary counting. The total rectangle is all $\binom{52}{5}$ hands. The inner box is the $\binom{48}{5}$ hands with no aces. The shaded region — everything outside the inner box — is the set of hands with at least one ace. Subtraction is simpler than adding up the cases for exactly $1$, exactly $2$, exactly $3$, and exactly $4$ aces.

"At most k" — direct case summation

"At most k" means 0 or 1 or 2 or \ldots or k. You can either:

Sum the cases directly: count each case from 0 through k and add them up.
Use the complement: \text{(at most } k\text{)} = \text{total} - \text{(more than } k\text{)}, and "more than k" might have fewer cases.

Choose whichever approach gives fewer terms.

Example structure. From 8 men and 5 women, choose a committee of 5 with at most 2 women.

0 women: \binom{5}{0}\binom{8}{5} = 1 \times 56 = 56.
1 woman: \binom{5}{1}\binom{8}{4} = 5 \times 70 = 350.
2 women: \binom{5}{2}\binom{8}{3} = 10 \times 56 = 560.

Total: 56 + 350 + 560 = 966.

The complement approach would count committees with 3, 4, or 5 women and subtract from \binom{13}{5} = 1287. That gives \binom{5}{3}\binom{8}{2} + \binom{5}{4}\binom{8}{1} + \binom{5}{5}\binom{8}{0} = 280 + 40 + 1 = 321, and 1287 - 321 = 966. Same answer, slightly fewer terms.

Selection from multiple groups

Many problems require you to draw items from two or more separate pools. The key principle: choices from independent groups multiply.

If you need r_1 items from group A (of size m) and r_2 items from group B (of size n), the count is:

\binom{m}{r_1} \times \binom{n}{r_2}

When the restriction specifies a range (like "at least 2 from group A"), you sum over all valid splits of the total selection across the groups.

When selections from Group $A$ and Group $B$ are independent, the counts multiply. This is the [multiplication principle](/wiki/fundamental-principle-of-counting) applied to combinations.

Combining techniques: a recipe

Most restricted-combination problems use one or more of these four moves:

Forced inclusion/exclusion — lock in or lock out specific elements, reducing the pool.
Case split — break the problem by how many items come from each category.
Complement — count the unwanted selections and subtract from the total.
Multiply across groups — independent choices from separate pools multiply.

The art is recognising which combination of moves makes the problem cleanest. With practice, you develop an instinct: if the restriction says "at least one," reach for the complement; if it says "exactly k from this group," set up a product of two combinations; if it says "these two must not both be chosen," split into cases by which one is excluded.

Two worked examples

Example 1: A committee of $5$ is to be formed from $6$ men and $4$ women such that at least $2$ women are included. How many committees are possible?

Step 1. Identify the valid cases.

"At least 2 women" means the committee has 2, 3, or 4 women. (It cannot have 5 women because only 4 are available.)

Why: "at least 2" is the logical negation of "0 or 1," so the valid cases are 2, 3, 4.

Step 2. Count the case with exactly 2 women.

Choose 2 women from 4 and 3 men from 6:

\binom{4}{2} \times \binom{6}{3} = 6 \times 20 = 120

Why: the two selections are independent (women and men are different pools), so the counts multiply.

Step 3. Count the case with exactly 3 women.

\binom{4}{3} \times \binom{6}{2} = 4 \times 15 = 60

Why: 3 women fill 3 slots, leaving 2 slots for men.

Step 4. Count the case with exactly 4 women.

\binom{4}{4} \times \binom{6}{1} = 1 \times 6 = 6

Why: all 4 women are on the committee, and the fifth member is any one of the 6 men.

Step 5. Add the cases.

120 + 60 + 6 = 186

Result. 186 committees.

Complement check: total committees = \binom{10}{5} = 252. Committees with 0 women: \binom{6}{5} = 6. Committees with 1 woman: \binom{4}{1}\binom{6}{4} = 4 \times 15 = 60. Unwanted: 6 + 60 = 66. Answer: 252 - 66 = 186. The two methods agree.

The three valid cases, shown with red circles for women and grey for men. Each case is a product of two independent combinations, and the total is the sum of the three products. The complement approach ($252 - 66 = 186$) gives the same answer with fewer calculations.

The diagram makes the case structure visible: in each row, the red circles (women) and grey circles (men) together fill all 5 committee seats, and no two rows overlap.

Example 2: From the letters of the word MATHEMATICS, how many selections of $4$ letters can be made that include at least one M?

Step 1. Identify the distinct letters and their frequencies.

MATHEMATICS has 11 letters: M, A, T, H, E, M, A, T, I, C, S. The distinct letters are M, A, T, H, E, I, C, S — eight in total. M appears twice, A appears twice, T appears twice, and the rest appear once each.

For selections (combinations, not arrangements), what matters is which letters and how many of each. The available letters are: M (up to 2), A (up to 2), T (up to 2), H (up to 1), E (up to 1), I (up to 1), C (up to 1), S (up to 1).

Why: a "selection" ignores order — \{M, A, T, H\} and \{H, T, A, M\} are the same selection. But identical letters matter: choosing both M's is different from choosing one M.

Step 2. Use the complement: (selections with at least one M) = (all selections of 4) - (selections with no M).

Why: directly counting "at least one M" requires splitting into "exactly one M" and "exactly two M's," each with its own sub-cases. The complement is cleaner.

Step 3. Count all selections of 4 letters (no restriction).

This is a constrained problem because of the repeated letters. Group the selections by the number of repeated-letter pairs used. A "pair" means choosing both copies of M, A, or T.

0 pairs: choose 4 different letters from the 8 distinct letters: \binom{8}{4} = 70.
1 pair: choose which repeated letter provides the pair (3 choices: M, A, or T), then choose 2 more distinct letters from the remaining 7: 3 \times \binom{7}{2} = 3 \times 21 = 63.
2 pairs: choose 2 of the 3 repeated letters to use as pairs: \binom{3}{2} = 3.

Total selections of 4: 70 + 63 + 3 = 136.

Step 4. Count selections of 4 with no M.

Remove both M's from the pool. The remaining letters are A (up to 2), T (up to 2), H, E, I, C, S — seven distinct letters, two of which (A and T) can be used twice.

0 pairs: \binom{7}{4} = 35.
1 pair (A or T): 2 \times \binom{6}{2} = 2 \times 15 = 30.
2 pairs (both A and T): \binom{2}{2} = 1.

Total with no M: 35 + 30 + 1 = 66.

Step 5. Subtract.

136 - 66 = 70

Result. 70 selections of 4 letters include at least one M.

Complementary counting applied to the MATHEMATICS problem. The total pool of $136$ four-letter selections splits into $66$ that avoid M entirely (the inner box) and $70$ that include at least one M (the surrounding region). Subtraction gives the answer without needing to enumerate sub-cases for "exactly one M" and "exactly two M's."

The complement did the heavy lifting: instead of splitting "at least one M" into two sub-cases and further splitting each by the number of other pairs, you counted two self-contained totals and subtracted.

Common confusions

"At least one" means "exactly one." It does not. "At least one" means 1 or 2 or 3 or more. \binom{n}{r} with the complement technique counts all of these simultaneously.
"I can use complement counting for anything." You can, but it is only useful when the complement has fewer cases than the direct count. "At least 3 from group A" with many cases on the direct side and few on the complement side is a good fit. "Exactly 2 women" is already a single case — complement counting would make it harder, not easier.
"Forced inclusion means the element is always first." Combinations are unordered. "The monitor must be on the committee" means the monitor is one of the r chosen members — there is no first or last position. If you were counting permutations (ordered arrangements), position would matter, but for combinations it does not.
"I multiply across groups AND add across groups." You multiply when the choices are simultaneous (choosing men and women for the same committee). You add when the cases are mutually exclusive (the committee has 2 women or 3 women, not both). Mixing these up is the most common error in restricted-combination problems.
"Repeated letters do not affect combination counting." They do. When a letter appears multiple times, you can include one copy or two (or more), and each possibility is a separate case. The sub-cases in Example 2 (grouping by the number of pairs) are exactly the technique for handling this.

Going deeper

If you can handle forced inclusion/exclusion, "at least" and "at most" conditions, and multi-group selection, you are ready for division and distribution problems. The rest of this section is for readers interested in the inclusion-exclusion principle — a general technique that extends complementary counting to situations with multiple overlapping conditions.

The inclusion-exclusion principle

Complementary counting handles one condition: "at least one element from set A." What if you have two conditions? Three?

Suppose you want to count 5-card hands from a 52-card deck that contain at least one heart and at least one spade. Call H the set of hands with no hearts and S the set of hands with no spades. You want to exclude hands in H \cup S (hands that violate at least one condition). The inclusion-exclusion principle says:

|H \cup S| = |H| + |S| - |H \cap S|

|H| = hands with no hearts = \binom{39}{5} (choose 5 from the 39 non-hearts).
|S| = hands with no spades = \binom{39}{5}.
|H \cap S| = hands with neither hearts nor spades = \binom{26}{5} (choose 5 from the 26 diamonds-and-clubs).

So the number of hands with at least one heart and at least one spade is:

\binom{52}{5} - \left[\binom{39}{5} + \binom{39}{5} - \binom{26}{5}\right]

= 2{,}598{,}960 - [575{,}757 + 575{,}757 - 65{,}780] = 2{,}598{,}960 - 1{,}085{,}734 = 1{,}513{,}226

For three or more conditions, the pattern extends:

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

The signs alternate: add the singles, subtract the pairs, add the triples, and so on. This is the same inclusion-exclusion you may have seen in set operations, now applied as a counting tool. It turns up in derangement counting, in sieve methods, and in probability — any time multiple overlapping conditions need to be untangled.

The "at least k" generalisation

A variant of complementary counting handles "at least k from a specific group" without listing all cases. If you have m special objects and n ordinary objects, and you want selections of r that include at least k of the special objects:

\sum_{j=k}^{\min(m, r)} \binom{m}{j} \binom{n}{r - j}

This is simply the sum over all valid values of j (the number of special objects in the selection). When k = 1, the complement shortcut \binom{m+n}{r} - \binom{n}{r} is faster. When k \geq 2, this direct sum is usually the cleanest route.

Where this leads next

Restricted combinations are the workhorse of harder counting problems.

Division and Distribution — distributing objects into groups uses restricted combinations as the counting engine.
Properties of Combinations — the symmetry rule, Pascal's identity, and the row-sum formula that underpin the shortcuts used here.
Combinations — Basics — the foundation: what \binom{n}{r} is, where the formula comes from, and how it relates to permutations.
Permutations with Restrictions — the ordered analogue of this article, where arrangements come with conditions.
Set Operations — union, intersection, and complement, which provide the logical framework for inclusion-exclusion.