Solutions of some diophantine equation

Question

How many solutions has the equation $x_1+x_2+\cdots+x_k=n$ in non-negative integers?

Answer 1

This problem can be easily solved by combinatorial tools. We have an equation $$x_1+x_2+\cdots+x_k=n \qquad (*)$$ 1. We'll find number of solutions of above equation in $\mathbb{N}_0=\mathbb{N}\cup\{0\}$. With every solution $(x_1,x_2,\dots,x_k)$ of this equation we can associate a finite sequence consisting of $0$ and $1$. $$(x_1,x_2,\dots,x_k)\mapsto \underbrace{00\dots0}_{x_1}1\underbrace{00\dots0}_{x_2}1\dots 1\underbrace{00\dots0}_{x_k}.$$ It's easy to check that this mapping would be bijective. This sequence contains $x_1+x_2+\cdots+x_k=n$ zeros and $k-1$ ones. So we must find the number of all different permutations of $n$ zeros and $k-1$ ones. It's equal to $$P(k-1,n)=\dfrac{(n+k-1)!}{(k-1)!n!}=C_{n+k-1}^{k-1}.$$ Hence it's the number of solutions of above equation in non-negative numbers.

2. Now we'll find number of solutions of above equation in $\mathbb{N}$. Note that this equation has not solutions if $n<k$. Suppose that $n\geqslant k$. We'll do this transform: $(x_1-1)+\dots+(x_k-1)=n-k$ and put $y_i:=x_i-1$ and we must find the number of solutions of $y_1+\cdots+y_k=n-k$ in non-negative numbers. We can apply the first part of problem and we get the answer:$$C_{(n-k)+k-1}^{k-1}=C_{n-1}^{k-1}.$$ Q.E.D.