Proof of Counting Tuples with a Given Sum

For $p\in\mathbb{N}$ and $s\in\mathbb{N}_{0}$ let

$$N_{p}(s)=\{x\in\mathbb{N}_{0}^{p}:x_{1}+\dots+x_{p}=s\},$$

where $x_{1}+\dots+x_{p}=\sum_{i=1}^{p}x_{i}$ is formed in $\mathbb{N}_{0}$. Throughout, for $t\in\mathbb{N}_{0}^{p}$ and $y\in\mathbb{N}_{0}$, $(t_{1},\dots,t_{p},y)$ is the tuple of Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (vi), so that $(t,y)\mapsto(t_{1},\dots,t_{p},y)$ is a bijection from $\mathbb{N}_{0}^{p}\times\mathbb{N}_{0}$ onto $\mathbb{N}_{0}^{p+1}$; and by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii) the entries of this tuple add up to

$$t_{1}+\dots+t_{p}+y=(t_{1}+\dots+t_{p})+y.$$

Step 1 (the claim for (i)). We show by induction on $q\in\mathbb{N}_{0}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii)) that for every $s\in\mathbb{N}_{0}$ the set $N_{q+1}(s)$ is finite and

$$\#N_{q+1}(s)=\binom{s+q}{q}.$$

The case $q=k$, $s=n$ is (i).

Step 2 (one entry). Let $q=0$ and $s\in\mathbb{N}_{0}$. Since $[1]=\{1\}$, the entries of $x\in\mathbb{N}_{0}^{1}$ add up to $x_{1}$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i)), so $N_{1}(s)$ consists of the $1$-tuples with $x_{1}=s$. There is exactly one such tuple, the map on $[1]$ with value $s$ (Maps Formed Pointwise: Constant Maps, Pairs of Values, Maps Applied to Values, and Families of Maps (i)). So $N_{1}(s)$ is a singleton, finite with one element (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iii), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii)), and

$$\binom{s+0}{0}=\binom{s}{0}=1$$

by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (i) and Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (i).

Step 3 (sorting by the sum of all entries but the last). Assume the claim for $q$, and let $s\in\mathbb{N}_{0}$. For $r\in\{0,\dots,s\}$ let

$$C_{r}=\{(t_{1},\dots,t_{q+1},s-r):t\in N_{q+1}(r)\}.$$

The map $t\mapsto(t_{1},\dots,t_{q+1},s-r)$ is injective, being a restriction of the bijection above, so it is a bijection from $N_{q+1}(r)$ onto $C_{r}$. By Counting through Bijections, Injections and Surjections (i) and the induction hypothesis, $C_{r}$ is finite and

$$\#C_{r}=\#N_{q+1}(r)=\binom{r+q}{q}.$$

Step 4 (the sets $C_{r}$ partition $N_{q+2}(s)$). Let $x\in N_{q+2}(s)$, and write $x=(t_{1},\dots,t_{q+1},y)$ with $t\in\mathbb{N}_{0}^{q+1}$ and $y\in\mathbb{N}_{0}$. Put $r=t_{1}+\dots+t_{q+1}$. Then $r+y=s$, so $r\le s$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii) and $y=s-r$ by The Difference of Two Natural Numbers with Zero (i); thus $t\in N_{q+1}(r)$ and $x\in C_{r}$ with $r\in\{0,\dots,s\}$. Conversely, for $r\le s$ and $t\in N_{q+1}(r)$ the entries of $(t_{1},\dots,t_{q+1},s-r)$ add up to $r+(s-r)=s$, again by The Difference of Two Natural Numbers with Zero (i), so $C_{r}\subseteq N_{q+2}(s)$. Finally, if $x\in C_{r}\cap C_{r'}$, then $x=(t_{1},\dots,t_{q+1},s-r)=(t'_{1},\dots,t'_{q+1},s-r')$ with $t\in N_{q+1}(r)$ and $t'\in N_{q+1}(r')$; injectivity of the bijection above gives $t=t'$, and hence $r=t_{1}+\dots+t_{q+1}=r'$. So

$$N_{q+2}(s)=\bigcup_{r=0}^{s}C_{r},$$

a union of pairwise disjoint sets.

Step 5 (counting). The index set $\{0,\dots,s\}$ is finite (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii)). By The Number of Elements of a Disjoint Finite Union (i), Step 3 and Binomial Identities (vi), $N_{q+2}(s)$ is finite and

$$\#N_{q+2}(s)=\sum_{r=0}^{s}\binom{r+q}{q}=\binom{s+q+1}{q+1}=\binom{s+(q+1)}{q+1},$$

the last step by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iii). This is the claim for $q+1$, which completes the induction and proves (i).

Step 6 (adding one to every entry). Let $P$ be the set in (ii). Counting $[k+1]$ as the disjoint union of its singletons (The Number of Elements of a Disjoint Finite Union (i), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i)), $\sum_{i=1}^{k+1}1=\#[k+1]=k+1$. For $y\in\mathbb{N}_{0}^{k+1}$ let $y+\mathbf{1}=(y_{1}+1,\dots,y_{k+1}+1)$; its entries lie in $\mathbb{N}$, since $y_{i}+1\neq0$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (viii) as $1\neq0$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ii)). By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (v),

$$\sum_{i=1}^{k+1}(y_{i}+1)=\sum_{i=1}^{k+1}y_{i}+\sum_{i=1}^{k+1}1=\sum_{i=1}^{k+1}y_{i}+(k+1).$$

So for $y\in N_{k+1}(n)$ the entries of $y+\mathbf{1}$ add up to $n+(k+1)=n+k+1$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iii)), and $y\mapsto y+\mathbf{1}$ maps $N_{k+1}(n)$ into $P$.

Step 7 (the map is a bijection). It is injective: if $y_{i}+1=y'_{i}+1$ for every $i$, then $y_{i}=y'_{i}$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (v) and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv). It is onto $P$: let $x\in P$. Each $x_{i}$ lies in $\mathbb{N}$, so $1\le x_{i}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v)), and $y_{i}=x_{i}-1\in\mathbb{N}_{0}$ satisfies $y_{i}+1=x_{i}$ (The Difference of Two Natural Numbers with Zero (i)). Then $y=(y_{1},\dots,y_{k+1})$ satisfies $y+\mathbf{1}=x$, and by Step 6

$$\sum_{i=1}^{k+1}y_{i}+(k+1)=\sum_{i=1}^{k+1}x_{i}=n+(k+1),$$

so $\sum_{i=1}^{k+1}y_{i}=n$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (v) and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv), that is, $y\in N_{k+1}(n)$.

Step 8 ((ii)). By Step 7, Counting through Bijections, Injections and Surjections (i) and (i), $P$ is finite and

$$\#P=\#N_{k+1}(n)=\binom{n+k}{k}.$$