Finite Counting, Factorials and Binomial Coefficients: Examples and Counterexamples

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Pascal's triangle computed to row $6$ , with Pascal's rule checked at every interior entry

Example

The array whose $n$ -th row is $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$ is Pascal's triangle. Rows $0$ to $6$ are

$\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \\ 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \end{array}$

Every interior entry is produced below by Pascal's rule $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ , and the hockey-stick identity $\sum_{i \le n}\binom{i}{k} = \binom{n+1}{k+1}$ from the row above, the boundary entries being the values $\binom{n}{0} = \binom{n}{n} = 1$ ; four interior entries are cross-checked against the closed formula of $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ . The row sums and the alternating row sums are then checked against $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for $n \ge 1$ , including the row where the alternating sum is not zero.

Facts & Assumptions

Given: The binomial coefficients of The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ and the factorials $0! = 1$ , $1! = 1$ , $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ of The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ .

[L1]

Boundary values: $\binom{n}{0} = \binom{n}{n} = 1$ for every $n$ , and $\binom{n}{k} = 0$ for $k > n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

[L2]

Pascal's rule: $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ (Pascal's rule $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ , and the hockey-stick identity $\sum_{i \le n}\binom{i}{k} = \binom{n+1}{k+1}$ ).

[L3]

The closed formula: $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ , so $\binom{n}{k}$ is the natural number whose canonical natural is $\iota(n!)/(\iota(k!)\iota((n-k)!))$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ , The canonical natural $\iota(n) = n \cdot 1_F$ of a field).

[L4]

Row sums: $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\binom{n}{k} = 0$ for $n \ge 1$ ( $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for $n \ge 1$ , Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $\mathbb{R}$ , Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ).

Verification

technique · direct

1.1

Row $0$ is the single entry $\binom{0}{0} = 1$ , and row $1$ is $\binom{1}{0} = 1$ , $\binom{1}{1} = 1$ , both by [L1]. Every row begins and ends with $1$ for the same reason.

givenL1

2.1

The interior entries, each by [L2] from the row above. Row $2$ : $\binom{2}{1} = \binom{1}{0}+\binom{1}{1} = 2$ . Row $3$ : $\binom{3}{1} = \binom{2}{0}+\binom{2}{1} = 3$ and $\binom{3}{2} = \binom{2}{1}+\binom{2}{2} = 3$ . Row $4$ : $4$ , $\binom{4}{2} = 3+3 = 6$ , $4$ . Row $5$ : $5$ , $\binom{5}{2} = 4+6 = 10$ , $\binom{5}{3} = 6+4 = 10$ , $5$ . Row $6$ : $6$ , $\binom{6}{2} = 5+10 = 15$ , $\binom{6}{3} = 10+10 = 20$ , $\binom{6}{4} = 10+5 = 15$ , $6$ . This is the array displayed above.

step 1.1L1L2

3.1

The closed formula agrees, checked on four interior entries by [L3]: $\binom{4}{2}\cdot 2!\cdot 2! = 6\cdot 2\cdot 2 = 24 = 4!$ ; $\binom{5}{2}\cdot 2!\cdot 3! = 10\cdot 2\cdot 6 = 120 = 5!$ ; $\binom{6}{2}\cdot 2!\cdot 4! = 15\cdot 2\cdot 24 = 720 = 6!$ ; $\binom{6}{3}\cdot 3!\cdot 3! = 20\cdot 6\cdot 6 = 720 = 6!$ . So the two routes give the same numbers.

step 2.1L3

3.2

The row sums are $1$ , $1+1 = 2$ , $1+2+1 = 4$ , $1+3+3+1 = 8$ , $1+4+6+4+1 = 16$ , $1+5+10+10+5+1 = 32$ and $1+6+15+20+15+6+1 = 64$ , that is $2^{0}, 2^{1}, \dots, 2^{6}$ , as [L4] requires.

step 2.1L4

3.3

The alternating row sums are $1$ for row $0$ , and $1-1 = 0$ , $1-2+1 = 0$ , $1-3+3-1 = 0$ , $1-4+6-4+1 = 0$ , $1-5+10-10+5-1 = 0$ , $1-6+15-20+15-6+1 = 0$ for rows $1$ to $6$ . Row $0$ is the exception, and it is exactly the row where the hypothesis $n \ge 1$ of [L4] fails: the sum there has the single term $\binom{0}{0} = 1$ .

step 2.1L1L4

4.1

Rows $0$ to $6$ are as displayed, each interior entry agreeing with [L2] and the four checked in step 3.1 agreeing with [L3], the row sums with the powers of $2$ , and the alternating sums with $0$ from row $1$ onwards and with $1$ at row $0$ .

step 3.1step 3.2step 3.3∎

Remarks

The exceptional row is the point of the last check. A reader who computes only rows $1$ to $6$ sees an alternating sum that is always $0$ and will state the identity for every $n$ . Row $0$ is where that statement is false, and this page records it as a false statement for exactly that reason (FALSE: $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for every $n \in \mathbb{N}$ ).
Symmetry is visible in every row and is $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ clause 3: row $6$ read backwards is row $6$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

Choosing a committee: $\binom{10}{3} = 120$ , and the ordered count $10^{\underline{3}} = 720$

Example

Let $P$ be a set with $\lvert P\rvert = 10$ . Two different sets are counted, and naming which is which is the whole discipline of the example.

The unordered selections of three members of $P$ are the elements of $[P]^{3}$ , and there are $\binom{10}{3} = 120$ of them.
The ordered selections of three distinct members, that is the injections $3 \to P$ , number $10^{\underline{3}} = 720$ .

The ratio of the two counts is $3! = 6$ , which is clause 1 of $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ seen concretely: each $3$ -element subset arises from exactly $3!$ ordered selections.

Facts & Assumptions

Given: A set $P$ with $\lvert P\rvert = 10$ , and the factorials $3! = 6$ , $7! = 5040$ , $10! = 3628800$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L1]

$\lvert [P]^{k}\rvert = \binom{\lvert P\rvert}{k}$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ , and $\binom{n}{k}\,k! = n^{\underline{k}}$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ , clause 1).

[L3]

The number of injections of a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ (The number of injections from a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ ).

[L4]

$n^{\underline{0}} = 1$ and $n^{\underline{\sigma(k)}} = n^{\underline{k}}(n-k)$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

Verification

technique · direct

1.1

The two sets are $[P]^{3}$ , whose elements are the $3$ -element subsets of $P$ , and $\operatorname{Inj}(3,P)$ , whose elements are the injective functions from $3 = \{0,1,2\}$ into $P$ . They are different sets, and each count below is stated for the set it counts.

givenL1L3

2.1

The unordered count. By [L2] with $n = 10$ , $k = 3$ , $\binom{10}{3}\cdot 3!\cdot 7! = 10!$ , that is $\binom{10}{3}\cdot 6 \cdot 5040 = 3628800$ , so $\binom{10}{3}\cdot 30240 = 3628800$ and $\binom{10}{3} = 120$ . By [L1] the set $[P]^{3}$ has $120$ elements.

step 1.1L1L2

2.2

The ordered count. By [L4], $10^{\underline{1}} = 1 \cdot 10 = 10$ , $10^{\underline{2}} = 10\cdot 9 = 90$ and $10^{\underline{3}} = 90 \cdot 8 = 720$ . By [L3] the set $\operatorname{Inj}(3,P)$ has $720$ elements.

step 1.1L3L4

3.1

The two counts are related as clause 1 of [L2] says: $\binom{10}{3}\cdot 3! = 120 \cdot 6 = 720 = 10^{\underline{3}}$ . Each $3$ -element subset of $P$ is the image of exactly $3! = 6$ injections $3 \to P$ , so passing from the ordered to the unordered count divides by $6$ .

step 2.1step 2.2L2∎

Remarks

The standard error is to count one set and name the other. "How many ways can a committee of three be chosen from ten people" is the count of $[P]^{3}$ only if the committee is unordered; if the three roles are distinguished it is the count of $\operatorname{Inj}(3,P)$ . The two differ by a factor of $6$ , and no computation can decide which was meant.

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Arrangements of a word with repeated letters, counted by the multinomial coefficient

Example

Take the eleven-letter word $\mathrm{MISSISSIPPI}$ , over the four-letter alphabet $\{\mathrm{M},\mathrm{I},\mathrm{S},\mathrm{P}\}$ , in which $\mathrm{M}$ occurs once, $\mathrm{I}$ four times, $\mathrm{S}$ four times and $\mathrm{P}$ twice. The number of distinct arrangements of its letters is

$\binom{11}{1,4,4,2} = \frac{11!}{1!\,4!\,4!\,2!} = \frac{39916800}{1152} = 34650 .$

The modelling step is the mathematics. An arrangement is a function from the set of eleven positions to the four-letter alphabet whose fibre over each letter has the prescribed size; that is literally an element of $\mathcal{B}(A,k)$ in The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes, with $A$ the set of positions, $m = 4$ and $k = (1,4,4,2)$ .

Facts & Assumptions

Given: The position set $A$ with $\lvert A\rvert = 11$ , the alphabet identified with $4 = \{0,1,2,3\}$ by $0 \mapsto \mathrm{M}$ , $1 \mapsto \mathrm{I}$ , $2 \mapsto \mathrm{S}$ , $3 \mapsto \mathrm{P}$ , and the tuple $k = (1,4,4,2)$ ; the factorials $1! = 1$ , $2! = 2$ , $4! = 24$ and $11! = 39916800$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L1]

$\mathcal{B}(A,k)$ is the set of $c : A \to m$ with $\lvert c^{-1}[\{i\}]\rvert = k_i$ for every $i<m$ ; it is nonempty only if $\sum_{i<m}k_i = \lvert A\rvert$ , and its cardinality is $\binom{\lvert A\rvert}{k}$ (The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes, The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$\binom{n}{k}\prod_{i<m}k_i! = n!$ (The multinomial coefficient equals $n!/\prod_{i<m} k_i!$ , and $(x_0+\dots+x_{m-1})^{n} = \sum \iota\!\binom{n}{k}\prod_{i<m} x_i^{k_i}$ in $\mathbb{R}$ , clause 1).

[L3]

Finite sums and products in $\mathbb{N}$ and cancellation by a nonzero natural (Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ , Cancellation for multiplication by a nonzero factor).

Verification

technique · direct

1.1

The modelling. An arrangement of the letters of $\mathrm{MISSISSIPPI}$ is a function $c$ assigning to each of the eleven positions one of the four letters, subject to the letter multiplicities; that is, $\lvert c^{-1}[\{0\}]\rvert = 1$ , $\lvert c^{-1}[\{1\}]\rvert = 4$ , $\lvert c^{-1}[\{2\}]\rvert = 4$ and $\lvert c^{-1}[\{3\}]\rvert = 2$ . So the set of arrangements is exactly $\mathcal{B}(A,k)$ with $k = (1,4,4,2)$ .

givenL1

2.1

The hypothesis is satisfied, and it must be checked before the coefficient is written down: $\sum_{i<4}k_i = 1+4+4+2 = 11 = \lvert A\rvert$ , so $k \in \mathcal{W}(11,4)$ and $\binom{11}{1,4,4,2}$ is defined.

step 1.1L1L3

3.1

The value. By [L2], $\binom{11}{1,4,4,2}\cdot(1!\cdot 4!\cdot 4!\cdot 2!) = 11!$ , that is $\binom{11}{1,4,4,2}\cdot(1\cdot 24\cdot 24\cdot 2) = 39916800$ ; the product of factorials is $1152$ , and $1152 \cdot 34650 = 39916800$ , so cancellation by the nonzero factor $1152$ gives $\binom{11}{1,4,4,2} = 34650$ .

step 2.1L2L3

4.1

Hence the word has exactly $34650$ distinct arrangements, this being $\lvert\mathcal{B}(A,k)\rvert$ by [L1].

step 1.1step 3.1L1∎

Remarks

Why the letters are identified with $\{0,1,2,3\}$ . The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes takes the colour set to be a natural number, so the alphabet has to be presented as one; any bijection will do, and the count does not depend on which. A different identification permutes the tuple $k$ , and by clause 1 of The multinomial coefficient equals $n!/\prod_{i<m} k_i!$ , and $(x_0+\dots+x_{m-1})^{n} = \sum \iota\!\binom{n}{k}\prod_{i<m} x_i^{k_i}$ in $\mathbb{R}$ the coefficient is determined by $n$ together with the product $\prod_{i<m} k_i!$ , which a permutation of the parts leaves unchanged. The invariance clause of The multinomial coefficient $\binom{n}{k_0,\dots,k_{m-1}}$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes is a different statement: it says the count depends only on $\lvert A\rvert$ , that is, only on the domain up to bijection.
The check in step 2.1 is not a formality. If the multiplicities did not sum to the length, $\mathcal{B}(A,k)$ would be empty and the symbol $\binom{11}{k}$ would not be defined at all.

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

Five-card hands from a $52$ -card deck: $\binom{52}{5} = 2598960$ , and the count of hands with all cards of one suit

Example

Model a deck as the set $D := 13 \times 4$ , a rank paired with a suit, so $\lvert D\rvert = 52$ by The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$ , and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$ . A hand is a five-element subset of $D$ , that is an element of $[D]^{5}$ . Then

$\big\lvert [D]^{5}\big\rvert = \binom{52}{5} = 2598960 ,$

and the number of hands all of whose cards share a suit is

$4\cdot\binom{13}{5} = 4 \cdot 1287 = 5148 .$

No probability is claimed anywhere. There is no probability space in this library at this point in the reading order; these are counts of sets, and nothing below divides one by another or calls a count a chance.

Facts & Assumptions

Given: The deck $D = 13 \times 4$ ; for $s < 4$ the suit $D_s := 13 \times \{s\}$ ; and the falling factorials computed from $n^{\underline{0}} = 1$ and $n^{\underline{\sigma(k)}} = n^{\underline{k}}(n-k)$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L1]

$\lvert [X]^{k}\rvert = \binom{\lvert X\rvert}{k}$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$\binom{n}{k}\,k! = n^{\underline{k}}$ for $k \le n$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ , clause 1), and $5! = 120$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L3]

The product rule (The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$ , and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$ ) and the sum rule for a partition indexed by a finite set, with $\sum_{i \in S} c = \lvert S\rvert c$ (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form).

[L4]

Cancellation by a nonzero natural (Cancellation for multiplication by a nonzero factor).

Verification

technique · direct

1.1

The deck has $\lvert D\rvert = \lvert 13\rvert\cdot\lvert 4\rvert = 13 \cdot 4 = 52$ by [L3], and a hand is by definition an element of $[D]^{5}$ , so the number of hands is $\binom{52}{5}$ by [L1].

givenL1L3

2.1

The total. By [L2], $\binom{52}{5}\cdot 5! = 52^{\underline{5}} = 52\cdot 51\cdot 50\cdot 49\cdot 48$ . Computing the falling factorial step by step: $52\cdot 51 = 2652$ , $2652\cdot 50 = 132600$ , $132600\cdot 49 = 6497400$ , $6497400\cdot 48 = 311875200$ . Since $5! = 120$ and $120\cdot 2598960 = 311875200$ , cancellation by $120$ gives $\binom{52}{5} = 2598960$ .

step 1.1L2L4

2.2

The single-suit hands. Let $F$ be the set of hands all of whose cards lie in one suit, and for $s < 4$ let $F_s$ be the set of hands contained in $D_s$ . The $F_s$ are pairwise disjoint, since a hand has five cards and cannot lie in two different suits at once, and their union is $F$ . Each $D_s = 13\times\{s\}$ is in bijection with $13$ under the first projection, so $\lvert F_s\rvert = \lvert [D_s]^{5}\rvert = \binom{13}{5}$ by [L1]. By [L2], $\binom{13}{5}\cdot 120 = 13^{\underline{5}} = 13\cdot 12\cdot 11\cdot 10\cdot 9 = 154440$ , and $120\cdot 1287 = 154440$ , so $\binom{13}{5} = 1287$ . Finally [L3] gives $\lvert F\rvert = \sum_{s \in 4}\lvert F_s\rvert = 4\cdot 1287 = 5148$ .

step 1.1L1L2L3L4

3.1

So there are $2598960$ hands in all, of which $5148$ have all five cards of one suit. Both numbers are cardinalities of explicitly described sets, and neither is a probability.

step 2.1step 2.2∎

Remarks

The sum rule is doing real work in step 2.2, and its hypothesis is checked rather than assumed: two different suits share no card, so the four blocks are disjoint. Without that, adding the four counts would overcount, which is the failure this page's counterexample exhibits.
What is deliberately absent. Turning $5148/2598960$ into a probability needs a probability space, which the library does not have here. The temptation to write one down is exactly the place a worked example smuggles in machinery it has not got.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

The $15$ weak compositions of $4$ into $3$ parts, listed and matched against stars and bars

Example

Take $n = 4$ and $m = 3$ . The weak compositions of $4$ into $3$ parts (Compositions and weak compositions of a natural number into a fixed number of parts) are the triples $(k_0,k_1,k_2)$ of naturals with $k_0+k_1+k_2 = 4$ . Listed in decreasing lexicographic order they are

$\begin{array}{lllll} (4,0,0) & (3,1,0) & (3,0,1) & (2,2,0) & (2,1,1) \\ (2,0,2) & (1,3,0) & (1,2,1) & (1,1,2) & (1,0,3) \\ (0,4,0) & (0,3,1) & (0,2,2) & (0,1,3) & (0,0,4) \end{array}$

fifteen in all, matching $\binom{n+m-1}{m-1} = \binom{6}{2} = 15$ from For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ . Of these, three have every part nonzero, namely $(2,1,1)$ , $(1,2,1)$ and $(1,1,2)$ , matching $\binom{n-1}{m-1} = \binom{3}{2} = 3$ .

Facts & Assumptions

Given: $n = 4$ , $m = 3$ , so $M := m-1 = 2$ and $n+M = 6$ ; the sets $\mathcal{W}(4,3)$ and $\mathcal{C}(4,3)$ of Compositions and weak compositions of a natural number into a fixed number of parts; and $2! = 2$ , $4! = 24$ , $6! = 720$ , $3! = 6$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L1]

For $m \ge 1$ , $\lvert\mathcal{W}(n,m)\rvert = \binom{n+m-1}{m-1}$ , and the map $k \mapsto S(k) := \{\,(\sum_{j<\sigma(i)}k_j) + i : i < M\,\}$ is a bijection onto the set of $M$ -element subsets of $n+M$ (For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ ).

[L2]

For $m \ge 1$ and $n \ge 1$ , $\lvert\mathcal{C}(n,m)\rvert = \binom{n-1}{m-1}$ (For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ ).

[L3]

$\binom{n}{k}k!(n-k)! = n!$ for $k \le n$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ ), and cancellation by a nonzero natural (Cancellation for multiplication by a nonzero factor).

[L4]

$\binom{3}{2} = \binom{3}{1} = 3$ from the closed formula, and finite sums in $\mathbb{N}$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ).

Verification

technique · direct

1.1

The list above is exhaustive and has no repetitions: it is organised by the value of $k_0$ , which runs over $4, 3, 2, 1, 0$ , and for each $k_0$ the pair $(k_1,k_2)$ runs over all solutions of $k_1+k_2 = 4-k_0$ , of which there are $5-k_0$ , namely $(4-k_0,0), (3-k_0,1), \dots, (0,4-k_0)$ . The block sizes are therefore $1, 2, 3, 4, 5$ , and $1+2+3+4+5 = 15$ .

givenL4

2.1

The formula agrees. By [L3] with $n = 6$ , $k = 2$ : $\binom{6}{2}\cdot 2!\cdot 4! = 6!$ , that is $\binom{6}{2}\cdot 2 \cdot 24 = 720$ , so $\binom{6}{2}\cdot 48 = 720$ and $\binom{6}{2} = 15$ . By [L1] with $n = 4$ , $m = 3$ this is $\lvert\mathcal{W}(4,3)\rvert$ , matching step 1.1.

step 1.1L1L3

2.2

The bijection of [L1] made concrete. Here $M = 2$ , so $S(k) = \{k_0,\ k_0+k_1+1\}$ , a two-element subset of $6 = \{0,1,2,3,4,5\}$ . For $(4,0,0)$ : $S = \{4,\ 5\}$ . For $(2,1,1)$ : $S = \{2,\ 4\}$ . For $(1,2,1)$ : $S = \{1,\ 4\}$ . For $(0,0,4)$ : $S = \{0,\ 1\}$ . Each is indeed a $2$ -element subset of $6$ , and the four are distinct, as injectivity requires. Reading the picture backwards, the two elements of $S$ are the positions of the two bars in a row of four stars and two bars, and the parts are the lengths of the three runs of stars.

step 1.1L1

3.1

The compositions. A weak composition has all parts nonzero exactly when none of $k_0,k_1,k_2$ is $0$ , and inspection of the list leaves $(2,1,1)$ , $(1,2,1)$ and $(1,1,2)$ , three in all. By [L2] the predicted count is $\binom{4-1}{3-1} = \binom{3}{2} = 3$ , which agrees. The bijection behind [L2] subtracts $1$ from every part, sending these three to $(1,0,0)$ , $(0,1,0)$ and $(0,0,1)$ , the three weak compositions of $1$ into $3$ parts.

step 1.1step 2.1L2L4

4.1

So $\lvert\mathcal{W}(4,3)\rvert = 15 = \binom{6}{2}$ and $\lvert\mathcal{C}(4,3)\rvert = 3 = \binom{3}{2}$ , both by direct enumeration and by the formulas.

step 2.1step 2.2step 3.1∎

Remarks

A stars-and-bars example that only checks the number is the weaker example. Step 2.2 exhibits the bijection on four of the fifteen tuples, so the reader sees which subset of $6$ each composition corresponds to rather than being told that some correspondence exists.
The count $1+2+3+4+5$ in step 1.1 is itself an instance of the theorem, at $m = 2$ : the number of weak compositions of $j$ into $2$ parts is $\binom{j+1}{1} = j+1$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

All $8$ functions $3 \to 2$ , the $0$ injections $3 \to 2$ , and the $8$ subsets of a $3$ -element set

Example

Every count here is small enough to list in full, so nothing is asserted by inspection. Take $3 = \{0,1,2\}$ and $2 = \{0,1\}$ .

There are $2^{3} = 8$ functions $3 \to 2$ , and all eight are listed below as triples $(f(0),f(1),f(2))$ .
None of them is injective, and the predicted count is $2^{\underline{3}} = 2\cdot 1\cdot 0 = 0$ .
There are $2^{3} = 8$ subsets of a three-element set, and grouping them by size gives $1+3+3+1 = 8$ .

Facts & Assumptions

Given: The sets $3 = \{0,1,2\}$ and $2 = \{0,1\}$ , and $A := 3$ .

[L1]

$\lvert X^{Y}\rvert = \lvert X\rvert^{\lvert Y\rvert}$ (The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $\lvert A^{B}\rvert = \lvert A\rvert^{\lvert B\rvert}$ , Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $\mathbb{R}$ , The cardinality $\lvert A\rvert$ of a finite set).

[L2]

The number of injections of a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ , with $n^{\underline{0}} = 1$ and $n^{\underline{\sigma(k)}} = n^{\underline{k}}(n-k)$ (The number of injections from a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ , The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L3]

Pigeonhole: there is no injection $\sigma(n) \to n$ , and none $p \to q$ when $q < p$ (The pigeonhole principle on $\mathbb{N}$ , claims 1 and 2).

[L4]

$\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ ( $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$ ), $\lvert [A]^{k}\rvert = \binom{\lvert A\rvert}{k}$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ), and $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ ( $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for $n \ge 1$ , clause 1).

[L5]

Pascal's rule and the boundary values $\binom{n}{0} = \binom{n}{n} = 1$ (Pascal's rule $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ , and the hockey-stick identity $\sum_{i \le n}\binom{i}{k} = \binom{n+1}{k+1}$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

Verification

technique · direct

1.1

The eight functions $3 \to 2$ , written as the triples of their values: $(0,0,0)$ , $(0,0,1)$ , $(0,1,0)$ , $(0,1,1)$ , $(1,0,0)$ , $(1,0,1)$ , $(1,1,0)$ , $(1,1,1)$ . The list is exhaustive because a function is determined by its three values and each value is $0$ or $1$ , and it has no repetitions. There are eight, and [L1] predicts $\lvert 2\rvert^{\lvert 3\rvert} = 2^{3} = 2\cdot 2\cdot 2 = 8$ .

givenL1

2.1

None of the eight is injective: in every triple above two of the three entries are equal, so two distinct elements of $3$ receive the same value. This agrees with [L2], which predicts $2^{\underline{3}} = 2^{\underline{2}}\cdot(2-2) = 2^{\underline{2}}\cdot 0 = 0$ injections, and with [L3], which forbids an injection $3 \to 2$ outright since $2 < 3$ .

step 1.1L2L3

2.2

The eight subsets of $A = 3$ , grouped by cardinality: $\varnothing$ ; then $\{0\}$ , $\{1\}$ , $\{2\}$ ; then $\{0,1\}$ , $\{0,2\}$ , $\{1,2\}$ ; then $\{0,1,2\}$ . So $\lvert [A]^{0}\rvert = 1$ , $\lvert [A]^{1}\rvert = 3$ , $\lvert [A]^{2}\rvert = 3$ , $\lvert [A]^{3}\rvert = 1$ , that is $\binom{3}{0} = 1$ , $\binom{3}{1} = 3$ , $\binom{3}{2} = 3$ , $\binom{3}{3} = 1$ , which is row $3$ of Pascal's triangle as [L5] gives it.

step 1.1L4L5

3.1

The two ways of counting $\mathcal{P}(A)$ agree: directly, the list in step 2.2 has $1+3+3+1 = 8$ entries; by [L4], $\lvert\mathcal{P}(A)\rvert = 2^{3} = 8$ and $\sum_{k<4}\binom{3}{k} = 2^{3}$ . This is clause 1 of [L4] in its smallest interesting case.

step 2.1step 2.2L4∎

Remarks

The zero count is the interesting one. $2^{\underline{3}} = 0$ because the falling factorial acquires the factor $2-2 = 0$ at the third step, which is the arithmetic shadow of the pigeonhole principle. Both routes are checked above against the same explicit list.
The three subsets of size $2$ and the three of size $1$ are matched by the complementation bijection of $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ : $\{0\} \leftrightarrow \{1,2\}$ , $\{1\} \leftrightarrow \{0,2\}$ , $\{2\} \leftrightarrow \{0,1\}$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

Vandermonde's identity checked at $m = 4$ , $n = 3$ , $k = 3$ , both sides equal to $35$

Example

Take $m = 4$ , $n = 3$ and $k = 3$ in Vandermonde's identity $\binom{m+n}{k} = \sum_{i<k+1}\binom{m}{i}\binom{n}{k-i}$ . The left-hand side is $\binom{7}{3} = 35$ , and the right-hand side is

$\binom{4}{0}\binom{3}{3} + \binom{4}{1}\binom{3}{2} + \binom{4}{2}\binom{3}{1} + \binom{4}{3}\binom{3}{0} = 1 + 12 + 18 + 4 = 35 .$

The same identity at $k = 5$ , still with $m = 4$ and $n = 3$ , exercises the boundary convention: three of the six terms vanish because their coefficients are $0$ , and both sides come to $21$ .

Facts & Assumptions

Given: $M := 4\times\{0\}$ and $N := 3\times\{1\}$ , disjoint with $\lvert M\rvert = 4$ , $\lvert N\rvert = 3$ and $\lvert M\cup N\rvert = 7$ ; and the factorials $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , $7! = 5040$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L1]

Vandermonde: $\binom{m+n}{k} = \sum_{i<k+1}\binom{m}{i}\binom{n}{k-i}$ , proved by partitioning $[M\cup N]^{k}$ according to $\lvert S \cap M\rvert$ , the block with value $i$ being in bijection with $[M]^{i}\times[N]^{k-i}$ (Vandermonde's identity $\binom{m+n}{k} = \sum_{i<k+1}\binom{m}{i}\binom{n}{k-i}$ , The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$ , and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$ ).

[L2]

$\binom{n}{k}k!(n-k)! = n!$ for $k \le n$ ( $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$ ; hence $\binom{n}{k}\,k! = n^{\underline{k}}$ , the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$ ), cancellation by a nonzero natural (Cancellation for multiplication by a nonzero factor), and $\binom{n}{0} = \binom{n}{n} = 1$ , $\binom{n}{1} = n$ , $\binom{n}{k} = 0$ for $k>n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

[L3]

Finite sums in $\mathbb{N}$ (Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ).

Verification

technique · direct

1.1

The coefficients needed, all from [L2]. $\binom{7}{3}\cdot 3!\cdot 4! = 7!$ gives $\binom{7}{3}\cdot 6\cdot 24 = 5040$ , so $\binom{7}{3}\cdot 144 = 5040$ and $\binom{7}{3} = 35$ . Similarly $\binom{4}{2}\cdot 2!\cdot 2! = 4!$ gives $\binom{4}{2} = 6$ ; and $\binom{4}{0} = \binom{3}{3} = \binom{3}{0} = 1$ , $\binom{4}{1} = 4$ , $\binom{4}{3} = \binom{4}{1} = 4$ by symmetry, $\binom{3}{1} = \binom{3}{2} = 3$ . Also $\binom{7}{5}\cdot 5!\cdot 2! = 7!$ gives $\binom{7}{5}\cdot 240 = 5040$ , so $\binom{7}{5} = 21$ .

givenL2

2.1

The case $k = 3$ . The four terms of the sum, indexed by $i < 4$ , are $\binom{4}{0}\binom{3}{3} = 1\cdot 1 = 1$ , $\binom{4}{1}\binom{3}{2} = 4\cdot 3 = 12$ , $\binom{4}{2}\binom{3}{1} = 6\cdot 3 = 18$ and $\binom{4}{3}\binom{3}{0} = 4\cdot 1 = 4$ ; their sum is $1+12+18+4 = 35$ , equal to $\binom{7}{3}$ .

step 1.1L1L3

2.2

The case $k = 5$ , where the boundary convention does the work. The sum runs over $i < 6$ and its terms are $\binom{4}{0}\binom{3}{5} = 0$ , $\binom{4}{1}\binom{3}{4} = 0$ , $\binom{4}{2}\binom{3}{3} = 6$ , $\binom{4}{3}\binom{3}{2} = 12$ , $\binom{4}{4}\binom{3}{1} = 3$ and $\binom{4}{5}\binom{3}{0} = 0$ , the vanishing ones being those with $5-i > 3$ or $i > 4$ . The total is $6+12+3 = 21 = \binom{7}{5}$ .

step 1.1L1L2L3

3.1

The partition behind one block. The term with $i = 2$ in step 2.1 counts the sets $S \in [M\cup N]^{3}$ with exactly two elements in $M$ ; the bijection of [L1] sends such an $S$ to the pair $(S\cap M, S\cap N)$ . For instance $S = \{(0,0),(1,0),(0,1)\}$ goes to $\big(\{(0,0),(1,0)\},\ \{(0,1)\}\big) \in [M]^{2}\times[N]^{1}$ , and there are $\binom{4}{2}\binom{3}{1} = 18$ such $S$ , which is the value computed there. So the identity is a count, not an algebraic accident.

step 1.1step 2.1L1

4.1

Both instances confirm [L1]: at $k = 3$ both sides are $35$ , at $k = 5$ both sides are $21$ , and in the second the terms whose blocks are empty contribute $0$ exactly as the identity's lack of a range restriction requires.

step 2.1step 2.2step 3.1∎

Remarks

Why a case with vanishing terms is included. The identity is stated for all $m$ , $n$ , $k$ with no side condition, and that is only correct because out-of-range binomial coefficients are $0$ rather than undefined. Checking a case where three terms vanish is checking exactly that clause.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

Two sets of the same finite cardinality between which the bijection is not unique

Statement refuted

Refuted claim: two equinumerous finite sets admit exactly one bijection between them.

The witness is $A := 2 = \{\varnothing,\{\varnothing\}\} = \{0,1\}$ and $B := [2]^{1} = \{\{0\},\{1\}\}$ , the set of one-element subsets of $2$ . Both have cardinality $2$ , and there are exactly two bijections between them.

Facts & Assumptions

Given: $A = 2 = \{0,1\}$ with $0 = \varnothing$ and $1 = \{0\}$ (The natural numbers $\mathbb{N}$ (von Neumann)), and $B = [2]^{1}$ , the set of $1$ -element subsets of $2$ .

[L1]

$\lvert n\rvert = n$ for a natural $n$ , and $\lvert A\rvert$ is the unique natural equinumerous with $A$ (The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$\lvert [X]^{k}\rvert = \binom{\lvert X\rvert}{k}$ and $\binom{n}{1} = n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

[L3]

The set of bijections between two finite sets of common cardinality $n$ has exactly $n!$ elements (A finite set $A$ with $\lvert A\rvert = n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality), and $2! = 2$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L4]

A bijection is an injective surjection (Injection, surjection, bijection, Equinumerous sets, $A \approx B$ and $A \preceq B$ ).

[L5]

Claim 3 of The pigeonhole principle on $\mathbb{N}$ : a finite set is equinumerous with exactly one natural number.

Counterexample

technique · direct

1.1

The two sets and their cardinalities. $A = 2$ has $\lvert A\rvert = 2$ by [L1]. The elements of $B = [2]^{1}$ are the one-element subsets of $\{0,1\}$ , namely $\{0\}$ and $\{1\}$ , so $\lvert B\rvert = \binom{2}{1} = 2$ by [L2]. Hence $\lvert A\rvert = \lvert B\rvert$ .

givenL1L2

2.1

Two distinct bijections. Let $f : A \to B$ be $f(0) = \{0\}$ , $f(1) = \{1\}$ , and let $g : A \to B$ be $g(0) = \{1\}$ , $g(1) = \{0\}$ . Each is injective, its two values being distinct, and each is surjective, its image being all of $B$ ; so both are bijections by [L4]. They are distinct, since $f(0) = \{0\} \ne \{1\} = g(0)$ .

step 1.1L4construct

3.1

There are exactly two. By [L3] the set of bijections $A \to B$ has $2! = 2$ elements, so $f$ and $g$ of step 2.1 are all of them.

step 1.1L3

4.1

The refuted claim fails: $\lvert A\rvert = \lvert B\rvert$ holds, and there are two bijections $A \to B$ , not one. The cardinality $\lvert A\rvert$ of a finite set asserts only that some bijection $A \to \lvert A\rvert$ exists; [L5] makes the resulting natural number unique, not the witnessing map.

step 2.1step 3.1L1L5∎

Remarks

What is unique and what is not. Cardinality is a well-defined function of the set, but a bijection witnessing an equality of cardinalities need not be unique. Whenever a construction is made "along a bijection", one has to check, as The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form does, that the result does not depend on which bijection was used.
The count grows fast. For $\lvert A\rvert = n$ there are $n!$ bijections onto any set of the same cardinality (A finite set $A$ with $\lvert A\rvert = n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality), so the bijection is unique only for $n \le 1$ .

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

A count that overcounts because the blocks are not disjoint, and exactly where the sum rule's hypothesis is spent

Statement refuted

Refuted claim: clause 2 of The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition with its disjointness hypothesis deleted, that is, for a finite index set $I$ and any family $(A_i)_{i \in I}$ of finite sets,

$\Big\lvert\bigcup_{i \in I} A_i\Big\rvert = \sum_{i \in I}\lvert A_i\rvert .$

The witness lives inside $\mathcal{P}(X)$ for $X := 4 = \{0,1,2,3\}$ . Take $I := 2$ , let $A_0$ be the set of subsets of $X$ containing $0$ and $A_1$ the set of subsets containing $1$ . Then $\lvert A_0\rvert = \lvert A_1\rvert = 8$ , so the right-hand side is $16$ , while $\lvert A_0 \cup A_1\rvert = 12$ .

Facts & Assumptions

Given: $X = 4 = \{0,1,2,3\}$ ; $A_0 := \{\, S \subseteq X : 0 \in S \,\}$ ; $A_1 := \{\, S \subseteq X : 1 \in S \,\}$ ; and $C := \{\, S \subseteq X : 0 \notin S \text{ and } 1 \notin S \,\}$ .

[L1]

$\lvert\mathcal{P}(Y)\rvert = 2^{\lvert Y\rvert}$ ( $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$ , Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $\mathbb{R}$ ), and $2^{2} = 4$ , $2^{3} = 8$ , $2^{4} = 16$ .

[L2]

The sum rule for two disjoint blocks: $\lvert S \cup T\rvert = \lvert S\rvert + \lvert T\rvert$ , and its proof, whose only use of disjointness is the injectivity of the splice map $h$ (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, step 1.1 there).

[L3]

Cardinality (The cardinality $\lvert A\rvert$ of a finite set): transport along a bijection; a subset of a finite set is finite (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ ).

[L4]

Maps (Injection, surjection, bijection): a map with a two-sided inverse is a bijection.

[L5]

Cancellation in $\mathbb{N}$ (Addition is cancellative), and sums over a finite index set (The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form).

Counterexample

technique · direct

1.1

The three sets are subsets of the finite set $\mathcal{P}(X)$ , hence finite by [L3], and $\lvert\mathcal{P}(X)\rvert = 2^{4} = 16$ by [L1].

givenL1L3

2.1

Each block has eight elements. The map $S \mapsto S \setminus \{0\}$ sends $A_0$ into $\mathcal{P}(\{1,2,3\})$ and $T \mapsto T \cup \{0\}$ sends $\mathcal{P}(\{1,2,3\})$ into $A_0$ ; the two composites are the identity, because $0 \in S$ for $S \in A_0$ and $0 \notin T$ for $T \subseteq \{1,2,3\}$ . So $\lvert A_0\rvert = 2^{3} = 8$ by [L1], [L3] and [L4], and the same argument at the point $1$ gives $\lvert A_1\rvert = 8$ . Hence $\sum_{i \in 2}\lvert A_i\rvert = 8 + 8 = 16$ .

step 1.1L1L3L4L5

2.2

The union has twelve. A subset of $X$ lies in $A_0 \cup A_1$ exactly when it contains $0$ or contains $1$ , so $\mathcal{P}(X)$ is the disjoint union of $A_0\cup A_1$ and $C$ ; and $C$ is in bijection with $\mathcal{P}(\{2,3\})$ under the identity map, since a subset of $X$ containing neither $0$ nor $1$ is precisely a subset of $\{2,3\}$ , giving $\lvert C\rvert = 2^{2} = 4$ . By [L2], $16 = \lvert A_0\cup A_1\rvert + 4$ , so $\lvert A_0 \cup A_1\rvert = 12$ by [L5].

step 1.1L1L2L3L4L5

3.1

The claim fails: $12 \ne 16$ . The overcount is exactly $4$ , the number of subsets containing both $0$ and $1$ , and it agrees with $\lvert C\rvert$ because $S \mapsto S \cup \{0,1\}$ is a bijection of $C$ onto $A_0 \cap A_1$ , with inverse $T \mapsto T \setminus \{0,1\}$ .

step 2.1step 2.2L4∎

Remarks

Where the proof of The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition breaks. Its step 1.1 splices bijections $f : p \to A$ and $g : q \to B$ into $h : p+q \to A \cup B$ , and the only place disjointness enters is the third case of injectivity: an index below $p$ must give a value different from an index at least $p$ , and that is guaranteed only because $f$ lands in $A$ , $g$ lands in $B$ and $A \cap B = \varnothing$ . Here the four subsets containing both $0$ and $1$ are each hit twice, so $h$ is surjective but not injective, and one gets $\lvert A_0\cup A_1\rvert \le 16$ rather than equality.
The systematic repair is inclusion and exclusion, which subtracts the count of the overlap. It is the next page of this track and is not available here, so the correction is not stated as a formula: what this item establishes is that some correction is needed.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

FALSE: every injection of a set into itself is a bijection

Statement

FALSE. The statement

every injective function $f : A \to A$ from a set to itself is a bijection

for all sets $A$ .

The claim is plausible because it is true for finite $A$ : that is clause 4 of A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ . What is easy to miss is that the proof of that clause uses finiteness twice, at the transport $\lvert f[A]\rvert = \lvert A\rvert$ and at the step "a subset of the same cardinality as the whole is the whole", and neither survives without it.

Facts & Assumptions

Given: The von Neumann naturals $\mathbb{N}$ with $0 = \varnothing$ and successor $\sigma$ (The natural numbers $\mathbb{N}$ (von Neumann)), and $A := \mathbb{N}$ , $f := \sigma$ .

[L1]

$(\mathbb{N},0,\sigma)$ satisfies the Peano axioms: $\sigma(n) \ne 0$ for every $n$ , and $\sigma$ is injective (The von Neumann naturals form a Peano system).

[L2]

Every nonzero natural is a successor (Every nonzero natural number is a successor), so the image of $\sigma$ is exactly $\mathbb{N}\setminus\{0\}$ .

[L3]

Injection, surjection, bijection (Injection, surjection, bijection): $f$ is surjective when its image is the whole codomain, and bijective when injective and surjective.

[L4]

For finite $A$ , every injection $A \to A$ is a bijection (A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ , clause 4), the proof going through $\lvert f[A]\rvert = \lvert A\rvert$ and clause 3 of the same theorem (The cardinality $\lvert A\rvert$ of a finite set).

[L5]

$\mathbb{N}$ is not finite: $\mathbb{N} \not\approx n$ for every natural $n$ (The pigeonhole principle on $\mathbb{N}$ , claim 4, Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A \preceq B$ ).

Refutation

technique · direct

1.1

The witness is the successor map $\sigma : \mathbb{N} \to \mathbb{N}$ . It is injective by [L1].

givenL1L3

2.1

It is not surjective: $0$ is not in its image, since $\sigma(n) \ne 0$ for every $n$ by [L1]. Equivalently, its image is $\mathbb{N}\setminus\{0\}$ by [L2], a proper subset of $\mathbb{N}$ .

step 1.1L1L2L3

3.1

So $\sigma$ is an injection of $\mathbb{N}$ into itself that is not a bijection, and the displayed statement is false.

step 1.1step 2.1L3

4.1

Finiteness is exactly the missing hypothesis. By [L4] the statement is true whenever $A$ is finite, and $\mathbb{N}$ is not finite by [L5]. In the proof of [L4] the hypothesis is spent at the transport of cardinality along the bijection $A \to f[A]$ , which presupposes $A$ finite, and then at the conclusion $f[A] = A$ from $\lvert f[A]\rvert = \lvert A\rvert$ , which is the clause of A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ that fails here: $\sigma[\mathbb{N}]$ is a proper subset of $\mathbb{N}$ equinumerous with it.

step 3.1L4L5∎

Remarks

A set for which the statement fails is called Dedekind-infinite, and the refutation above exhibits $\mathbb{N}$ as one. Claim 5 of The pigeonhole principle on $\mathbb{N}$ says that no natural number is Dedekind-infinite, which is the finite half of the same picture.
The relation between the two notions of infinity — "not finite" and "Dedekind-infinite" — is a genuine question of set theory without choice, and it is treated on the countability page rather than here.
The surjective half fails too. The map $\mathbb{N} \to \mathbb{N}$ sending $0$ and $1$ to $0$ and $n \ge 2$ to $n-1$ is surjective and not injective, so neither half of clause 4 of A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$ , and equality holds if and only if $B = A$ survives the loss of finiteness.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

FALSE: $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ for all finite $A$ and $B$

Statement

FALSE. The statement

$\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$

for all finite sets $A$ and $B$ .

This is The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition clause 1 with the hypothesis $A \cap B = \varnothing$ deleted. It is the single most common way a count goes wrong, and the smallest witness is as small as a witness can be.

Facts & Assumptions

Given: The sets $\{0\}$ , $\{0,1\}$ and $\{1,2\}$ , with $0$ , $1$ , $2$ the von Neumann naturals (The natural numbers $\mathbb{N}$ (von Neumann)).

[L1]

$\lvert n\rvert = n$ for a natural $n$ , and a bijection transports cardinality (The cardinality $\lvert A\rvert$ of a finite set, Injection, surjection, bijection).

[L2]

$\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ when $A \cap B = \varnothing$ (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , and a sum over a finite index set splits along a partition, clause 1).

[L3]

Distinct naturals are distinct, so $1 \ne 2$ and $3 \ne 4$ (Trichotomy of the order on $\mathbb{N}$ ).

Refutation

technique · direct

1.1

The smallest witness. Take $A = B = \{0\}$ . Then $A \cup B = \{0\}$ , which is $1$ as a von Neumann natural, so $\lvert A \cup B\rvert = 1$ by [L1]; while $\lvert A\rvert + \lvert B\rvert = 1 + 1 = 2$ . Since $1 \ne 2$ by [L3], the displayed statement fails.

givenL1L3

2.1

A witness with partial overlap, to show that the failure is not an artefact of taking $A$ and $B$ equal. Take $A = \{0,1\} = 2$ and $B = \{1,2\}$ . Then $\lvert A\rvert = 2$ by [L1], and $\lvert B\rvert = 2$ because $0 \mapsto 1$ , $1 \mapsto 2$ is a bijection of $2$ onto $B$ . But $A \cup B = \{0,1,2\} = 3$ , so $\lvert A\cup B\rvert = 3$ , whereas $\lvert A\rvert + \lvert B\rvert = 4$ . Again the two differ.

step 1.1L1L3

3.1

The missing hypothesis is disjointness. [L2] proves the identity whenever $A \cap B = \varnothing$ , and in step 1.1 the intersection is $\{0\}$ while in step 2.1 it is $\{1\}$ ; in each case the excess of the right-hand side over the left is the cardinality of that intersection.

step 1.1step 2.1L2∎

Remarks

What the general correction is. Adding the counts and then subtracting the count of the overlap is the two-set case of inclusion and exclusion. That principle is the next page of this track and is not available here, so no formula for the general case is stated: what is established above is only that the identity as displayed is false, and where its hypothesis went.
The same failure at the level of a family is exhibited concretely in A count that overcounts because the blocks are not disjoint, and exactly where the sum rule's hypothesis is spent, where twelve subsets are counted as sixteen.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

FALSE: for all sets $A$ and $B$ with $B$ having at least two elements, $A \times B$ is strictly larger than $A$

Statement

FALSE. The statement

for all sets $A$ and $B$ with $B$ having at least two elements, $A \prec A \times B$

that is, $A$ injects into $A \times B$ and is not equinumerous with it (Equinumerous sets, $A \approx B$ and $A \preceq B$ ).

The claim generalises the finite product rule in the shape a reader expects: if $\lvert A\rvert$ is multiplied by at least $2$ , surely the product is bigger. It fails at both ends of the range, trivially when $A$ is empty and substantially when $A$ is infinite.

Facts & Assumptions

Given: The sets $\mathbb{N}$ and $\varnothing$ , and $2 = \{0,1\}$ (The natural numbers $\mathbb{N}$ (von Neumann)).

[L1]

$\mathbb{N}\times\mathbb{N} \approx \mathbb{N}$ : the map $J(m,n) = 2^{m}(2n+1)$ is a bijection of $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}\setminus\{0\}$ , and composing with the inverse of the successor gives a bijection onto $\mathbb{N}$ ( $\mathbb{N} \times \mathbb{N} \approx \mathbb{N}$ , Finite, countably infinite, countable, uncountable).

[L2]

$X \prec Y$ means $X \preceq Y$ and $X \not\approx Y$ (Equinumerous sets, $A \approx B$ and $A \preceq B$ ).

[L3]

$\lvert A \times B\rvert = \lvert A\rvert\lvert B\rvert$ for finite $A$ , $B$ (The product rule: $\lvert A \times B\rvert = \lvert A\rvert\,\lvert B\rvert$ , and $\big\lvert\prod_{i<m} A_i\big\rvert = \prod_{i<m}\lvert A_i\rvert$ ), and $\lvert X\rvert = 0$ exactly when $X = \varnothing$ (The cardinality $\lvert A\rvert$ of a finite set).

[L4]

Order arithmetic of $\mathbb{N}$ : $p \le q$ implies $pk \le qk$ ; $x \le y$ implies $x + c \le y + c$ ; $a \ne 0$ is the same as $1 \le a$ ; $2 \cdot a = \sigma(1)\cdot a = 1\cdot a + a = a + a$ by the successor-left law; $1 \cdot a = a$ ; and multiplication is commutative (Order is compatible with multiplication, Order is compatible with addition, Discreteness: $\sigma(n)$ is the immediate successor, Zero and one under multiplication, Distributivity and the successor law for multiplication, Multiplication is commutative, Order on the natural numbers).

[L5]

$0 \ne 1$ in $\mathbb{N}$ , so $\mathbb{N}$ has at least two elements (The von Neumann naturals form a Peano system).

Refutation

technique · direct

1.1

The substantial witness: $A = B = \mathbb{N}$ . The set $\mathbb{N}$ has at least two elements by [L5], so the hypothesis on $B$ holds. By [L1] there is a bijection $\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ , so $A \approx A \times B$ , and therefore $A \prec A\times B$ is false by [L2].

givenL1L2L5

1.2

A degenerate witness, which shows the claim fails even for finite $A$ : take $A = \varnothing$ and $B = 2$ . Then $A \times B = \varnothing$ , since a pair in it would have a first coordinate in $\varnothing$ ; so $A \approx A \times B$ and again $A \prec A\times B$ fails.

givenL2L3

2.1

The corrected finite statement is true. Let $A$ be finite and nonempty and let $B$ be finite with $\lvert B\rvert \ge 2$ ; write $a := \lvert A\rvert \ge 1$ and $b := \lvert B\rvert$ . Then $\lvert A\times B\rvert = ab \ge 2a = a + a \ge a + 1 > a$ by [L3] and [L4], using $1 \le a$ . So a finite nonempty $A$ is strictly smaller than $A \times B$ in cardinality. Both hypotheses are needed, by step 1.1 and step 1.2 respectively.

step 1.1step 1.2L3L4

3.1

So the displayed statement is false, and what fails is not the product rule but its extension beyond the finite nonempty case: finiteness and nonemptiness of $A$ are exactly the hypotheses under which multiplying by a factor of at least $2$ increases the count.

step 1.1step 1.2step 2.1L2L3∎

Remarks

The contrast with Cantor's theorem is the point. $X \prec \mathcal{P}(X)$ holds for every set whatsoever (Cantor's theorem: $A \prec \mathcal{P}(A)$ ), finite or infinite; strict increase survives to the infinite case there and not here. Passing to the power set is a genuinely different operation from multiplying by a fixed set.
Read the cited theorem before using it. $\mathbb{N} \times \mathbb{N} \approx \mathbb{N}$ states that $J(m,n) = 2^{m}(2n+1)$ is a bijection onto the nonzero naturals, and the bijection onto $\mathbb{N}$ is obtained by composing with the inverse of the successor. The statement used above is the one that item actually proves.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29Open item page →

FALSE: $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for every $n \in \mathbb{N}$

Statement

FALSE. The statement

$\displaystyle\sum_{k<n+1}(-1)^{k}\,\iota\binom{n}{k} = 0$

for every $n \in \mathbb{N}$ .

The claim is what a text whose natural numbers begin at $1$ would state truly. In this library $\mathbb{N}$ contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann)), and the statement acquires a counterexample at its very first index.

Facts & Assumptions

Given: The canonical natural $\iota$ (The canonical natural $\iota(n) = n \cdot 1_F$ of a field) and the real finite sum of Finite sums and finite products, by recursion; $\mathbb{N}$ contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann)).

[L1]

$\sum_{k<0}u_k = 0$ and $\sum_{k<\sigma(N)}u_k = \sum_{k<N}u_k + u_N$ (Finite sums and finite products, by recursion, Laws of finite sums and finite products).

[L2]

$\binom{0}{0} = 1$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ), and $\iota(1) = 1$ (The canonical natural $\iota(n) = n \cdot 1_F$ of a field).

[L3]

$a^{0} = 1$ for every real $a$ , including $a = 0$ ; and $0^{\,m} = 0$ for $m \ge 1$ (Integer powers $a^m$ , Multiplication by zero: $0 \cdot a = 0$ , Field).

[L4]

The true statement: $\sum_{k<n+1}(-1)^{k}\iota\binom{n}{k} = 0$ for $n \ge 1$ ( $\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for $n \ge 1$ , clause 2), proved from the binomial theorem at $x = -1$ , $y = 1$ (The binomial theorem in $\mathbb{R}$ : $(x+y)^{n} = \sum_{k<n+1} \iota\!\binom{n}{k}\, x^{k} y^{\,n-k}$ ).

Refutation

technique · direct

1.1

Evaluate the left-hand side at $n = 0$ . The sum runs over $k < 0+1 = 1$ , so by [L1] it is the single term $(-1)^{0}\,\iota\binom{0}{0}$ .

givenL1

2.1

That term is $1$ : $(-1)^{0} = 1$ by [L3], $\binom{0}{0} = 1$ by [L2], and $\iota(1) = 1$ . So the sum equals $1$ , not $0$ , and the displayed statement is false at $n = 0$ .

step 1.1L2L3

3.1

Where the hypothesis is spent in the true version. [L4] obtains the identity by evaluating the binomial theorem at $x = -1$ , $y = 1$ : the left-hand side becomes $(-1+1)^{n} = 0^{\,n}$ , which is $0$ only for $n \ge 1$ , while $0^{0} = 1$ by [L3]. That single evaluation is the entire difference between the true statement and the false one.

step 2.1L3L4∎

Remarks

The convention $0^{0} = 1$ is not the culprit. It is what makes the binomial theorem itself true at $n = 0$ and at $x = 0$ , with no exceptional case; the price is that one of its corollaries carries a hypothesis. Changing the convention would move the exception, not remove it.
The concrete picture. In Pascal's triangle computed to row $6$ , with Pascal's rule checked at every interior entry the alternating sums of rows $1$ to $6$ are all $0$ and the alternating sum of row $0$ is $1$ . A reader who computes from row $1$ onwards sees only the true pattern.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

FALSE: the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ for every $m \in \mathbb{N}$

Statement

FALSE. The statement

$\big\lvert\mathcal{W}(n,m)\big\rvert = \dbinom{n+m-1}{\,m-1\,}$

for every $n \in \mathbb{N}$ and every $m \in \mathbb{N}$ , that is, For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ with its hypothesis $m \ge 1$ deleted.

This is a false statement of an unusual kind: at $m = 0$ the expression on the right is not even well formed under the reading a reader would intend, and under the only reading available in this library it is well formed and gives the wrong number.

Facts & Assumptions

Given: The sets $\mathcal{W}(n,m)$ of Compositions and weak compositions of a natural number into a fixed number of parts; binomial coefficients defined for natural arguments only (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ); and the truncated difference of Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ , under which $n - m$ is $0$ whenever $n < m$ .

[L1]

$\lvert\mathcal{W}(0,0)\rvert = 1$ and $\lvert\mathcal{W}(n,0)\rvert = 0$ for $n \ge 1$ (Compositions and weak compositions of a natural number into a fixed number of parts, The cardinality $\lvert A\rvert$ of a finite set).

[L2]

$\binom{N}{0} = 1$ and $\binom{N}{N} = 1$ for every natural $N$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

[L4]

$\binom{n}{k}$ is defined only for $n, k \in \mathbb{N}$ , and $-1$ is not a natural number (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ , The natural numbers $\mathbb{N}$ (von Neumann), Order on the natural numbers).

[L5]

$0 \ne 1$ (Trichotomy of the order on $\mathbb{N}$ , The natural numbers $\mathbb{N}$ (von Neumann)).

Refutation

technique · direct

1.1

Fix $m = 0$ and $n = 1$ . The true count is $\lvert\mathcal{W}(1,0)\rvert = 0$ by [L1]: a weak composition of $1$ into $0$ parts would be a function $0 \to \mathbb{N}$ , and the only such function is the empty function, whose sum is the empty sum $0 \ne 1$ .

givenL1L5

2.1

The formula gives $1$ . With the truncated difference, $n+m-1 = 1+0-1 = 0$ and $m-1 = 0-1 = 0$ , so the right-hand side reads $\binom{0}{0} = 1$ by [L2]. Since $1 \ne 0$ by [L5], the displayed statement is false at $(n,m) = (1,0)$ .

step 1.1L2L5

3.1

Under the other reading the expression is not defined at all. If $m-1$ is meant as an integer, it is $-1$ at $m = 0$ , and $-1$ is not a natural number, so $\binom{n-1}{-1}$ names nothing: The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ defines $\binom{N}{k}$ for natural $N$ and $k$ only. So the statement is either false or ill formed, and in neither reading is it true.

step 2.1L4∎

Remarks

The formula is correct for every $m \ge 1$ , which is what For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ asserts: $\lvert\mathcal{W}(n,m)\rvert = \binom{n+m-1}{m-1}$ under that hypothesis. The two edges are worth seeing. At $m = 1$ it reads $\binom{n}{0} = 1$ , matching the unique weak composition $(n)$ . At $n = 0$ it reads $\binom{m-1}{m-1} = 1$ , matching the unique weak composition all of whose parts are $0$ . Neither of these is the failing case; the failure is confined to $m = 0$ .
A false statement whose falsity is ill-formedness is worth stating in exactly those terms. What For $m \ge 1$ the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ , and the number of compositions is $\binom{n-1}{m-1}$ for $n \ge 1$ asserts is a statement about $m \ge 1$ ; the object $\binom{n+m-1}{m-1}$ simply does not exist at $m = 0$ unless one adopts a truncation convention, and adopting one makes the value wrong rather than absent.
The companion true values are recorded in Compositions and weak compositions of a natural number into a fixed number of parts: at $m = 0$ there is exactly one weak composition of $0$ and none of any $n \ge 1$ .

Finite Counting, Factorials and Binomial Coefficients: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Pascal's triangle computed to row 666, with Pascal's rule checked at every interior entry

Example

Facts & Assumptions

Verification

Remarks

Choosing a committee: (103)=120\binom{10}{3} = 120(310​)=120, and the ordered count 103‾=72010^{\underline{3}} = 720103​=720

Example

Facts & Assumptions

Verification

Remarks

Arrangements of a word with repeated letters, counted by the multinomial coefficient

Example

Facts & Assumptions

Verification

Remarks

Five-card hands from a 525252-card deck: (525)=2598960\binom{52}{5} = 2598960(552​)=2598960, and the count of hands with all cards of one suit

Example

Facts & Assumptions

Verification

Remarks

The 151515 weak compositions of 444 into 333 parts, listed and matched against stars and bars

Example

Facts & Assumptions

Verification

Remarks

All 888 functions 3→23 \to 23→2, the 000 injections 3→23 \to 23→2, and the 888 subsets of a 333-element set

Example

Facts & Assumptions

Verification

Remarks

Vandermonde's identity checked at m=4m = 4m=4, n=3n = 3n=3, k=3k = 3k=3, both sides equal to 353535

Example

Facts & Assumptions

Verification

Remarks

Two sets of the same finite cardinality between which the bijection is not unique

Statement refuted

Facts & Assumptions

Counterexample

Remarks

A count that overcounts because the blocks are not disjoint, and exactly where the sum rule's hypothesis is spent

Statement refuted

Facts & Assumptions

Counterexample

Remarks

FALSE: every injection of a set into itself is a bijection

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: ∣A∪B∣=∣A∣+∣B∣\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert∣A∪B∣=∣A∣+∣B∣ for all finite AAA and BBB

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: for all sets AAA and BBB with BBB having at least two elements, A×BA \times BA×B is strictly larger than AAA

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: ∑k<n+1(−1)kι ⁣(nk)=0\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0∑k<n+1​(−1)kι(kn​)=0 for every n∈Nn \in \mathbb{N}n∈N

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: the number of weak compositions of nnn into mmm parts is (n+m−1m−1)\binom{n+m-1}{m-1}(m−1n+m−1​) for every m∈Nm \in \mathbb{N}m∈N

Statement

Facts & Assumptions

Refutation

Remarks

Sources

Standard references

Pascal's triangle computed to row $6$ , with Pascal's rule checked at every interior entry

Choosing a committee: $\binom{10}{3} = 120$ , and the ordered count $10^{\underline{3}} = 720$

Five-card hands from a $52$ -card deck: $\binom{52}{5} = 2598960$ , and the count of hands with all cards of one suit

The $15$ weak compositions of $4$ into $3$ parts, listed and matched against stars and bars

All $8$ functions $3 \to 2$ , the $0$ injections $3 \to 2$ , and the $8$ subsets of a $3$ -element set

Vandermonde's identity checked at $m = 4$ , $n = 3$ , $k = 3$ , both sides equal to $35$

FALSE: $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ for all finite $A$ and $B$

FALSE: for all sets $A$ and $B$ with $B$ having at least two elements, $A \times B$ is strictly larger than $A$

FALSE: $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for every $n \in \mathbb{N}$

FALSE: the number of weak compositions of $n$ into $m$ parts is $\binom{n+m-1}{m-1}$ for every $m \in \mathbb{N}$