第 3 章 · 22 分钟

Two ways: combinatorial proofs of identities

Algebra and a combinatorial argument give the same formula and not the same thing.

概念地图

Two ways

Count one set in two ways and an identity falls out.

深色为本章概念，浅色为其他章

陪练模式

不想只是读？让它带你走一遍。

导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。

对话只存在本机

Locus01

延伸阅读

Pascal · seventeenth century · the recurrence of the arithmetic triangle

Wrote down \(\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\) and built the triangle row by row from it. He argued against computing each coefficient separately; the cost is that the recurrence was then an observed regularity with no explanation.

Foundational

Newton and the generalised binomial theorem · late seventeenth century

Extended the expansion of \((x+y)^n\) to non-integer exponents, bringing binomial coefficients into analysis. This made algebraic methods dominant; the cost is that their combinatorial meaning stayed buried under algorithms for a long time.

Turn

The tradition of combinatorial proof · twentieth-century texts

Holds that the best proof of an identity shows that both sides count the same set, rather than reducing both sides to the same expression. A direct reply to purely algebraic treatment, and the act this chapter delivers.

Revision

Brualdi · the chapters on binomial coefficients and Pascal's triangle

The subject of this course. The textbook gives both algebraic and combinatorial proofs; this chapter says what the two differ in — what you walk away with.

Subject of this course

机制02

Count one set twice

To show two expressions are equal, the cheapest route is often not simplification but finding a set and showing that the left side counts it and so does the right. That practice is called a combinatorial proof. Its extra return is this: an algebraic proof tells you the equality holds, a combinatorial one also tells you why, and can therefore be modified when a neighbouring problem appears.

机制An identity, through having both sides count one set, is proved and explained at the same time.

可迁移性测试

Move it to reconciling accounts: match ledger and detail by summing each side, or by showing which ledger line each entry lands on. The second also tells you where a discrepancy would appear. The isomorphism breaks in that accounts really may fail to match.

机制03

Split on one particular element

There is essentially one way to build that correspondence: fix on a particular element and ask whether it is in. Each chosen object either contains it or does not, the two classes are disjoint and exhaust the whole, and the addition principle hands you a recurrence. Pascal's identity is the first instance, and chapter 5's recurrences are that act generalised.

机制A counting set, through being split on whether one particular element is in, falls into two disjoint parts and yields a recurrence.

可迁移性测试

Move it to sampling a committee: to count all possible review panels, ask first whether the chair is a particular person, and the answer cuts every arrangement into two non-overlapping heaps to be counted and added. The isomorphism breaks in that real categories may have fuzzy boundaries, while 'contains it or not' is entirely determinate.

Derivation04

Two identities: one by splitting, one by counting twice

What is being proved are Pascal's identity and the Vandermonde convolution, showing that both come from one act in two directions.

The n objects are distinct and 0≤r≤n
A hypothesis. Boundary cases need the convention (rn​)=0 for r<0 or r>n, or the recurrence fails at the edges.
Fix a particular element x
A hypothesis, and the whole content of the act: one particular element cuts the set in two.
Split the n objects into two groups of sizes m and n−m
A hypothesis for the second identity; choose one split and keep it fixed.

推导 · 0 / 4

Worked derivation05

One identity, two proofs, different takeaways

\sum_{r = 0}^{n} (r n) = 2^{n}

. Prove it algebraically and combinatorially, and compare what you keep.

Algebraically, substitute into the binomial theorem; combinatorially, count the subsets of a set.

裂缝06

The boundary of this chapter's claims

争议地形07

本书主张

Combinatorial identities can be proved algebraically or combinatorially; both are legitimate proofs and you choose by convenience.

另一种看法

The combinatorial-proof line holds that they are equal in strength and unequal in pedagogical and research value — only a combinatorial proof leaves a transferable correspondence, while algebra leaves a one-off simplification. Where a combinatorial proof is available, an algebraic one should not satisfy you.

分歧扎在

The disagreement is rooted in what a proof is for. To establish the conclusion, they are equal; to reuse on a neighbouring problem, the combinatorial proof leaves one extra modifiable object. Neither side disputes the mathematics.

什么证据能裁决

What would settle it is transfer to a neighbour: have two groups prove the same identity algebraically and combinatorially, then give a variant (adding a constraint) and compare solve rates. A markedly higher rate in the combinatorial group supports the unequal-value claim.

The evidence points to the combinatorial side and is equally weak: existing comparisons are teaching experience rather than controlled trials. What is missing is a design separating the difficulty of the variant from the proof style.

Boundary and counterexample08

The 'split on a particular element' commitment as a testable specification

The modelling commitment under test: a real classification really cuts the population into disjoint, exhaustive parts, so the class counts sum to the total.

Hypothesis dropped: the classification is disjoint and exhaustive
The prerequisite for the addition principle and the whole recurrence; with overlap or gaps the class counts do not sum to the total.
The counterexample: users classified as 'new' or 'returning', where someone who registered this month and came back is counted on both sides and the class counts exceed the total
The overlapping part was counted twice.
The observable: the difference between the sum of class counts and an independently obtained total
The total must come from an independent route, not from adding the classes.
What counts against it: the absolute difference exceeds a pre-registered threshold
The threshold is fixed in advance on the recording error of the data itself.
Pre-registered failure condition: the difference above threshold, or the existence of records fitting no class
The second points to non-exhaustiveness, the first usually to overlap.

推导 · 0 / 3

接口09

Which slot it hangs on

挂在哪个槽位The conclusion you already hold is probably 'a proof is for establishing the conclusion' — a judgement about what proofs are for. This chapter goes at the half it leaves out.

Does this chapter (a) replace 'a proof only establishes the conclusion', or (b) open a new slot about the transferability of a proof?

慢变量Register two slow variables: how many of your working results you can state a combinatorial meaning for, and how many you only remember as formulas. Look at the second first.

小结10

本章小结

01A combinatorial proof has both sides count one set, giving the equality and the reason together.

02'Split on whether a particular element is in' is the standard way to build the correspondence; Pascal's identity is the first instance.

03Vandermonde's convolution is the same act in the other direction: count the same set from another angle.

04Algebraic and combinatorial proofs are equal in correctness and unequal in the reusable act they leave.

05The only step carrying observational risk is that a real classification is disjoint and exhaustive.

提取练习 · 合上书，先自己答一遍。

?Is Pascal's identity (a) splitting and a bijection unpacked or (b) a modelling commitment about reality?

?Do class counts summing above the independent total indicate (a) overlap or (b) gaps?

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?

二选一

读到这里，把它记为已读。