How many solutions are there to $x+y+z=14$ where $x,y,z$ are all non-negative integers, $x \leq 5, y \leq 6, z \leq 7$?

Question

Through using brute force, I have got 15 triplets of solutions. Have I reached the right answer, and how can I not use brute force?

Answer 1

For the given conditions, the maximum values of x, y and z are: $$\begin{align} x={} & 5 \\ y= {} & 6\\ z = {} & 7 \\ \sup(x+y+z) = {} & 18 \end{align}$$

Hence we must subtract 4 from $x$, $y$ and $z$ collectively such that $x+y+z=14$.

Of the 5 partitions of 4, all except 1+1+1+1 are possible allocations.

• 4+0+0 - ${3\choose1}=3$ ways of allocating.
• 3+1+0 - $3!=6$ ways of allocating.
• 2+2+0- ${3\choose1}=3$ ways of allocating.
• 1+1+2- ${3\choose1}=3$ ways of allocating.

Thus, as you calculated, $3+6+3+3=15$ integer solutions.

Answer 2

Using generating functions, like in this example $$x_1+x_2+x_3=14$$ $$0\leq x_1 \leq5$$ $$0\leq x_2 \leq6$$ $$0\leq x_3 \leq7$$ the generating function is $$(1+x+...+x^5)(1+x+...+x^6)(1+x+...+x^7)$$ and the coefficient near $x^{14}$ term is the answer, which is 15.

Answer 3

To explain my comment above, which you seem to have not understood, your question is essentially the same as that of finding how many 14-element sub-multisets exist of the set $\{x,x,x,x,x,y,y,y,y,y,y,z,z,z,z,z,z,z\}$ which is discussed here.

Borrowing from the other post, given $n$ distinct letters available, wishing to take a $k$-element submultiset, and having $c_1,c_2,\dots,c_n$ of each respective letter available respectively, the general solution will be $$\sum\limits_{i=0}^n\left((-1)^i\sum\limits_{\Delta\subseteq [n]~:~|\Delta|=i}\binom{n+k-1-\sum\limits_{j\in\Delta}(c_j+1)}{n-1}\right)$$

In your specific case we have $n=3,k=14,c_1=5,c_2=6,c_3=7$;

$$\binom{16}{2} - \binom{10}{2}-\binom{9}{2}-\binom{8}{2}+\binom{3}{2}+\binom{2}{2}+0-0=15$$

This method comes from a combination of stars and bars and inclusion-exclusion, running inclusion-exclusion on the events that some $x_i$ violated it's respective upper bound condition.

Answer 4

Here is another way to solve the problem.

Since, $x \leq 5, y \leq 6$ and $z \leq 7$, we can define $x_1, x_2, x_3$ as $5-x,6-y$ and $7-z$ respectively. Clearly, $x_1, x_2$ and $x_3$ are all non-negative integers. The original equation can thus be rewritten as

$$x_1 + x_2 + x_3 = 4$$

This has $\binom{4+2}{2} = 15$ solutions.