Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  Elias 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 \}) $. –  Elias Jan 22 '12 at 9:09
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.