TheoremStatement: AI-adaptedProof: 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.

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$

Statement

Let $m \geq 1$ and write $m = σ (M)$ , so $M = m - 1$ . Then for every $n \in N$

$∣ W (n, m) ∣ = (\binom{n + m - 1}{m - 1}) = (\binom{n + M}{M}),$

and the map $k \mapsto {(\sum_{j < σ (i)} k_{j}) + i : i < M}$ is a bijection of $W (n, m)$ onto the set of $M$ -element subsets of $n + M$ .

Moreover, for $m \geq 1$ and $n \geq 1$ ,

$∣ C (n, m) ∣ = (\binom{n - 1}{m - 1}) .$

The hypothesis $m \geq 1$ is not decoration. At $m = 0$ the expression $(\binom{n + m - 1}{m - 1})$ would require the value $m - 1$ at $m = 0$ , and Compositions and weak compositions of a natural number into a fixed number of parts records the true counts there: $∣ W (0, 0) ∣ = 1$ and $∣ W (n, 0) ∣ = 0$ for $n \geq 1$ . The hypothesis $n \geq 1$ in the second display is equally load bearing: at $n = 0$ , $m = 1$ the formula would give $(\binom{0}{0}) = 1$ while $C (0, 1) = \emptyset$ .

Facts & Assumptions

Given: Naturals $n$ and $m = σ (M)$ with $M \in N$ ; the sets $W (n, m)$ and $C (n, m)$ of Compositions and weak compositions of a natural number into a fixed number of parts; 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 $N$ .

[L1]

Induction (The principle of mathematical induction).

[L2]

Finite sums in $N$ (Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ , Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ ): the recursion clauses; additivity; the constant clause $\sum_{k < N} c = N \cdot c$ ; splitting at $p \leq N$ ; and the fact that a partial sum $\sum_{j < P} k_{j}$ with $P \leq N$ satisfies $\sum_{j < P} k_{j} \leq \sum_{j < N} k_{j}$ , which is splitting together with $x \leq x + t$ .

[L3]

Binomial coefficients (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ): $∣ [X]^{j} ∣ = (\binom{∣ X ∣}{j})$ ; $(\binom{N}{0}) = 1$ ; $(\binom{N}{j}) = 0$ for $j > N$ .

[L4]

The hockey-stick identity $\sum_{i < σ (N)} (\binom{i}{j}) = (\binom{σ (N)}{σ (j)})$ (Pascal's rule $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , and the hockey-stick identity $\sum_{i \leq n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ , clause 2).

[L5]

The sum rule and sums over a finite index set (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , 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).

[L6]

Cardinality and subsets (The cardinality $∣ A ∣$ of a finite set, A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ): transport; a subset of a finite set is finite; a subset of the same cardinality as the whole is the whole.

[L7]

Maps (Injection, surjection, bijection, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ): a map with a two-sided inverse is a bijection; an injection is a bijection onto its image.

[L8]

Arithmetic and order in $N$ : $σ (a) = a + 1$ ; $a + σ (b) = σ (a + b)$ ; addition is commutative and cancellative; $a \leq b$ and $b \leq c$ give $a \leq c$ ; trichotomy; $a \neq 0$ is the same as $1 \leq a$ (Order on the natural numbers, Addition is cancellative, Addition is commutative, Order is compatible with addition, Trichotomy of the order on $N$ , Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann)).

[L9]

Every nonempty subset of $N$ has a least element (The well-ordering principle).

Proof

technique · induction

1.1

The last-part decomposition, valid for every $M \in N$ and every $n$ . The map $k \mapsto (\sum_{i < M} k_{i}, k ↾ M)$ sends $W (n, σ (M))$ into the union of the pairwise disjoint sets ${j} \times W (j, M)$ for $j < σ (n)$ : writing $j : = \sum_{i < M} k_{i}$ , the recursion clause gives $j + k_{M} = n$ , so $j \leq n$ and $k ↾ M \in W (j, M)$ . Its two-sided inverse sends $(j, κ)$ to the tuple extending $κ$ by the value $n - j$ at $M$ , whose sum is $j + (n - j) = n$ . Hence $∣ W (n, σ (M)) ∣ = \sum_{j < σ (n)} ∣ W (j, M) ∣$ by [L5].

L2L5L7L8construct

1.2

Base case, $M = 0$ , that is $m = 1$ . A weak composition of $n$ into one part is a function $k : 1 \to N$ with $\sum_{i < 1} k_{i} = k_{0} = n$ , and there is exactly one such function; so $∣ W (n, 1) ∣ = 1 = (\binom{n + 0}{0})$ by [L3].

baseL2L3

1.3

Inductive hypothesis: fix $M$ and assume $∣ W (n, σ (M)) ∣ = (\binom{n + M}{M})$ for every $n \in N$ .

1.4

A reindexing identity: $\sum_{j < σ (n)} (\binom{j + M}{M}) = \sum_{i < σ (n + M)} (\binom{i}{M})$ . Split the right-hand side at $p = M$ , legitimate since $M \leq σ (n + M)$ : it becomes $\sum_{i < M} (\binom{i}{M}) + \sum_{j < σ (n + M) - M} (\binom{M + j}{M})$ . The first sum vanishes, every term being $(\binom{i}{M}) = 0$ for $i < M$ by [L3] and a sum of zeros being $0$ by the constant clause; and $σ (n + M) - M = σ (n)$ , because $M + σ (n) = σ (M + n) = σ (n + M)$ .

L2L3L8

2.1

Inductive step. Applying step 1.1 with $σ (M)$ in place of $M$ , then the hypothesis of step 1.3, then step 1.4 and finally the hockey-stick identity [L4] with $N = n + M$ and $j = M$ : $∣ W (n, σ (σ (M))) ∣ = \sum_{j < σ (n)} ∣ W (j, σ (M)) ∣ = \sum_{j < σ (n)} (\binom{j + M}{M}) = \sum_{i < σ (n + M)} (\binom{i}{M}) = (\binom{σ (n + M)}{σ (M)}) = (\binom{n + σ (M)}{σ (M)})$ , the last equality because $σ (n + M) = n + σ (M)$ . That is the claim at $σ (M)$ .

step 1.1step 1.3step 1.4L4L8

3.1

By step 1.2, step 2.1 and induction, $∣ W (n, σ (M)) ∣ = (\binom{n + M}{M})$ for every $M$ and every $n$ , which is the first display since $m = σ (M)$ and $M = m - 1$ .

step 1.2step 2.1L1

4.1

The explicit bijection. For $k \in W (n, σ (M))$ and $i < M$ put $s_{i} : = (\sum_{j < σ (i)} k_{j}) + i$ and $S (k) : = {s_{i} : i < M}$ . The list is strictly increasing, since $s_{σ (i)} = (\sum_{j < σ (i)} k_{j} + k_{σ (i)}) + σ (i) = s_{i} + k_{σ (i)} + 1$ ; and $s_{i} < n + M$ , since $\sum_{j < σ (i)} k_{j} \leq \sum_{j < σ (M)} k_{j} = n$ by [L2] and $i \leq M - 1$ . So $S (k)$ is a subset of $n + M$ with exactly $M$ elements, and $S$ maps $W (n, σ (M))$ into $[n + M]^{M}$ . It is injective: a strictly increasing list enumerating a finite subset of $N$ is determined by that subset, since its first entry is the least element and each later entry is the least element strictly above the previous one ([L9] and induction), so $S (k) = S (\tilde{k})$ forces $s_{i} = {\tilde{s}}_{i}$ for all $i < M$ ; then $k_{0} = s_{0}$ and $k_{σ (i)} = s_{σ (i)} - s_{i} - 1$ recover $k$ on $M$ , and $k_{M} = n - \sum_{j < M} k_{j}$ recovers the last part. Since both sets have $(\binom{n + M}{M})$ elements by step 3.1 and [L3], the image of $S$ is a subset of $[n + M]^{M}$ of the same cardinality, hence all of it by [L6]. So $S$ is a bijection.

step 3.1L2L3L6L7L8L9construct

4.2

The count of compositions, for $m = σ (M) \geq 1$ and $n \geq 1$ . If $m \leq n$ , the map $k \mapsto k^{'}$ with $k_{i}^{'} : = k_{i} - 1$ sends $C (n, m)$ into $W (n - m, m)$ : each $k_{i} \geq 1$ , so $k_{i} = k_{i}^{'} + 1$ , and $\sum_{i < m} k_{i} = \sum_{i < m} k_{i}^{'} + \sum_{i < m} 1 = \sum_{i < m} k_{i}^{'} + m$ by additivity and the constant clause, whence $\sum_{i < m} k_{i}^{'} = n - m$ . Its two-sided inverse adds $1$ to every part. So $∣ C (n, m) ∣ = ∣ W (n - m, m) ∣ = (\binom{(n - m) + M}{M})$ by step 3.1, and $(n - m) + M = n - 1$ because $(n - m) + m = n$ and $M = m - 1$ with $m \geq 1$ . If instead $m > n$ , then every $k \in C (n, m)$ would satisfy $n = \sum_{i < m} k_{i} \geq \sum_{i < m} 1 = m$ by monotonicity, which is false; so $C (n, m) = \emptyset$ , and $(\binom{n - 1}{m - 1}) = 0$ as well, since $m > n \geq 1$ gives $m - 1 > n - 1$ . In both cases $∣ C (n, m) ∣ = (\binom{n - 1}{m - 1})$ .

step 3.1L2L3L6L7L8

5.1

The count of weak compositions is step 3.1, the bijection realising it is step 4.1, and the count of compositions is step 4.2.

step 3.1step 4.1step 4.2discharge-induction∎

Remarks

The picture behind $S$ . Lay out $n$ stars and $M$ bars in a row of $n + M$ places; the bars split the stars into $σ (M) = m$ runs, whose lengths are the parts. The set $S (k)$ is the set of positions of the bars, and step 4.1 is that picture made precise. Surjectivity is obtained from the count rather than by constructing the inverse directly, which spares an appeal to the increasing enumeration of an arbitrary subset.

tikz \begin{tikzpicture}[x=0.85cm,y=1cm] \node at (2.55,1.25) {$k=(2,0,3)$}; \node at (0,0) {$\star$}; \node at (0.85,0) {$\star$}; \draw[line width=1pt] (1.7,-0.3) -- (1.7,0.3); \draw[line width=1pt] (2.55,-0.3) -- (2.55,0.3); \node at (3.4,0) {$\star$}; \node at (4.25,0) {$\star$}; \node at (5.1,0) {$\star$}; \node at (0,-0.65) {$0$}; \node at (0.85,-0.65) {$1$}; \node at (1.7,-0.65) {$2$}; \node at (2.55,-0.65) {$3$}; \node at (3.4,-0.65) {$4$}; \node at (4.25,-0.65) {$5$}; \node at (5.1,-0.65) {$6$}; \node at (2.55,-1.35) {$S(k)=\{2,3\}\subseteq 7$}; \end{tikzpicture}

Why the count is proved by induction and not by the bijection alone. Building the inverse of $S$ by hand needs the increasing enumeration of an arbitrary $M$ -element subset of $n + M$ , which is more machinery than the hockey-stick induction. The induction gives the number, and the number then gives the surjectivity of $S$ .
Both hypotheses are visible. The failure at $m = 0$ is recorded on the companion page as a false statement; the failure at $n = 0$ of the composition formula is recorded in the Statement above.

Depends on

Used by

Dependency tree · two levels

55 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)
Hockey-stick identity (Wikipedia) (standard reference, not scraped)

For m≥1m≥1 the number of weak compositions of nn into mm parts is (n+m−1m−1)(m−1n+m−1​), and the number of compositions is (n−1m−1)(m−1n−1​) for n≥1n≥1