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

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 $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 \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$ . 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 $W (4, 3)$ and $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 $N$ ).

[L1]

For $m \geq 1$ , $∣ W (n, m) ∣ = (\binom{n + m - 1}{m - 1})$ , and the map $k \mapsto S (k) : = {(\sum_{j < σ (i)} k_{j}) + i : i < M}$ is a bijection onto the set of $M$ -element subsets of $n + M$ (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$ ).

[L2]

For $m \geq 1$ and $n \geq 1$ , $∣ C (n, m) ∣ = (\binom{n - 1}{m - 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$ ).

[L3]

$(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq 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 $N$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $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 $∣ W (4, 3) ∣$ , 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 $∣ W (4, 3) ∣ = 15 = (\binom{6}{2})$ and $∣ C (4, 3) ∣ = 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$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

45 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

Stars and bars (combinatorics) (Wikipedia) (standard reference, not scraped)
Composition (combinatorics) (Wikipedia) (standard reference, not scraped)
Binomial coefficient (Wikipedia) (standard reference, not scraped)

The 1515 weak compositions of 44 into 33 parts, listed and matched against stars and bars