Permutations and Combinations · Lesson 4 of 6
Choosing Without Regard to Order
“Count selections by removing the internal orders of each chosen group and connect the resulting identities.”
• Distinguish a selection from an ordered arrangement. • Derive the combination formula from the permutation formula. • Explain choosing–rejecting symmetry and the boundary values. • Derive the addition identity by algebra and separate cases. • Count committees, pairs and card selections without overcounting.
When changing order changes nothing
Three players X, Y and Z are available for a two-player team. The team containing X and Y is the same team whether we write XY or YX. Listing both would count one team twice. The possible teams are simply XY, XZ and YZ.
A combination is a selection of objects for which order does not matter. For n distinct objects, ⁿCᵣ counts selections of r objects, with each object selected at most once.
Ask what the outcome records. A committee is a set of members unless roles are specified. A chairperson–vice-chairperson assignment records who holds each role, so its order matters. The words “choose” and “select” alone do not settle this distinction; the definition of the result does.
Why each selected group has several orders
Select two objects from A, B, C and D. The six selections are AB, AC, AD, BC, BD and CD. Each selected pair has two orders: for AB these are AB and BA. Consequently, the twelve ordered pairs can be grouped into six selections, each with 2! orders.
With five objects A, B, C, D and E, the ten three-object selections are ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE and CDE. Each triple has 3! = 6 orders. Thus the 60 ordered triples consist of 10 groups of 6. Nothing about the internal order changes which triple was selected.
This grouping gives a derivation for any allowed r: select r distinct objects in ⁿCᵣ ways, then arrange the selected objects in r! ways. Their product counts exactly the same outcomes as choosing an ordered r-object arrangement directly. Dividing the permutation count by r! removes the internal orders of each group.
Problem
Twelve people each shake hands once with every other person. How many handshakes occur?
- 1.A handshake is an unordered pair of distinct people. A shaking hands with B is the same handshake as B shaking hands with A.
- 2.Count ¹²C₂=12!/(2!10!)=(12×11)/2=66.
- 3.The division by 2 removes the two orders of each pair. Counting 12 × 11 without division would count each handshake twice.
Problem
Seven distinct points lie on a circle. How many chords join pairs of these points?
- 1.Two distinct endpoints determine one chord. Their order does not matter, and different endpoint pairs produce different chords.
- 2.The count is ⁷C₂=(7×6)/2=21.
- 3.Each pair is counted once. A diameter, if one occurs, is still a chord and belongs in the count.
Choosing everything, nothing, or the complement
There is one way to choose all n objects: take the complete set. There is also one way to choose none: take the empty set. Choosing nothing is a single outcome, rather than a task with no outcomes. These boundary values agree with 0! = 1.
The symmetry can be seen without calculation. When six of ten people are chosen, the four left behind identify exactly the same decision. Algebra gives the same result: n!/[(n − r)!(n − (n − r))!] = n!/[(n − r)!r!]. The denominator factors are the same as for choosing r.
For valid a and b in one fixed row of combination counts, equal values ⁿCₐ=ⁿC_(b) imply a = b or a + b = n. To see why no other equalities occur, compare neighbouring counts. The ratio ⁿC₍ᵣ₊₁₎/ⁿCᵣ=(n-r)/(r+1) is greater than 1 before the middle. The counts rise to the middle and then mirror by symmetry; equal values therefore occur at matching or mirror positions.
Problem
If ⁿC₉=ⁿC₈, find ⁿC₁₇.
- 1.The selection sizes 9 and 8 are different, so they must be mirror positions: n = 9 + 8 = 17.
- 2.Alternatively cancel factorials to obtain (n − 8)/9 = 1, again giving n = 17.
- 3.Therefore ⁿC₁₇=¹⁷C₁₇=1, because all seventeen objects are selected.
The addition identity
Consider selecting r people from a group of n ordinary members and one distinguished member. Every selection either includes the distinguished member or does not. These cases cannot overlap and together cover every selection.
If the distinguished member is excluded, all r are chosen from the other n members: ⁿCᵣ ways. If included, choose the remaining r − 1 from those n: ⁿC₍ᵣ₋₁₎ ways. Add the separate cases to count all r-member selections from n + 1 people.
For an algebraic proof, expand both terms as factorials and use the common denominator r!(n − r + 1)!. The first numerator becomes n!(n − r + 1), and the second becomes n!r. Adding gives n![(n − r + 1) + r] = n!(n + 1) = (n + 1)!. The denominator is r![(n + 1) − r]!, so the result is ⁽ⁿ⁺¹⁾Cᵣ. Each change comes from making the denominators equal, not from adding factorial symbols.
Selections from several groups
Some groups must supply a fixed number of members. Make each required selection separately, then multiply, because one complete committee contains all those choices. If the permitted group compositions are alternatives, count each composition and add instead.
Problem
A group contains 2 men and 3 women. Count all three-person committees, then those with 1 man and 2 women.
- 1.There are five distinct people altogether. With no restriction, choose three: ⁵C₃=10.
- 2.For the restricted committee, choose one man in ²C₁=2 ways and two women in ³C₂=3 ways.
- 3.The complete committee requires both selections, so multiply: 2 × 3 = 6. Do not multiply by 3! because the committee has no internal roles.
Choosing cards carefully
A standard deck has 52 distinct cards: four suits of thirteen cards each. Hearts and diamonds are red; clubs and spades are black. Each suit has three face cards—jack, queen and king—so there are twelve face cards. A card selection ignores dealing order.
Problem
Count four-card selections, then selections with four cards of one suit, one from each suit, four face cards, two red and two black, or four cards of one colour.
- 1.Without restriction: ⁵²C₄=270725. The four chosen cards form a group, so internal orders do not count.
- 2.One suit: choose the suit in 4 ways, then choose 4 of its 13 cards. Count 4 × ¹³C₄ = 4 × 715 = 2860. The suit cases are separate.
- 3.One from each suit: make four required selections of one card. Count ¹³C₁ × ¹³C₁ × ¹³C₁ × ¹³C₁=13⁴=28561. Suit labels specify which group supplies each card; no extra 4! factor is needed.
- 4.Four face cards: choose 4 from the 12 distinct face cards, giving ¹²C₄=495.
- 5.Two red and two black: choose two from each set of 26. Count ²⁶C₂ × ²⁶C₂=325²=105625.
- 6.One colour: either all four are red or all four are black. Add the two separate cases: 2 × ²⁶C₄ = 2 × 14950 = 29900.
People and playing cards are distinct objects. Balls of the same colour are also distinct if each individual ball is available for selection. If a problem instead asks only for colour totals or explicitly calls copies indistinguishable, clarify that interpretation before applying a distinct-object combination formula.
Quiz
A three-person committee from eight people has no assigned roles. Which expression counts it?
How many handshakes occur when 6 people each shake hands once with every other person?
What is ¹⁰C₇ equal to?
What is ⁶C₃+⁶C₂?
Choose 2 people from a group of 4 and 1 from a separate group of 3. How many committees are possible?
Why divide ⁿPᵣ by r! when order is ignored?
Practice Problems
- If ⁿC₈=ⁿC₂, find n and then ⁿC₂.
- Solve ²ⁿC₃/ⁿC₃=12 and then the corresponding equation with ratio 11. State n ≥ 3.
- Count chords through 21 distinct points on a circle.
- Count teams of 3 boys and 3 girls selected from 5 boys and 4 girls.
- Count selections of 3 individually distinct red balls, 3 white balls and 3 blue balls from supplies of 6, 5 and 5 respectively.
- Count five-card selections containing exactly one ace. Include the restriction on the other four cards.
- Choose eleven players from seventeen, of whom five can bowl, with exactly four bowlers in the chosen team.
- Count selections of 2 black and 3 red individually distinct balls from 5 black and 6 red balls.
- Choose five courses from nine when two specified courses are compulsory. Explain how the compulsory choices change the remaining selection.
Key Takeaways
• A combination records membership rather than internal order. • Each r-object selection produces r! permutations. • The combination formula is n!/[r!(n − r)!]. • Choosing r and leaving n − r are equivalent descriptions. • The addition identity separates inclusion from exclusion of one object. • Multiply required group selections; add separate composition cases.