0
$\begingroup$

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

  • 0
    I would be satisfied with an explicit bijection between $ S (\mathbb{N})$ and $S(\{0,1 \}) $.2012-01-22

1 Answers 1

4

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