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.
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) $$