Number of k-tuples of non-negative integers whose sum equals a given integer

Solution 1:

Let $ n,k\in\mathbb{N}^{*}\left(=\mathbb{N}\setminus\left\lbrace 0\right\rbrace\right) $.

If $ \left(a_{i_{1},\cdots,i_{k}}\right)_{i_{1},\cdots,i_{k}\geq 0}\in\mathbb{R}^{\mathbb{N}^{k}} $, then : \begin{aligned}\large\sum_{i_{1}+\cdots +i_{k}=n}{a_{i_{1},\cdots,i_{k}}}=\sum_{0\leq i_{1}\leq\cdots\leq i_{k-1}\leq n}{a_{n-i_{1},i_{1}-i_{2},\cdots ,i_{k-2}-i_{k-1},i_{k-1}}}\end{aligned}

Thus : $$ \sum_{i_{1}+\cdots +i_{k}=n}{1}=\sum_{0\leq i_{1}\leq\cdots\leq i_{k-1}\leq n}{1}=\binom{n+k-1}{k-1} $$

$\textbf{Note :}$ You can prove by induction on $ k $, that $ \sum\limits_{0\leq i_{1}\leq\cdots\leq i_{k}\leq n}{1}=\binom{n+k}{k} $, denoting $ u_{n,k}=\sum\limits_{0\leq i_{1}\leq\cdots\leq i_{k}\leq n}{1} $, we have : $$ u_{n,k}=\sum_{i=0}^{n}{u_{i,k-1}} $$