Chapter 11: Combinations and Group Selection

A textbook lesson on counting groups, handling restrictions, and recognizing the structure behind classical probability word problems.

Chapter Overview

Committee of ThreePlain group selection. Feuding Council MembersSubtract forbidden pairs. Senior Analysts RequiredFill required seats first. Scholarship BoardAdd exact teacher-count cases. Drawers and DocumentsStars and bars distribution.

This chapter is about selection. A selection problem asks how many groups can be formed, not how many ordered lists can be written. The main skill is deciding which groups are legal before any arithmetic begins.

  • Counting begins by separating order-based arrangements from group-based selections.
  • The combination formula explains what changes when order no longer matters.
  • Classic committee and team problems are direct group selections.
  • Complement counting subtracts illegal groups when forbidden cases are easier to count.
  • Required-member problems are built directly by filling the forced seats first.
  • At-least conditions split into separate legal cases.
  • Stars and bars distributes identical objects into distinct buckets.

11.1 Choosing the Method

In counting, method selection comes before computation. A good solution begins by reading the story and deciding what makes two outcomes different.

  • Ask whether order is important. If swapping two chosen objects creates a new outcome, the problem is an arrangement problem.
  • Ask whether repeats are allowed. Repeated digits, repeated letters, and repeated selections usually change the counting model.
  • Ask whether restrictions exist. Words such as must, cannot, at least, together, apart, minimum, and exactly are signals to slow down.

Combinations enter when order is not important. A committee of Ana, Ben, and Cy is the same committee as Cy, Ana, and Ben. The names changed position, but the group did not change.

Core Concept

When the same members form the same outcome in any order, the problem belongs to combinations rather than permutations.

11.2 Core Formula

A combination counts the number of ways to choose $r$ objects from $n$ objects when order does not matter.

$$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$
Core Concept

The factor $r!$ divides away the repeated internal orders of each selected group.

What the Symbols Mean

  • $n$ is the total number of available objects, people, or choices.
  • $r$ is the number being selected.
  • $!$ means factorial, so $5!=5\cdot4\cdot3\cdot2\cdot1$.
  • $r!$ divides away the repeated orders inside each selected group.
  • $(n-r)!$ removes the unused objects from the ordered count.

The formula begins from an ordered count, then divides by the number of ways the selected group could have been rearranged without becoming a new group.

11.3 Simple Committees and Teams

The simplest combination problem gives one pool and one group size. No roles are assigned and no one has special restrictions.

Worked Example 11.3.1 — Committee of Three

A governing committee must elect three members from twelve candidates. Find the number of possible groups of three candidates that can serve on the committee.

  • The committee has no president, secretary, or ranked positions.\{A,B,C\} = \{C,A,B\}
  • Order is not important, so this is a combination.\binom{n}{r}
  • There are $n=12$ candidates and $r=3$ selected members.\binom{12}{3}
$$\binom{12}{3}=\frac{12!}{3!(12-3)!}=\frac{12!}{3!9!}=220$$

There are 220 possible committees.

11.4 Subtract Illegal Groups

Some restrictions are easiest to handle by first counting all possible groups and then removing the groups that break the rule. This is called complement counting: count the whole set, subtract the forbidden part.

Core Concept

When a restriction forbids a small, clean set of outcomes, count all groups and subtract the illegal groups.

Worked Example 11.4.1 — Feuding Council Members

A school council must choose four students from ten volunteers. Two students, Maya and Noor, refuse to serve together. How many valid councils can be formed?

  • Ignore the restriction first: choose any 4 students from 10.\binom{10}{4}
  • Count the illegal groups with Maya and Noor already included.\binom{8}{2}
  • Subtract the illegal groups from the total groups.\binom{10}{4}-\binom{8}{2}
$$\binom{10}{4}-\binom{8}{2}=210-28=182$$

There are 182 valid councils.

11.5 Build Legal Groups Directly

When the restriction says certain people must be included, it is often cleaner to build only legal groups. Put the required choices into the group first, then count the remaining open seats.

Core Concept

Required members occupy seats before the counting begins; only the remaining open seats still need to be chosen.

Worked Example 11.5.1 — Senior Analysts Required

A research team must choose five members from fourteen applicants. Two senior analysts must both be included on the team. How many possible research teams can be formed?

  • The two senior analysts are already locked into the team.
  • The team needs 5 people total, so 3 seats remain open.
  • The remaining 3 seats must be chosen from the other 12 applicants.
$$\binom{12}{3}=220$$

There are 220 possible teams.

11.6 Add Legal Cases

Minimum and "at least" conditions often create several legal cases. Count each legal case separately, then add the cases because each case represents a different kind of outcome.

Core Concept

At-least conditions become a sum of exact cases.

Worked Example 11.6.1 — Scholarship Board

A scholarship board chooses five reviewers from seven teachers and six community members. The board must include at least three teachers. How many valid boards can be formed?

  • "At least three teachers" means 3, 4, or 5 teachers.
  • For each case, choose the teachers and choose the remaining community members.
  • Add the legal cases because they do not overlap.
$$\binom{7}{3}\binom{6}{2}+\binom{7}{4}\binom{6}{1}+\binom{7}{5}\binom{6}{0}$$ $$=35\cdot15+35\cdot6+21\cdot1=756$$

There are 756 valid boards.

11.7 Stars and Bars: The Bucket Method

Stars and bars is the traditional name for distributing identical objects into distinct categories. The "stars" represent the objects. The "bars" are dividers that separate one bucket from the next.

For $r$ identical objects placed into $n$ distinct buckets, with empty buckets allowed: $$\binom{r+n-1}{n-1}=\binom{r+n-1}{r}$$
Core Concept

Stars and bars turns a distribution problem into the placement of dividers among identical objects.

What the Symbols Mean

  • $r$ is the number of identical objects being distributed.
  • $n$ is the number of distinct buckets, boxes, people, or categories.
  • $n-1$ is the number of dividers needed to separate the buckets.
  • $r+n-1$ is the total number of stars and bars in the model.

Worked Example 11.7.1 — Drawers and Documents

Ten identical reference documents are filed into four labeled drawers. A drawer may receive no documents. How many distributions are possible?

  • The documents are identical, so the order of documents does not matter.
  • The drawers are labeled, so the buckets are distinct.
  • Empty drawers are allowed, so the basic stars-and-bars formula applies.
$$\binom{10+4-1}{4-1}=\binom{13}{3}=286$$

There are 286 possible filing distributions.

Worked Example 11.7.2 — Training Tokens

A coach gives fifteen identical training tokens to five teams. Every team must receive at least two tokens. How many distributions are possible?

  • First give each team the required minimum of 2 tokens.5 \cdot 2 = 10
  • Find the number of tokens left to distribute.15 - 10 = 5
  • Distribute the remaining 5 identical tokens into 5 labeled teams.\binom{5+5-1}{5-1}
$$\binom{5+5-1}{5-1}=\binom{9}{4}=126$$

There are 126 possible distributions.

11.8 Combination Calculator

Use this calculator to connect the formula to the numbers in a problem. The result updates as soon as the values are changed.