# Number of ways for getting sum equal to s using inclusion-exclusion

I am trying very hard to understand following inclusion-exclusion problem but can't get it. It will be very helpful if someone can provide detail explanation.

f(s) is number of ways of having sum of elements equal to s in set T

g(i,j) is number of ways to get sum upto i using j distinct numbers from 1 to N.

Can anyone explain how

$$f(n) = \sum_{i \ge 1} (-1)^i*g(n,i)$$

This problem is actually from competitive programming if someone wants to refer to full resource and it's solution is also there.

• I explained the solution, but I could not answer your question directly because what your interpretation of $f(n)$ is not correct. $s(n)$ in their solution is not actually counting anything. – Mike Earnest Jan 23 at 19:38

You are trying to count the number of solutions to $$x_1+x_2+\dots+x_{n} = k$$ which satisfy $$0\le x_a\le a-1$$ for all $$1\le a \le n$$.
If we replaced this with the weaker condition $$0\le x_a$$, the answer would be $$\binom{k+n-1}k$$. Here is where inclusion-exclusion comes into play; you take all $$\binom{k+n-1}k$$ solutions, subtract the "bad" solutions where one of the variables satisfies $$x_a\ge a$$, then add back in the doubly subtracted solutions where two of the variables are too big, etc.
Suppose we want to count solutions where $$x_a\ge a$$ for all $$a\in S$$. That is, all of the variables in $$S$$ (and possibly others) are too big. Subtracting $$a$$ from each of the bad variables, this is the same as solving $$x_0+x_1+\dots+x_{n-1}=k-\Big(\sum_{i\in S}i\Big)$$ Letting $$i$$ be the sum in question, the number of solutions is $$\binom{k-i+n-1}{k-i}$$. Furthermore, if this subset has size $$i$$, then it its sign in the inclusion exclusion sum will be $$(-1)^i$$.
When performing the inclusion-exclusion, we must sum over all subsets $$S$$. However, we can group together all of the subsets $$S$$ which have the same sum and size, as this is all that is needed to compute their contribution. This is where the $$f(i,j)$$ comes into play; it is the number of subsets with sum $$i$$ and size $$j$$. Therefore, the final answer is $$\sum_{i=0}^k \binom{n-1+(k-i)}{(k-i)}\sum_{j\ge 0}(-1)^j f(i,j)$$