counting ways for sum with maximums on variables

Question

If $a < 3$ and $b < 4$ and $a, b, c, d \geq 0$, how may different combinations are there for $a + b + c + d = 10$?

I've tried star and bar method but had no luck. How can I approach this?

Answer 1

I am assuming $a,b,c,d \in \mathbb{Z}$ and non-negative. And even though you mentioned combination, I assume $a=b=c=0,d=10$ is different from $a=b=d=0, c=10$. It very easy to tune it if you intended otherwise.

This problem can be most elegantly solved with additive number theory method. As I don't know it (yet :), I will approach it with a computer algorithm method called dynamic programming.

Define $p(n,m)$ the number of ways of partitioning an integer $n$ into sum of $m$ non-negative integers. $p(n,m)$ can be arranged into a $n\times m$ matrix/grid to minimize counting work.

So our problem becomes evaluation of $p(10,4)$ with the restriction $a<3, b<4$.

$p(10,4)=p(10,3)+p(9,3)+p(8,3)$ RHS, assign $0,1,2$ to $a$ respectively and pass to next level

$p(10,3)=p(10,2)+p(9,2)+p(8,2)+p(7,2)$ RHS, assign $0,1,2,3$ to $b$ respectively and pass to next level；

$p(9,3)=p(9,2)+p(8,2)+p(7,2)+p(6,2)$ RHS, assign $0,1,2,3$ to $b$ respectively and pass to next level;

(Note: $p(9,2),p(8,2)$ etc appears on RHS multiple times, the intention of a dynamic programming is to process these repetition only once.)

$\cdots$

$p(10,2)=p(10,1)+p(9,1)+\cdots+p(0,1)=11$, assign $0,1,2,\cdots,10$ to $c$ respectively. And each represent a final scheme, so we have $11$ ways...

Make a table and do it manually. It's a good educational experience to understand dynamic programming.

Answer 2

There are three possible values $(0,1,2)$ for $a$ and four $(0,1,2,3)$ for $b$. Thus there are twelve settings for $a$ and $b$. For each setting, there are $10 - (a+b) + 1$ possible values for $c$. Then $d$ is constrained and fixed.

So go through the $12$ settings for $a$ and $b$, and for each, add up the number of settings for $c$. And you're done!

For instance: $a=0, b=0$ leads to $11$ possible values for $c$ $(0, 1, \ldots, 10)$ and then $d$ is constrained.

I get $102$.