If $a + b + c + d = 45$, how many combinations are there of $a,b,c$, and $d$ if $a \le 5$ and $b \le 3$?

Question

I'm stumped on binomial coefficients and counting problems in discrete math.

To be clear, this is not the same problem I'm having to do for homework. I changed the numbers around, but had to include a constant as the answer for the sake of time.

How many combinations of a, b, c, and d are there when $a + b + c + d = 45$, $a \leq 5$ and $b \leq 3$?

EDIT: I want a general answer, so I can know HOW to solve the problem. So, a general formula would be nice.

Answer 1

We are given the following system:

$\begin{cases} a + b + c + d=45\\ 0\leq a\leq 5\\ 0\leq b\leq 3\\ 0\leq c\\ 0\leq d\end{cases}$

Approach via inclusion-exclusion.

Let $X$ denote the event where we ignore the upper bound conditions, $X_a$ denote the event where the upper boundary condition on $a$ is broken (and possibly on $b$ too), $X_b$ is the event where the upper boundary condition on $b$ is broken (and possibly on $a$ too), and finally $X_{a,b}$ as the event where both upper bounds are broken.

Looking at $X$, we have the system

$\begin{cases} a + b + c + d=45\\ 0\leq a\\ 0\leq b\\ 0\leq c\\ 0\leq d\end{cases}$

which has $\binom{45+4-1}{4-1} = \binom{48}{3}$ possibilities.

Looking in more detail at $X_a$, we are asked to count the number of solutions to the system

$\begin{cases} a + b + c + d=45\\ 6\leq a\\ 0\leq b\\ 0\leq c\\ 0\leq d\end{cases}$

We can use a change of variables here, setting $a' = a-6$, giving us the system

$\begin{cases} a' + b + c + d=39\\ 0\leq a'\\ 0\leq b\\ 0\leq c\\ 0\leq d\end{cases}$

which has $\binom{39+4-1}{4-1}=\binom{42}{3}$ possibilities.

Do so similarly for calculating how many possibilities there are for $X_b$ and $X_{a,b}$

The final total which does not violate either upper boundary condition will be $$|X|-|X_a|-|X_b|+|X_{a,b}|$$

Answer 2

We work with your specific problem. The reasoning is described in fair detail, so that the ideas used can become more familiar, and can be reused in similar contexts.

I assume you know how to find the number of solutions of $a+b+c+d=45$ in non-negative integers, since that is basic Stars and Bars.

Now we must remove the bad choices, where $a\gt 5$ or $b\gt 3$.

How many choices have $a\gt 5$? Give $a$ $6$ items, and distribute the remainder between $a$, $b$, $c$, and $d$. So the number of choices with $a\gt 5$ is the number of solutions of $a+b+c+d=39$. Call this $x$.

Similarly, we can calculate the number $y$ of bad choices where $b\gt 3$.

So is $x+y$ the number of bad choices? Not quite! For $x+y$ double-counts the choices where $a\gt 5$ and $b\gt 3$. But by reasoning similar to the above, the number of doubly bad choices $z$ is the number of solutions of $a+b+c+d=35$.

So now we know the number of bad choices, it is $x+y-z$, and we can finish.