# 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 \})$.

-
You can get the appropriate ellipsis using \dotsc for dots between $\mathbf c$ommas and \dotso for dots between binary $\mathbf o$perators. –  joriki Jan 17 '12 at 22:33
Clearly $S(\mathbb Z)$ is infinite since you can just increment one of the $x_i$ and decrement another to get another solution. Perhaps you mean $\mathbb N$ and not $\mathbb Z$? –  joriki Jan 17 '12 at 22:37
Thank joriki. Excuse me the slip. –  אליהו צלע Jan 17 '12 at 22:40
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 \})$. –  אליהו צלע Jan 22 '12 at 9:09
add comment

## 1 Answer

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$.

-
I already knew this "algorithm" of bars and stars. Excuse me again. I should have made ​​it clear that the purpose of the question was a rigorous mathematical justification of this "algorithm". –  אליהו צלע Jan 18 '12 at 10:53
Indeed you should have made that clear. Also, you should now make clear what level of rigour you're aiming for. The stars and bars method is not an "algorithm"; it's a method of proof. Are you looking for a formal proof from the axioms of set theory? Anything in between? Currently it's anyone's guess what sort of answer might answer your question. BTW, I'm unable to ping you because your name in the Hebrew script isn't being offered as one of the auto-completions and I'm finding it difficult to copy it correctly. You might want to use a name in the Latin script and/or file this as a bug. –  joriki Jan 18 '12 at 11:05
Eliahu, did you vote joriki's answer down? Someone did, and that makes no sense to me. It's not joriki's fault that he answered the question Eliahu actually asked, instead of reading Eliahu's mind and answering the question Eliahu meant to ask. If you find something wrong with joriki's mathematics, say so, but otherwise it's a good answer to the question as actually asked, and deserves upvotes, not a downvote. –  Gerry Myerson Jan 18 '12 at 11:40
add comment