The Central Idea
Suppose \(5\) people are available and we want to choose \(3\) of them for a committee.
The committee
\[ \{A,B,C\} \]is the same committee as
\[ \{B,A,C\} \]and
\[ \{C,B,A\}. \]Changing the order in which the same three people are listed does not create a new committee.
This is the defining feature of a combination.
What Is a Combination?
A combination is an unordered selection.
If \(r\) objects are chosen from \(n\) distinct available objects and the order of the selected objects does not matter, the result is a combination.
The key question is:
Would rearranging the selected objects create a new outcome?
If the answer is no, combination counting is appropriate.
Permutation versus Combination
Permutations and combinations differ only in whether order matters.
Suppose \(A\), \(B\), and \(C\) are selected.
As a permutation,
\[ ABC,\ BAC,\ ACB,\ CAB,\ BCA,\ CBA \]are six different ordered outcomes.
As a combination, all six represent the same three-object selection:
\[ \boxed{\{A,B,C\}}. \]Why Permutation Counting Overcounts
Suppose \(r\) distinct objects have already been selected.
Those \(r\) objects can be internally arranged in
\[ r! \]different orders.
If order does not matter, all \(r!\) of those permutations represent the same combination.
Therefore, we divide a permutation count by \(r!\).
Deriving the Combination Formula
The number of ordered selections of \(r\) objects from \(n\) distinct objects is
\[ P(n,r)=\frac{n!}{(n-r)!}. \]Each unordered selection has been counted
\[ r! \]times because its selected objects can be arranged in \(r!\) orders.
Divide:
\[ \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}. \]Thus,
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]Binomial Coefficient Notation
The expression
\[ \binom{n}{r} \]is read
\(n\) choose \(r\).
It counts the number of ways to choose \(r\) objects from \(n\) distinct objects when order does not matter.
Another common notation is
\[ C(n,r). \]The Combination Formula
For nonnegative integers \(n\) and \(r\) with \(0\le r\le n\),
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]Here:
- \(n\) is the number of available distinct objects;
- \(r\) is the number selected;
- order does not matter.
Example: Choose Three from Five
Choose \(3\) people from \(5\) for a committee.
\[ \binom{5}{3} = \frac{5!}{3!2!}. \]Expand only as far as necessary:
\[ \frac{5\cdot4\cdot3!}{3!\cdot2} = \frac{20}{2}. \]Therefore,
\[ \boxed{\binom{5}{3}=10}. \]Why the Same Three People Are Not Recounted
If we used permutations, selecting three people from five would give
\[ P(5,3)=5\cdot4\cdot3=60. \]But each three-person committee appears in
\[ 3!=6 \]different listing orders.
Therefore,
\[ \frac{60}{6}=10. \]That is exactly
\[ \boxed{\binom{5}{3}=10}. \]Order Test
A useful diagnostic is to swap two selected objects.
If the outcome changes, use permutation reasoning.
If the outcome stays the same, use combination reasoning.
For example, a committee containing \(A\) and \(B\) is unchanged if we list \(B\) before \(A\).
But first place \(A\), second place \(B\) is different from first place \(B\), second place \(A\).
Example: Choosing a Team
A coach chooses \(5\) players from \(12\) available players.
The order in which the players are selected does not matter.
Therefore,
\[ \binom{12}{5} = \frac{12!}{5!7!}. \]Simplifying,
\[ \boxed{\binom{12}{5}=792}. \]Example: Choosing a Subset
How many \(4\)-element subsets can be chosen from a set with \(9\) distinct elements?
A subset is unordered.
Therefore,
\[ \binom{9}{4} = \frac{9!}{4!5!}. \]Thus,
\[ \boxed{\binom{9}{4}=126}. \]Example: Choosing Cards
A five-card hand is chosen from a standard \(52\)-card deck.
The order in which the cards are dealt does not define a different hand.
Therefore, the total number of five-card hands is
\[ \boxed{\binom{52}{5}}. \]Numerically,
\[ \boxed{\binom{52}{5}=2598960}. \]Efficient Factorial Simplification
Large factorials should usually be simplified before they are evaluated.
For example,
\[ \binom{15}{3} = \frac{15!}{3!12!}. \]Expand \(15!\) only down to \(12!\):
\[ \frac{15\cdot14\cdot13\cdot12!}{3!\cdot12!}. \]Cancel:
\[ \frac{15\cdot14\cdot13}{6}. \]Therefore,
\[ \boxed{\binom{15}{3}=455}. \]Cancel Before Multiplying
In
\[ \frac{15\cdot14\cdot13}{6}, \]it is often easier to cancel factors before multiplying.
Since
\[ 6=3\cdot2, \]we can write
\[ \frac{15}{3}\cdot\frac{14}{2}\cdot13 = 5\cdot7\cdot13 = 455. \]This keeps intermediate numbers smaller.
Choosing \(r\) or Leaving Out \(n-r\)
Choosing \(r\) objects from \(n\) automatically determines which \(n-r\) objects are not chosen.
Therefore,
\[ \boxed{\binom{n}{r}=\binom{n}{n-r}}. \]This is called the symmetry identity for combinations.
Why the Symmetry Identity Works
Suppose we choose \(3\) people from \(10\).
Every three-person selected group corresponds to exactly one seven-person unselected group.
Thus,
\[ \binom{10}{3} = \binom{10}{7}. \]Algebraically,
\[ \frac{10!}{3!7!} = \frac{10!}{7!3!}. \]Example: Use Symmetry to Simplify
Evaluate
\[ \binom{20}{18}. \]Rather than choosing \(18\), use symmetry:
\[ \binom{20}{18} = \binom{20}{2}. \]Then
\[ \binom{20}{2} = \frac{20\cdot19}{2} = \boxed{190}. \]Boundary Case: Choose Nothing
There is exactly one way to choose no objects from \(n\) available objects: choose nothing.
Therefore,
\[ \boxed{\binom{n}{0}=1}. \]The formula confirms this:
\[ \binom{n}{0} = \frac{n!}{0!n!} = 1. \]Boundary Case: Choose Everything
There is exactly one way to choose all \(n\) objects.
Therefore,
\[ \boxed{\binom{n}{n}=1}. \]This also follows from the symmetry identity:
\[ \binom{n}{n} = \binom{n}{0} = 1. \]Boundary Case: Choose One
Choosing one object from \(n\) available objects gives
\[ \boxed{\binom{n}{1}=n}. \]There are simply \(n\) possible single-object selections.
Boundary Case: Leave Out One
Choosing \(n-1\) objects is equivalent to deciding which one object is left out.
Therefore,
\[ \boxed{\binom{n}{n-1}=n}. \]Combinations and Subsets
Every \(r\)-element combination of an \(n\)-element set is an \(r\)-element subset.
Thus,
\[ \boxed{\binom{n}{r}} \]is also the number of \(r\)-element subsets of an \(n\)-element set.
Example: Subsets of a Six-Element Set
A set has six elements. How many three-element subsets does it have?
\[ \binom{6}{3} = \frac{6!}{3!3!}. \]Therefore,
\[ \boxed{\binom{6}{3}=20}. \]Total Number of Subsets
An \(n\)-element set has
\[ \binom{n}{0} \]subsets of size \(0\),
\[ \binom{n}{1} \]subsets of size \(1\), and so on through
\[ \binom{n}{n}. \]Therefore, the total number of subsets is
\[ \sum_{r=0}^{n}\binom{n}{r}. \]This sum equals
\[ \boxed{2^n}. \]This identity will later connect combinations to the binomial theorem.
Why an \(n\)-Element Set Has \(2^n\) Subsets
Each element has two independent possibilities:
- included;
- not included.
Therefore, by the multiplication principle,
\[ 2^n \]subsets are possible.
Grouping these subsets by their sizes gives the identity
\[ \boxed{\sum_{r=0}^{n}\binom{n}{r}=2^n}. \]Combinations with a Required Object
Suppose \(r\) objects are chosen from \(n\), but one particular object must be included.
Fix the required object.
Then choose the remaining
\[ r-1 \]objects from the remaining
\[ n-1 \]possibilities.
Therefore, the count is
\[ \boxed{\binom{n-1}{r-1}}. \]Example: Required Committee Member
A committee of \(4\) is chosen from \(10\) people, and Alex must be on the committee.
Fix Alex.
Choose the remaining \(3\) members from the other \(9\):
\[ \binom{9}{3}. \]Therefore,
\[ \boxed{\binom{9}{3}=84}. \]Combinations with a Forbidden Object
Suppose \(r\) objects are chosen from \(n\), but one particular object may not be selected.
Remove that object from consideration.
Then choose \(r\) objects from the remaining \(n-1\):
\[ \boxed{\binom{n-1}{r}}. \]Example: Forbidden Committee Member
A committee of \(5\) is chosen from \(12\) people, but Blair cannot serve.
Choose all \(5\) members from the remaining \(11\):
\[ \binom{11}{5}. \]Therefore,
\[ \boxed{\binom{11}{5}=462}. \]At Least One of Two Particular Objects
Complementary counting is often efficient.
Suppose an \(r\)-element subset is chosen from \(n\) objects, and at least one of two particular objects must be included.
Count all selections:
\[ \binom{n}{r}. \]Subtract selections containing neither of the two particular objects:
\[ \binom{n-2}{r}. \]Therefore,
\[ \boxed{\binom{n}{r}-\binom{n-2}{r}}. \]Example: At Least One Required Pair Member
A committee of \(4\) is chosen from \(10\) people. At least one of Alex and Blair must serve.
All committees:
\[ \binom{10}{4}=210. \]Committees containing neither Alex nor Blair:
\[ \binom{8}{4}=70. \]Therefore,
\[ 210-70=\boxed{140}. \]Exactly One of Two Particular Objects
Suppose exactly one of two particular objects must be selected.
Choose which one of the two is included:
\[ \binom{2}{1}=2. \]Then choose the remaining \(r-1\) objects from the other \(n-2\):
\[ \binom{n-2}{r-1}. \]Therefore,
\[ \boxed{2\binom{n-2}{r-1}}. \]Example: Exactly One of Alex and Blair
A committee of \(5\) is chosen from \(12\) people. Exactly one of Alex and Blair must serve.
Choose which one serves:
\[ 2. \]Then choose the remaining four members from the other ten:
\[ \binom{10}{4}. \]Therefore,
\[ 2\binom{10}{4} = 2(210) = \boxed{420}. \]Both of Two Particular Objects Required
If two specified objects must both be selected, fix both.
Then choose the remaining
\[ r-2 \]objects from the remaining
\[ n-2. \]The count is
\[ \boxed{\binom{n-2}{r-2}}. \]Example: Both Required
A committee of \(6\) is chosen from \(14\) people. Alex and Blair must both be included.
Choose the remaining \(4\) members from the other \(12\):
\[ \binom{12}{4}. \]Therefore,
\[ \boxed{\binom{12}{4}=495}. \]Neither of Two Particular Objects Allowed
If two specified objects are both excluded, choose all \(r\) objects from the remaining \(n-2\).
\[ \boxed{\binom{n-2}{r}}. \]Choosing from Categories
Many combination problems require selections from several categories.
If the category choices are independent stages, multiply the corresponding combination counts.
For example, choosing \(2\) people from one group and \(3\) from another gives
\[ \binom{a}{2}\binom{b}{3}. \]Example: Mixed Committee
A committee must contain \(3\) engineers chosen from \(8\) engineers and \(2\) designers chosen from \(6\) designers.
Choose the engineers:
\[ \binom{8}{3}. \]Choose the designers:
\[ \binom{6}{2}. \]Multiply:
\[ \binom{8}{3}\binom{6}{2} = 56\cdot15 = \boxed{840}. \]At Least a Certain Number from a Category
Problems with phrases such as at least often require counting several cases.
Suppose a \(4\)-person committee is chosen from \(5\) engineers and \(4\) designers, with at least \(2\) engineers.
The possible engineer counts are
\[ 2,\ 3,\ 4. \]Count each case separately and add.
Example: At Least Two Engineers
Choose a \(4\)-person committee from \(5\) engineers and \(4\) designers, with at least \(2\) engineers.
Exactly \(2\) engineers:
\[ \binom{5}{2}\binom{4}{2}. \]Exactly \(3\) engineers:
\[ \binom{5}{3}\binom{4}{1}. \]Exactly \(4\) engineers:
\[ \binom{5}{4}\binom{4}{0}. \]Add:
\[ 10\cdot6+10\cdot4+5\cdot1 = 60+40+5 = \boxed{105}. \]Exactly a Certain Number from a Category
If a selection must contain exactly \(k\) objects from one category, choose those \(k\) from that category and choose the remaining objects from the other available categories.
For example, exactly \(2\) engineers on a \(5\)-person committee gives
\[ \binom{E}{2}\binom{D}{3} \]when all other members must be designers.
Example: Exactly Two Red Objects
A selection of \(5\) objects is chosen from \(7\) red objects and \(8\) blue objects. Exactly \(2\) must be red.
Choose \(2\) red:
\[ \binom{7}{2}. \]Choose \(3\) blue:
\[ \binom{8}{3}. \]Therefore,
\[ \binom{7}{2}\binom{8}{3} = 21\cdot56 = \boxed{1176}. \]Combination Counting by Cases
If several mutually exclusive selection patterns satisfy the problem, count each pattern separately and add.
This combines combinations with the addition principle.
The general structure is
\[ \boxed{\text{total}=\text{case 1}+\text{case 2}+\cdots}. \]Combination Counting with Sequential Stages
If a valid outcome requires several independent choices to be made together, multiply their counts.
For example,
\[ \binom{8}{2}\binom{5}{1} \]may represent choosing two objects from one category and one object from another.
This combines combinations with the multiplication principle.
Combinations and Card Hands
Card problems frequently use combinations because the order of cards in a hand does not matter.
For example, a five-card hand containing exactly two hearts can be counted by choosing
\[ \binom{13}{2} \]hearts and
\[ \binom{39}{3} \]non-hearts.
The count is
\[ \boxed{\binom{13}{2}\binom{39}{3}}. \]Example: Exactly Three Aces
How many five-card hands contain exactly three aces?
Choose \(3\) of the \(4\) aces:
\[ \binom{4}{3}. \]Choose the remaining \(2\) cards from the \(48\) non-aces:
\[ \binom{48}{2}. \]Therefore,
\[ \boxed{\binom{4}{3}\binom{48}{2}=4512}. \]Combinations and Binary Strings with Fixed Counts
Suppose a binary string of length \(8\) contains exactly three \(1\)'s.
Choose which three of the eight positions contain \(1\)'s.
The remaining positions automatically contain \(0\)'s.
Therefore,
\[ \boxed{\binom{8}{3}=56}. \]Connection to Repeated-Object Permutations
The same binary-string problem can be viewed as arranging
\[ 1,1,1,0,0,0,0,0. \]The repeated-object formula gives
\[ \frac{8!}{3!5!}. \]But this is exactly
\[ \binom{8}{3}. \]Thus combinations and repeated-object permutations are closely connected.
Pascal's Identity
One of the most important combination identities is
\[ \boxed{\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}}. \]It can be understood by focusing on one particular object.
Why Pascal's Identity Works
Suppose we choose \(r\) objects from \(n\), and focus on one particular object \(A\).
Every valid selection belongs to exactly one of two cases.
Case 1: \(A\) is not selected.
\[ \binom{n-1}{r}. \]Case 2: \(A\) is selected.
Then choose the remaining \(r-1\) objects from the other \(n-1\):
\[ \binom{n-1}{r-1}. \]Adding the disjoint cases gives
\[ \boxed{\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}}. \]Example: Pascal's Identity
Evaluate
\[ \binom{8}{3} \]using Pascal's identity.
\[ \binom{8}{3} = \binom{7}{3}+\binom{7}{2}. \]Since
\[ \binom{7}{3}=35 \]and
\[ \binom{7}{2}=21, \]we obtain
\[ \boxed{\binom{8}{3}=56}. \]Combinations and Pascal's Triangle
Pascal's triangle is built from binomial coefficients.
Row \(n\) contains
\[ \binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}. \]Pascal's identity explains why each interior entry equals the sum of the two entries above it.
A later lesson will develop Pascal's triangle systematically.
Combinations and the Binomial Theorem
The coefficients in the expansion of
\[ (x+y)^n \]are combinations.
For example,
\[ (x+y)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3y + \binom{4}{2}x^2y^2 + \binom{4}{3}xy^3 + \binom{4}{4}y^4. \]This connection will be developed in the later binomial-theorem lesson.
Why Binomial Coefficients Appear in Expansions
In
\[ (x+y)^n, \]each term in the expansion results from choosing either \(x\) or \(y\) from each of the \(n\) factors.
To create a term containing exactly \(r\) copies of \(y\), we choose which \(r\) of the \(n\) factors contribute \(y\).
There are
\[ \binom{n}{r} \]ways to make that choice.
Combinations as Counting Paths
Suppose a path consists of \(r\) rightward steps and \(s\) upward steps.
The total number of steps is
\[ r+s. \]Choose which \(r\) positions in the sequence contain the rightward steps:
\[ \boxed{\binom{r+s}{r}}. \]Equivalently, choose the \(s\) upward-step positions:
\[ \binom{r+s}{s}. \]Example: Grid Paths
A shortest path moves \(4\) steps right and \(3\) steps up.
Every shortest path contains seven total steps.
Choose which four positions contain rightward moves:
\[ \binom{7}{4}. \]Therefore,
\[ \boxed{\binom{7}{4}=35}. \]Combinations and Selection without Replacement
Combination problems typically involve selecting distinct objects without replacement.
Once an object has been selected, it is not selected again.
If repetition of selected types is allowed, a different model may be required. That topic will be developed in the lesson on multisets.
Common Error: Using a Permutation Formula
Suppose \(3\) committee members are chosen from \(8\) people.
Using
\[ P(8,3)=336 \]counts every committee in \(3!=6\) different orders.
The correct count is
\[ \binom{8}{3} = \frac{336}{6} = \boxed{56}. \]Common Error: Treating Distinct Offices as a Combination
If president, vice president, and secretary are assigned from \(8\) people, order matters because the offices are different.
The correct count is
\[ P(8,3), \]not
\[ \binom{8}{3}. \]A combination chooses a group. A permutation assigns an order or distinct roles.
Common Error: Using the Wrong Denominator
The combination formula is
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]Both denominator factors are necessary.
The factor \((n-r)!\) cancels the unused tail of \(n!\), while \(r!\) removes the internal reorderings of the selected objects.
Common Error: Forgetting a Required Object
If a particular object must be included, do not choose all \(r\) objects freely.
Fix the required object first.
Then choose only
\[ r-1 \]more objects from
\[ n-1. \]The count is
\[ \boxed{\binom{n-1}{r-1}}. \]Common Error: Multiplying Cases That Should Be Added
If a committee may contain either exactly two engineers or exactly three engineers, those are mutually exclusive cases.
Count each case separately and add.
Multiplication is used for sequential choices within one outcome. Addition is used for disjoint alternative cases.
Common Error: Adding Choices That Must Occur Together
If a committee must contain \(2\) engineers and \(3\) designers, both selections are required.
Therefore, multiply:
\[ \boxed{\binom{E}{2}\binom{D}{3}}. \]Adding the two counts would not represent complete committees.
Common Error: Expanding Large Factorials Completely
In
\[ \binom{30}{3}, \]there is no reason to calculate \(30!\) or \(27!\).
Write
\[ \binom{30}{3} = \frac{30\cdot29\cdot28}{3!}. \]Then simplify:
\[ \boxed{\binom{30}{3}=4060}. \]A Reliable Procedure for Combination Problems
- Identify the available distinct objects.
- Identify how many objects must be selected.
- Ask whether changing the order creates a new outcome.
- If order does not matter, use combination reasoning.
- Use \(\binom{n}{r}=\frac{n!}{r!(n-r)!}\) for an unrestricted selection.
- Fix required objects before choosing the remaining objects.
- Remove forbidden objects before choosing.
- Separate mutually exclusive cases and add them.
- Multiply independent category selections that occur together.
- Use complements when counting the forbidden case is easier.
A Reliable Formula Checklist
Before using
\[ \binom{n}{r}, \]verify that:
- there are \(n\) distinct available objects;
- exactly \(r\) are selected;
- the same object is not selected twice;
- order does not matter;
- any restrictions have been incorporated.
Example: Full Workflow
A six-person committee is chosen from \(14\) people. Alex must be included, and Blair must be excluded.
Fix Alex.
Remove Blair from consideration.
That leaves \(12\) unrestricted people from whom the remaining \(5\) committee members must be chosen.
Therefore,
\[ \binom{12}{5}. \]Thus,
\[ \boxed{\binom{12}{5}=792}. \]Practice 1: Basic Combination
Evaluate:
\[ \binom{7}{3}. \]Practice 2: Committee Selection
How many five-person committees can be chosen from \(11\) people?
Practice 3: Use Symmetry
Evaluate:
\[ \binom{18}{16}. \]Practice 4: Required Member
A committee of \(4\) is chosen from \(9\) people. Alex must be included. How many committees are possible?
Practice 5: Forbidden Member
A committee of \(5\) is chosen from \(12\) people. Blair cannot be included. How many committees are possible?
Practice 6: Exactly One of Two
A committee of \(4\) is chosen from \(10\) people. Exactly one of Alex and Blair must serve. How many committees are possible?
Practice 7: Category Selection
A committee must contain \(2\) people chosen from \(7\) engineers and \(3\) people chosen from \(8\) designers. How many committees are possible?
Practice 8: Fixed Number of Successes
How many binary strings of length \(9\) contain exactly four \(1\)'s?
Practice 9: Grid Paths
How many shortest grid paths use \(5\) steps right and \(3\) steps up?
Practice 10: Identify the Error
A student says that the number of ways to choose three people from eight is
\[ 8\cdot7\cdot6=336. \]Explain the overcounting and give the correct answer.
Practice Answers
Practice 1
\[ \binom{7}{3} = \frac{7!}{3!4!} = \frac{7\cdot6\cdot5}{6} = \boxed{35}. \]Practice 2
\[ \binom{11}{5} = \boxed{462}. \]Practice 3
Use symmetry:
\[ \binom{18}{16} = \binom{18}{2} = \frac{18\cdot17}{2} = \boxed{153}. \]Practice 4
Fix Alex and choose the remaining three members from the other eight:
\[ \binom{8}{3} = \boxed{56}. \]Practice 5
Exclude Blair and choose all five members from the remaining eleven:
\[ \binom{11}{5} = \boxed{462}. \]Practice 6
Choose which one of Alex and Blair serves:
\[ 2. \]Then choose the remaining three members from the other eight:
\[ 2\binom{8}{3} = 2(56) = \boxed{112}. \]Practice 7
\[ \binom{7}{2}\binom{8}{3} = 21\cdot56 = \boxed{1176}. \]Practice 8
Choose which four of the nine positions contain \(1\)'s:
\[ \binom{9}{4} = \boxed{126}. \]Practice 9
There are eight total steps. Choose the five positions containing rightward moves:
\[ \binom{8}{5} = \binom{8}{3} = \boxed{56}. \]Practice 10
The product
\[ 8\cdot7\cdot6 \]counts each three-person group in all
\[ 3!=6 \]possible orders.
Divide by \(6\):
\[ \frac{8\cdot7\cdot6}{6} = \boxed{56}. \]Equivalently,
\[ \boxed{\binom{8}{3}=56}. \]What to Remember
A combination is an unordered selection.
For \(n\) distinct available objects and \(r\) selected objects,
\[ \boxed{\binom{n}{r}=\frac{n!}{r!(n-r)!}}. \]The factor \(r!\) removes the internal reorderings of each selected group.
Important identities include
\[ \boxed{\binom{n}{r}=\binom{n}{n-r}} \]and
\[ \boxed{\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}}. \]The most important diagnostic question remains simple: does changing the order create a different outcome?
If not, combination reasoning is usually the correct model.
Where We Go Next
Ordinary combinations choose distinct objects without repetition. Some selection problems allow multiple copies of the same type or begin with collections that already contain repeated elements.
The next lesson, Multisets, develops the language and counting structure needed for selections and collections in which multiplicity matters.