1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mike Earnest Jan 23 at 19:38
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the answer. I can't upvote it due to my bad reputation. Sorry for that. $\endgroup$ – Parth Patel Jan 24 at 16:06
  • $\begingroup$ @ParthPatel You’re welcome! $\endgroup$ – Mike Earnest Jan 24 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.