Stars and Bars But With A Unique Upper Limit For Each

Question

This question has been asked before on here:

We can know the number of solutions such that $a_1+a_2+a_3+....a_n=N$, $a_i\geq0$, and $i\in\{1,2,\ldots,n\}$ can be found by stars and bars ($\binom{N+n-1}{n-1}$). But if we (like the question linked) wanted to then add the requirement that each $a_i\leq r_i$ and that $r_i$ can be unique for each $i$ how many combinations are there?

I've been trying to understand Mike Earnest's answer as theirs seemed more understandable but have come short on the last equation: $$\sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1}$$ From my understanding, it seems that the larger summation is used to subtract $x$ number of combinations from the total amount, but that seems to be contradictory with $(-1)^{|S|}$ since it would change from adding or subtracting based on if $S$ is even or odd? I also was wondering if there was any reason it was total value and not just $S$?

I also think I understand how we get ${\sum_{i\in S}(r_i+1)}$ since it's the same as the equation done before but it seems to mess up the equation since it often produces a negative factorial integer which can't be solved. I know to define $\binom{m}k=0$ when $m < 0$ but don't seem to get an accurate answer with these 2 questions lingering.

If we take the example that is given in the past post that $N = 6, n = 3$, and $(r_1,r_2,r_3)=(3,3,2)$ then our answer should be 5 since the only possibilities are (1,3,2), (2,2,2), (3,2,1), (3,1,2), and (2,3,1) but if we calculate it, it would be:$$\binom{6+3-1}{3-1}-\sum_{S\subseteq \{1,2,3\}}(-1)^{|S|}\binom{6+3-1-\sum_{i\in S}(r_i+1)}{3-1}$$ $$\binom{8}{2}-((-1)^{|1|}\binom{8-(3+3+2)}{2}+(-1)^{|2|}\binom{8-(3+3+2)}{2}+(-1)^{|3|}\binom{8-(3+3+2)}{2})$$ I wasn't sure what $i\in S$ meant when used in a summation, so I assumed it was the summation of all the numbers 1-3 in case that was where I went wrong. Thanks for any help!

Answer 1

We consider the special case $N=6, n=3$ and $(r_1,r_2,r_3)=(3,3,2)$. The valid triples $(a_1,a_2,a_3)$ with $0\leq a_j\leq r_j,1\leq j\leq 3$ are: \begin{align*} &(1,3,2)\qquad\qquad(3,1,2)\\ &(2,2,2)\qquad\qquad(3,2,1)\\ &(2,3,1)\qquad\qquad\color{blue}{(3,3,0)}\\ \end{align*} Note that we have $6$ valid triples since $a_j\geq 0$ and so $(3,3,0)$ is valid.

In the following we use the notation $[n]:=\{1,2,\ldots,n\}$ and define $\binom{p}{q}=0$ if $p<0$.

We obtain \begin{align*} \sum_{S\subseteq [n]}&(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1}\\ &=\color{blue}{\sum_{S\subseteq [3]}(-1)^{|S|}\binom{8-\sum_{i\in S}(r_i+1)}{2}}\\ &=(-1)^{|\emptyset|}\binom{8}{2}\\ &\quad+(-1)^{|\{1\}|}\binom{8-4}{2}+(-1)^{|\{2\}|}\binom{8-4}{2}+(-1)^{|\{3\}|}\binom{8-3}{2}\\ &\quad+(-1)^{|\{1,2\}|}\binom{8-(4+4)}{2}+(-1)^{|\{1,3\}|}\binom{8-(4+3)}{2}\\ &\quad\qquad+(-1)^{|\{2,3\}|}\binom{8-(4+3)}{2}\\ &\quad+(-1)^{|[3]|}\binom{8-(4+4+3)}{2}\\ &=\binom{8}{2}-\binom{4}{2}-\binom{4}{2}-\binom{5}{2}+0+0+0-0\\ &=28-6-6-10\\ &\,\,\color{blue}{=6} \end{align*} in accordance with the list above.