TheoremStatement: Literature-sourcedProof: Literature-sourcedSession-authored (Fable 5 assisted)audited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The twelvefold way

Statement

Fix positive integers $n$ and $k$ . Then the twelve standard ball-box counts are:

labelled balls to labelled boxes, arbitrary: $k^{n}$ ;
labelled balls to labelled boxes, injective: $k^{\underline{n}}$ ;
labelled balls to labelled boxes, surjective: $k! S (n, k)$ ;
unlabelled balls to labelled boxes, arbitrary: $(\binom{n + k - 1}{k - 1})$ ;
unlabelled balls to labelled boxes, injective: $(\binom{k}{n})$ ;
unlabelled balls to labelled boxes, surjective: $(\binom{n - 1}{k - 1})$ ;
labelled balls to unlabelled boxes, arbitrary: $\sum_{j = 1}^{\min (n, k)} S (n, j)$ ;
labelled balls to unlabelled boxes, injective: $1$ if $n \leq k$ , otherwise $0$ ;
labelled balls to unlabelled boxes, surjective: $S (n, k)$ ;
unlabelled balls to unlabelled boxes, arbitrary: the number of partitions of $n$ with at most $k$ parts;
unlabelled balls to unlabelled boxes, injective: $1$ if $n \leq k$ , otherwise $0$ ;
unlabelled balls to unlabelled boxes, surjective: $p_{k} (n)$ .

Facts & Assumptions

Given: positive integers $n$ and $k$ , interpreted by the conventions of Conventions for integer partitions, Ferrers diagrams, and the twelvefold-way table.

[L1]

The set of functions from an $n$ -element set to a $k$ -element set has cardinality $k^{n}$ (The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ ).

[L2]

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

[L3]

The Stirling number $S (n, j)$ counts partitions of an $n$ -element set into exactly $j$ nonempty blocks (The Stirling numbers of the second kind and the Bell numbers).

[L4]

Weak compositions of $n$ into $k$ parts are counted by $(\binom{n + k - 1}{k - 1})$ , and compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$ (For $m \geq 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 \geq 1$ , Compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$ ).

[L5]

The three unlabelled-to-unlabelled cells are the counts proved in The unlabelled-to-unlabelled cells of the twelvefold way.

Proof

technique · classification

1.1

For labelled balls and labelled boxes, clause 1 is [L1] and clause 2 is [L2]. For clause 3, a surjection $f : [n] \to [k]$ has $k$ nonempty fibres, which form a partition of $[n]$ into exactly $k$ blocks; conversely, labelling the $k$ blocks of any such partition by the elements of $[k]$ recovers a surjection. By [L3], there are therefore $k! S (n, k)$ surjections.

L1L2L3

1.2

For unlabelled balls and labelled boxes, the data are occupancy vectors $(a_{1}, \dots, a_{k})$ . Arbitrary placements are weak compositions, so clause 4 is [L4]. Surjective placements are positive compositions, so clause 6 is [L4]. Injective placements are exactly the $0$ - $1$ occupancy vectors with total $n$ , so one chooses which $n$ of the $k$ labelled boxes are occupied; this gives clause 5, namely $(\binom{k}{n})$ .

L4construct

1.3

For labelled balls and unlabelled boxes, one remembers only the fibres and forgets their labels. Thus a surjective placement is exactly a partition of $[n]$ into $k$ nonempty blocks, giving clause 9 as $S (n, k)$ by [L3]. An arbitrary placement uses some number $j$ of nonempty boxes with $1 \leq j \leq \min (n, k)$ , so clause 7 is the sum of the counts $S (n, j)$ over those $j$ . For injective placements every fibre is a singleton, hence there is one orbit when $n \leq k$ and none when $n > k$ , proving clause 8.

2.1

Clauses 10, 11, and 12 are exactly the three conclusions of [L5].

L5∎

Depends on

Used by

Dependency tree · two levels

42 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Alexander Hulpke, Combinatorics notes (standard reference, not scraped)
Darij Grinberg, Enumerative Combinatorics: class notes (standard reference, not scraped)