# The number of solutions of linear equations.

Suppose that $n$ and $k$ to be non-negative integers with $k < n$.

Let $S(\{0,1 \})$ the number of integer solutions $y = (y_1, \dotsc, y_{n-1 + k})$ with $y_j \in \{1,0 \}$ and $j = 1,\dotsc, n -1 + k$ of the equation $$y_1+\dotso+y_{n+k-1}=k.$$ Let $S (\mathbb{N})$ the number of integer solutions $x = (x_1, \dotsc, x_{n})$ with $x_i \in \mathbb{N}$ and $i = 1,\dotsc, n$ of the equation $$x_1+\dotso+x_n=k.$$ Prove that $S (\mathbb{N})=S(\{0,1 \})$.

Edited 1. There is the "algorithm" with bars and stars (see eg Wikipedia) that "proves" this equality. But the purpose of this question is simply to give a rigorous mathematical justification for this algorithm.

Edited 2. I am interested in a demonstration of the level set theory. I would be satisfied with an explicit bijection between $S (\mathbb{N})$ and $S(\{0,1 \})$.

-
A demonstration at the level of set theory? Do you know that it took Russell and Whitehead 586 pages to produce a demonstration of $1+1=2$ at the level of set theory? – Gerry Myerson Jan 18 '12 at 11:42
I would be satisfied with an explicit bijection between $S (\mathbb{N})$ and $S(\{0,1 \})$. – MathOverview Jan 22 '12 at 9:09

In $y_1+\dotso+y_{n+k-1}=k$ there must be $k$ ones and $n-1$ zeros. Treat the ones as stars and the zeros as bars (see stars and bars). Then the $n-1$ bars form $n$ compartments of stars, and the counts of the stars in the compartments correspond to the numbers $x_i$.