← Introductory Combinatorics
第 1 章 · 20 分钟
The only act in counting: fix an equivalence, build a bijection
The two principles are one thing written twice.
概念地图
Equivalence
Before counting, say what counts as the same object.
深色为本章概念，浅色为其他章
陪练模式
不想只是读？让它带你走一遍。
导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。
Locus01
延伸阅读
Cantor · late nineteenth century · defining 'same size' by bijection
Defined two sets to be equally large when a one-to-one correspondence exists, rather than by counting each first. He argued against treating cardinality as given in advance; the cost is that the definition yields many counterintuitive results for infinite sets, and combinatorics uses almost only its finite case.
Foundational
The seventeenth- and eighteenth-century tradition · Pascal, Bernoulli, Euler
Accumulated algorithms for permutations, combinations and partitions out of gambling and series problems. They argued against enumerating case by case; the cost is that the formulas lived for a long time as recipes with no common explanation.
Turn
The bijective method in modern combinatorics · later twentieth century
Holds that the best proof of an identity is an explicit correspondence between the two sides, not algebraic manipulation. A direct reply to 'getting the number is enough', and the organising principle of this course.
Revision
Brualdi · Introductory Combinatorics, 5th edition
The subject of this course. The textbook puts the two basic principles first; this course merges them into one act — building a bijection — and moves 'what counts as the same object' in front of both.
Subject of this course
机制02
Fix the equivalence first
'How many ways can three people line up' has already made a decision before it is asked: the three are distinguishable. Swap them for three identical sheets of paper and the answer drops from 6 to 1. So the first step in counting is never arithmetic but saying what counts as the same object — in the language of groups, choosing an equivalence relation on the set of objects. Nearly every miscount later in this course traces back to this step being skipped.
机制A counting problem, through first fixing what counts as the same, acquires a determinate answer.
可迁移性测试
Move it to software testing: before asking how many test cases exist you must say when two inputs count as the same case — by parameter value or by the branch covered. The isomorphism breaks in that testing's equivalence classes are usually a human convention, while a mathematical equivalence relation is fully determined once written.
机制03
Build a bijection
With the equivalence fixed, all that remains is one job: put the hard-to-count set into a bijection with a set whose size is known. Addition, multiplication, stars and bars, recurrences, generating functions are all different ways of building that correspondence. Remembering them as five unrelated formulas is the most common way to learn this subject, and the most laborious.
机制A hard-to-count set, through a one-to-one correspondence with a set of known size, reduces the problem to a solved one.
可迁移性测试
Move it to stock-taking: instead of counting items on shelves, count the receiving slips — provided each slip corresponds to exactly one item. The isomorphism breaks in that a warehouse may hold goods with no slip, while a mathematical bijection must be proved to miss nothing and double nothing.
Derivation04
Both principles are special cases of a bijection
What is being proved: the addition and multiplication principles are not two independent rules; each is one explicit bijection.
The sets and are finite
A hypothesis. On infinite sets 'same size' behaves quite differently — Cantor's examples put a part in bijection with the whole.
Condition for addition: (read: A and B are disjoint)
A hypothesis. Drop it and the formula is immediately false; chapter 4 is entirely about what to do once it goes.
Condition for multiplication: the number of options at the second step does not depend on what was chosen at the first
A hypothesis. Weaker than independence but stronger than 'the same option set': only the count must match.
推导 · 0 / 4
Worked derivation05
Where it breaks when disjointness fails
A class has 18 taking mathematics and 15 taking physics. Is the number taking a course 33?
Ask first whether the problem says the two are disjoint, then see whether the bijection of derivation step 1 survives.
裂缝06
The boundary of this chapter's claims
争议地形07
本书主张
Counting rests on two principles; master them plus a handful of standard models (permutations, combinations, stars and bars) and most counting problems can be taken apart.
另一种看法
The bijective line holds that starting from the two principles leads learners to store counting as a batch of formulas; explicit correspondences should be required from the outset so that formulas are derived rather than remembered.
分歧扎在
The disagreement is rooted in a pedagogical decision — tools first or principle first — not in the mathematics. Both produce the same numbers; at issue is which organisation produces fewer errors.
什么证据能裁决
What would settle it is the distribution of error types: give two groups the same batch of non-standard counting problems and record their mistakes. If the formula-organised group makes more 'wrong formula' errors, the bijection-organised group more 'correspondence not built' errors, and the latter's overall error rate is lower, the bijective claim holds.
The evidence points to the bijective side, and the evidence itself is weak: existing comparisons are classroom observation rather than controlled trials. What is missing is a design that separates the teaching method from the teacher.
Boundary and counterexample08
The 'fix the equivalence' commitment as a testable specification
The modelling commitment under test: real counting objects have an objective 'what counts as the same', so a counting question has a unique answer.
Hypothesis dropped: the equivalence relation is uniquely determined when the question is asked
The prerequisite for a unique answer; where it is not, one sentence corresponds to several different problems.
The counterexample: 'how many execution paths does this code have' differs several-fold under a per-branch and a per-statement reading
Both answers are right and correspond to two different equivalence relations.
The observable: counts produced independently by several analysts on the same question
It must be the same natural-language question, with no convention agreed in advance.
What counts against it: the spread of results exceeds a pre-registered threshold and the disagreement traces to the equivalence rather than to arithmetic
Both conditions are needed; a miscalculation is not a counterexample.
Pre-registered failure condition: spread above threshold with the disagreement traced to the reading, or analysts reporting different equivalence relations
Either counts as the commitment failing.
推导 · 0 / 3
接口09
Which slot it hangs on
挂在哪个槽位The conclusion you already hold is probably 'count carefully' — a judgement about why counts go wrong. This chapter goes at that attribution.
Does this chapter (a) replace 'miscounts come from carelessness', or (b) constrain it to cases where the equivalence is already fixed?
慢变量Register two slow variables: how many of your recent counts had the equivalence written down, and how many times two people produced different totals. Look at the second first.
小结10
本章小结
01The first step in counting is fixing the equivalence, not arithmetic; a different 'same' is a different problem.
02The addition and multiplication principles are each an explicit bijection, not two independent rules.
03The whole condition for addition is disjointness; for multiplication, that the later count does not depend on the earlier choice.
04When a formula fails, go back to its bijection and see whether injectivity or surjectivity broke.
05The only step carrying observational risk is that those two conditions hold in the real case.
提取练习 · 合上书，先自己答一遍。
?Is 'the size of a disjoint union is the sum of the parts' (a) true by definition or (b) a modelling commitment about reality?
?Does 'pick a, then pick a larger number' fail the multiplication principle because of (a) disjointness or (b) the option count depending on the first choice?
Forced choice11
A · Identify the mechanism
Which of these is a mechanism?
二选一
Forced choice12
C · Locate the crack
In which situation does this framework give a confident and wrong answer?
二选一
读到这里，把它记为已读。