Counting the number of ways in which an integer can be written as a sum of other two integers belonging to two different finite sets.

Question

I am trying to count the number of ways in which I can write a given $l = 1,.., a+b$ as $l = j+m$ where $j = 1, .., a$ and $m = 0, .. ,b$. I suppose partitions could be used to solve the problem, but I am not an expert of those and do not really know how to use them properly. Any help would be appreciated.

Answer 1

By stars and bars the number of ways to write a number l as a sum of two positive numbers is: $$ \binom{l-2+(2-1)}{2-1}=\binom{l-1}1. $$ From this number we should subtract the number of combinations with $j>a$ and $m>b$, which are $$ \binom{l-a-1}1\quad\text{and}\quad \binom{l-b-1}1, $$ respectively. Fol $l>a+b$ this would however double count the expressions with both $j>a$ and $m>b$. Therefore by inclusion-exclusion the final result valid for any $l>0$ is: $$ \binom{l-1}1-\binom{l-a-1}1-\binom{l-b-1}1+\binom{l-a-b-1}1, $$ with the convention $\binom nk=0$ if $n<0$, so that the expression can be written as: $$ l-1-\max(0,l-a-1)-\max(0,l-b-1)+\max(0,l-a-b-1). $$