Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|improve this answer

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.