第 2 章 · 20 分钟

Ordered and unordered: how duplicates are given back

Permutations and combinations differ only in what you divided by.

概念地图

Return duplicates

Overcount, then divide by how many times each object was counted.

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

陪练模式

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

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

对话只存在本机

Locus01

延伸阅读

Pascal · seventeenth century · the arithmetic triangle

Systematised the recurrence and triangular arrangement of the binomial coefficients out of a gambling division problem. He argued against enumerating the plays; the cost is that at the time these numbers had an algorithm and no explanation — 'why this expression' waited a long time for a combinatorial proof.

Foundational

The eighteenth-century tradition · Bernoulli and Euler

Organised ordered and unordered, with and without repetition, into four recipes. This made the computation teachable; the cost is that four formulas look unrelated, hiding the single act they come from.

Turn

Stars and bars and bijective proofs · standard modern treatment

Uses an explicit correspondence to turn 'identical balls into distinct boxes' into 'choose the bar positions', reducing repeated combinations to ordinary ones. A direct reply to memorising four formulas separately.

Revision

Brualdi · the chapters on permutations and combinations

The subject of this course. The textbook lays the four cases out clearly; this chapter says that they differ in one place only — what you divided by, and why dividing is allowed.

Subject of this course

机制02

Overcount, then give it back

The usual route to an unordered count runs through an ordered one, and the step that gets you back this course calls returning duplicates. Its place in the argument is that it is the sole difference between a permutation and a combination — and it carries one hard condition. If some objects are counted six times and others three, dividing by six is wrong, and the whole of the next derivation turns on that.

机制An unordered count, through counting as ordered and dividing by each object's multiplicity, reduces to a solved problem.

可迁移性测试

Move it to meeting statistics: count ordered pairs 'who was in a meeting with whom', then divide by 2 to get the number of pairwise meetings — provided every pair was counted exactly twice. The isomorphism breaks in that real records may be one-sided (A logged it, B did not), and then dividing by 2 is wrong.

机制03

Bars: turning repetition into no repetition

'Put $n$ identical balls into $k$ distinct boxes' looks like a new problem, and the standard treatment moves it wholesale onto an old one by a device called stars and bars. It is the most typical use of chapter 1's principle — invent no new formula, build a correspondence — and it is worth noticing that the bars themselves carry no meaning; they are scaffolding for the correspondence and nothing else.

机制An allocation problem with repetition, through a correspondence with choosing bar positions, becomes an ordinary combination.

可迁移性测试

Move it to budget allocation: dividing a total among several departments is the same as choosing a few cut points on a ruler. The isomorphism breaks in that budgets usually carry a minimum per department, while the standard stars-and-bars form allows a box to receive zero — with a floor you must subtract it out first.

Derivation04

From permutations to combinations: why the division is legal

What is being proved is $(r n) = \frac{P ( n , r )}{r !}$ , with the weight on 'why you may divide'.

The n objects are distinct (read: n distinguishable objects)
A hypothesis. With identical objects the multiplicity is no longer uniform and the division fails at once.
Order among the r chosen objects is disregarded
A hypothesis, and chapter 1's equivalence relation: two arrangements with the same element set count as one combination.
Every r-element subset corresponds to exactly r! arrangements
A hypothesis, and the entire ground for the division; r! reads 'r factorial'.

推导 · 0 / 4

Worked derivation05

Why division fails with identical objects

How many arrangements does MISSISSIPPI have, and why can you not simply divide

11!

by one uniform number?

Count with every letter labelled distinct, then ask how many times each real arrangement was counted.

裂缝06

The boundary of this chapter's claims

争议地形07

本书主张

Ordered, unordered, with repetition and without are the four basic cases; four formulas plus their conditions cover most sampling problems.

另一种看法

The bijective line holds that the four formulas are one act applied four times, so only 'overcount and give back' and 'build a correspondence' should be taught, with the formulas derived by the learner.

分歧扎在

The disagreement is rooted in a pedagogical decision — remember the result or remember the act — not in the mathematics. Both compute the same numbers; at issue is which organisation errs less on non-standard cases.

什么证据能裁决

What would settle it is performance on non-standard problems: give two groups a batch of problems outside the four standard cases (allocations with floors, partially identical objects) and compare accuracy. Markedly higher accuracy in the act-organised group supports the bijective claim.

The evidence points to the bijective side and is weak: existing comparisons are classroom observation. What is missing is a controlled design separating the method from the teacher.

Boundary and counterexample08

The 'returning duplicates' commitment as a testable specification

The modelling commitment under test: in a real counting problem every object is over-counted the same number of times, so one division corrects it.

Hypothesis dropped: the multiplicity is the same for every object
The entire ground for the division; with uneven multiplicities no divisor is right.
The counterexample: meeting records where some meetings are logged by both parties and some by one, so dividing by 2 undercounts
The one-sided ones were counted once, the two-sided ones twice.
The observable: for the same raw records, the number of times each real object was recorded, checked item by item
It must be item by item; a total divided by a constant cannot reveal uneven multiplicity.
What counts against it: the distribution of multiplicities is not a single point and its spread exceeds a pre-registered threshold
The threshold is fixed in advance on how much unevenness costs the division its meaning.
Pre-registered failure condition: a non-degenerate multiplicity distribution, or a corrected total differing from an independent count beyond the threshold
Either counts as the commitment failing.

推导 · 0 / 3

接口09

Which slot it hangs on

挂在哪个槽位The conclusion you already hold is probably 'deduplication means deleting the repeats' — a judgement about data cleaning. This chapter goes at its operating condition.

Does this chapter (a) replace 'deduplication is deleting repeats', or (b) constrain it: only when every record has the same multiplicity may one division stand in for item-by-item deduplication?

慢变量Register two slow variables: how many of your counts use 'divide by a number' in place of item-by-item deduplication, and in how many of those you checked that the multiplicity is uniform. Look at the second first.

小结10

本章小结

01Permutations and combinations differ only in what you divided by, and the division rests on uniform multiplicity.

02The binomial coefficient is the direct consequence of 'every subset is counted exactly r! times', not a result to memorise.

03With identical objects the multiplicity stops being uniform; a non-integer quotient is the signal.

04Stars and bars builds a correspondence rather than inventing a formula; its standard form allows empty boxes, and a floor must be subtracted first.

05The only step carrying observational risk is that the real objects are distinct under that reading.

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

?Is 'the combination count is the permutation count divided by r!' (a) the arithmetic of equivalence classes or (b) a modelling commitment about reality?

?Does the MISSISSIPPI division work because (a) the denominator is computable or (b) every real arrangement has the same multiplicity?

Forced choice11

B · Identify the tag

'Every r-element subset corresponds to r! arrangements, so the quotient is the number of subsets' — what kind of step is that?

二选一

Forced choice12

D · Judge the interface

Which one hangs on a slot in your existing structure?

二选一

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