How many ordered quadruples $(a,b,c,d)$ satisfy $a+b+c+d=18$ under various conditions?

Question

part (a)

How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are nonnegative integers?

(part (b) How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are odd positive integers?

part (c)

How many ordered quadruples $(a,b,c,d)$ satisfy $$a+b+c+d=18,$$ where $a,b,c,d$ are integers such that $|a|,\ |b|,\ |c|,\ |d|$ are each at most $10$?

For part (a) I counted the number of positive quadruples which is 18+4=22 so it would be 21C3 = 1330 ways to do that. But, I'm not sure how to do part (b) or (c).

Answer 1

A reasonable way to approach parts (b,c) is to attempt to reduce them to problems of type (a): "How many ordered quadruples $(a,b,c,d)$ satisfy $a+b+c+d = k$ where $a,b,c,d$ are nonnegative integers?" So heuristically, the goal is to make nonnegative integers out of odd positive integers, and out of integers whose absolute values are at most 10. Can you come up with a way to re-parametrize solutions to parts (b,c) based on ranges of nonnegative integers?

Answer 2

Part (a): read about stars and bars

$\binom{18+4-1}{4-1}$

Part (b)

$a=2p+1 , b=2q+1 , c=2r+1 , d=2s+1$

$p+q+r+s=7$

Stars and bars again

$\binom{7+4-1}{4-1}$

Part (c)

Continuing Brian’s solution, $a+10=w , b+10=x , c+10=y , d+10 = z$

$w+x+y+z=58$ where all four are at most 20.

Quadruples with at least one greater than 20:divide 37 into 4 and then add 21 to one of the four numbers

$\binom{37+4-1}{4-1}\times 4$

Quadruples with two greater than 20: divide 16 into 4 and then add 21 to two of the four numbers

$\binom{16+4-1}{4-1}\times\binom{4}{2}$

Last we use principle of inclusion and exclusion

$\binom{58+4-1}{4-1}-\binom{37+4-1}{4-1}\times 4 + \binom{16+4-1}{4-1}\times\binom{4}{2}$ =$2284$

Answer 3

I agree with your (a) answer and Rezha's (b) looks good.

For (c), moving everything up by 10 gives you 4 nonnegative numbers with sum 58, but summands over 20 definitely come up a lot. Here's the trick: Move everything down 10 instead, then multiply everything by $-1$: \begin{align} a + b + c + d = 18 & \quad \text{with } -10 \le a, b, c, d \le 10 \\ (a-10) + (b-10) + (c-10) + (d-10) = 18-40 \\ \alpha + \beta + \gamma + \delta = -22 & \quad \text{with } -20 \le \alpha, \beta, \gamma, \delta \le 0 \\ -\alpha - \beta -\gamma - \delta = 22 \\ w + x + y + z = 22 & \quad \text{with } 0 \le w, x, y, z \le 20 \end{align} That is, move the variables down 10 and then negate them. The range of allowed values goes from $[-10,10]$ to $[-20,0]$ to $[0,20]$, so a maximum constraint is still in effect. But the sum went from 18 to $18-40 = -22$ to 22: we'll see that the maximum constraint won't matter much when it's so close to the sum.

Count solutions to $w + x + y + z = 22$ as in (a), I believe you get ${25 \choose 3} = 2300$. Those include some solutions with values over 20, but very few: You could have $(22,0,0,0)$ with 4 ways to assign the 22, and $(21,1,0,0)$ with 12 ways to assign the 21 and 1 (not just ${4 \choose 2}=6$ ways since, e.g., $(0,21,0,1)$ and $(0,1,0,21)$ are distinct solutions). Removing those 16 "bad" solutions leaves 2284 with allowed values.

PS: In the time it takes to think of that and work out the details, you could find a computer algebra system and look up the coefficient of $x^{18}$ in the expansion of $$(x^{-10} + x^{-9} + \cdots + x^{-1} + x^0 + x^1 + \cdots + x^9 + x^{10})^4$$ which is, in fact, 2284.