Book of Proof, third edition
Richard Hammack · Free textbook
Read Book of Proof §§3.2, 3.4–3.6 (chapter 3 begins at PDF p.77); explain why k! counts orders.
Open the sourceCounting without listing everything
Products, choices, and polynomials as compressed inventories.
Prerequisites: 03 · Sets: the grammar of selection, 05 · From seeing a pattern to proving it
Understand
Objectives
- Separate ordered sequences from subsets of distinct labels.
- Enumerate size-two subsets and explain the division by 2!.
- Read each coefficient of a selection polynomial as a count.
Start with something you can see
Five labeled switches are either on or off. Before counting, decide whether “choose a then b” and “choose b then a” are different outcomes. They are different ordered instructions, but the same two-switch subset. Predict the number of unordered pairs before reading the table. The MIT counting lecture contrasts sets and sequences at 1:29. [1]
Give the idea a precise name
For a set of n distinct elements, C(n,k) counts its k-element subsets. Choosing in order produces n(n−1)⋯(n−k+1) sequences; each subset of distinct elements appears in exactly k! orders. A generating polynomial records one count at each selected size.
C(n,k)=n!/[k!(n−k)!]; (1+t)ⁿ=Σₖ₌₀ⁿ C(n,k)tᵏ
Here n is a nonnegative integer, 0≤k≤n, and the n available elements are distinct. The product n! runs from 1 to n, with 0!=1. In each factor (1+t), 1 means omit that element and t means include it. The exponent counts selected elements; the coefficient counts selections. The division by k! requires distinct selected elements so that every unordered selection really has k! different orders.
Work one small world
For switches {a,b,c,d,e}, the choice diagram below lists each pair once. Fix the first label and choose a later label: a→{b,c,d,e}, b→{c,d,e}, c→{d,e}, d→{e}. The branch sizes 4+3+2+1 give 10. There are 5×4=20 ordered distinct pairs; reversing each pair identifies two sequences. The polynomial (1+t)⁵ has coefficients 1,5,10,10,5,1.
| First label | Later choices (one subset each) | Pairs |
|---|---|---|
| a | ab, ac, ad, ae | 4 |
| b | bc, bd, be | 3 |
| c | cd, ce | 2 |
| d | de | 1 |
| e | none | 0 |
To obtain t² from (1+t)³, choose t from exactly two factors and 1 from the third: three different factor pairs contribute. The MIT expansion passage starts at 32:23. [2]
Counterexample to dividing every ordered count by k!: two draws from {a,b} with replacement give aa, ab, ba, bb. Reversal pairs ab with ba, but aa and bb each remain single outcomes. There are three unordered multisets, not 4/2=2; the distinct-element condition has failed.
THE BRIDGEA matroid removes forbidden selections; its count by size is no longer automatically binomial.
WHERE THIS IDEA STOPSA polynomial coefficient counts what its construction specifies. Do not confuse subset counts with signed characteristic coefficients.
Experiment
Cover the count column and predict each branch size. Add the branches, then compare the result with 5×4 ordered selections.
What does the exponent record, and what does its coefficient count?
Check & explain
How many distinct three-switch subsets can be chosen from five labeled switches?
Which polynomial inventories all subsets of five distinct switches by size?
- (1+t)⁵
- 5t²
- 5!t
Teach back
Enumerate the two-switch subsets of five labels, then derive the size-three coefficient without listing the triples. Explain why replacement changes the division.
- Name precisely what counts as one outcome.
- Group orders only when the selected labels are distinct.
- Interpret exponent as size and coefficient as number of subsets.
Read deeper
Discrete Mathematics: An Open Introduction, fourth edition
Oscar Levin · Open textbook
Read fourth-edition §§3.1 and 3.4 for binomial and combination counting.
Open the sourceLecture17: Counting Rules II
MIT OpenCourseWare · Lecture excerpt · 30:00–45:00 of 85 min
Watch 32:23–36:23 as the short core, or 30:00–45:00 for the longer binomial expansion; both are excerpts of the same 85-minute lecture.
Open the sourceLec 16 | MIT 6.042J Mathematics for Computer Science, Fall 2010
MIT OpenCourseWare · Lecture · 80 min
Begin at 1:29 to distinguish sets from sequences; the full 80-minute counting lecture is available from this card.
Open the source