### Notes

For constants $$n,k$$, the number of non-negative integer solutions to $$\sum_{i=1}^n x_i = k$$ is $$\binom{k+n-1}{k}$$

Sum rule: add up sizes of disjoint sets to get size of union

Bijection rule: you can count a set by counting a different set of the same size

Subset/combination rule: the number of ways to choose k out of n items is $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

3+x2+x3...+xn=k is equivalent to x2+x3...+xn=k-3

### Demo 2
Let $$n \ge 2$$ and $$k \ge 3$$. Count the number of non-negative integer solutions to $$\sum_{i=1}^n x_i = k$$ where $$x_1 \le 3$$.

### Alternate Solution

The set of *all* non-negative integer solutions (not just ones where $$x_1 \le 3$$) can be split into disjoint subsets where:

1. $$x_1\le 3$$ (these are the solutions we are trying to count)
1. $$x_1> 3$$ (these are "invalid" solutions)

The total number of solutions is $$\binom{k+n-1}{k}$$. 

To count the number of invalid solutions, consider a new variable $$x_*=x_1-4$$. Then the invalid solutions $$x_1+x_2+...+x_n=k$$ correspond exactly to the non-negative solutions of $$x_*+x_2+...+x_n=k-4$$. By the notes, there are $$\binom{(k-4)+n-1}{k-4}=\binom{k+n-5}{k-4}$$ such solutions.

By the sum rule, the number of valid solutions is $$\binom{k+n-1}{k}-\binom{k+n-5}{k-4}$$.


### Solution

The set of solutions can be split into disjoint subsets where:

1. $$x_1 = 3$$
1. $$x_1 = 2$$
1. $$x_1 = 1$$
1. $$x_1 = 0$$

The solutions where $$x_1=3$$ are precisely the solutions where the remaining $$n-1$$ variables sum to $$k-3$$. By the notes, there are $$\binom{(k-3)+(n-1)-1}{k-3}=\binom{k+n-5}{k-3}$$ such solutions.

By the same reasoning, the remaining cases have $$\binom{k+n-4}{k-2},\binom{k+n-3}{k-1},\binom{k+n-2}{k}$$ solutions.

Finally, the total number of solutions is (by the Sum rule) $$\binom{k+n-5}{k-3}+\binom{k+n-4}{k-2}+\binom{k+n-3}{k-1}+\binom{k+n-2}{k}$$.