STEP-BY-STEP LESSON · §9.5
Counting Subsets of a Set: Combinations
Distinguish selecting members from assigning an order.
Before you begin
Factorial
For positive integer n, n!=n(n−1)…1, and 0!=1. This counts orders of n distinct objects: n choices for the first position, then n−1, and so on.
Successive choices
If every first choice has the same number of continuations, multiply the numbers of choices at the stages. If branch sizes differ, add the branch counts. Decide first what makes two completed outcomes different.
Symbols
- n!
- product 1·2·…·n; 0!=1
- C(n,r)
- number of r-element subsets
- n,r
- Integers n≥0 and 0≤r≤n; population and subset sizes
Definitions and notation for this topic
Combinations / binomial coefficient
C(n,k)=n!/[k!(n−k)!]
For integers n≥0 and 0≤k≤n, C(n,k), also written as n above k in parentheses, counts k-element subsets of an n-element set.
Order is ignored and elements are not repeated. Dividing P(n,k) by k! removes the k! orders of every selected subset; C(n,0)=C(n,n)=1.
Separate glossary example
C(5,2)=10. The subset {A,B} is the same choice as {B,A}.
C(4,2)=6
Binomial theorem and Pascal’s identity
(a+b)^n=∑_{k=0}^{n} C(n,k)a^(n−k)b^kFor real a,b and integer n≥0, the binomial theorem expands (a+b)^n by choosing which k of the n factors contribute b.
Pascal’s identity is C(n,k)=C(n−1,k−1)+C(n−1,k) for n≥2 and 1≤k≤n−1; split subsets by whether they include a fixed element. Boundary values are C(n,0)=C(n,n)=1.
Separate glossary example
(a+b)³=a³+3a²b+3ab²+b³. Also C(5,2)=C(4,1)+C(4,2)=4+6.
Step by step
Step 1 / 6
Decide whether order matters
The team {A,B} equals {B,A}. “Chair A, secretary B” changes when swapped.
This determines which results are distinct.
Worked example
How many unordered pairs can be chosen from 5 people?
- The two team members have no different roles, so selecting AB or BA must count as one outcome.
- There are 5·4=20 ordered pairs.
- Each pair was counted twice: AB and BA. Thus 20/2=10.
Optional self-check
Compare choosing an unordered pair from four people with assigning two different roles to two of them.
Show answer
Unordered pairs: C(4,2)=6. Distinct roles: 4·3=12. Each unordered pair produces two role assignments.