0
$\begingroup$

I just want to ask if there is any way to distinguish whether a problem is solved with the principle of inclusion and exclusion or combinations or permutations. Is there any way I can find out if I look at an problem?

I know that it is not a concrete question, only sometimes I don't know which principle / formula to use.

$\endgroup$
1
$\begingroup$

Often times, a problem can be approached by inclusion-exclusion or just by directly counting with permutations and combinations. However, inclusion-exclusion can often make a problem much easier to solve.

Inclusion-Exclusion occurs when you can rephrase a question so you are trying to count the union of many sets. For example with derangements (ie. the number of permutations where no element is mapped to itself), it is not immediately clear this could be tackled by inclusion-exclusion. However, if you phrase it as defining the set $S_i = \#\text{permutations with element }i\text{ fixed}$, and then count $|S_1\cup S_2\cup\cdots\cup S_n|$, you will get the complement of the number of derangements. When phrased this way, it is much clearer that you would like to use inclusion-exclusion, as you are now trying to count the size of a union.

The trick is finding the right restatement of a problem so you are counting unions. This just takes practice to do.

$\endgroup$
  • $\begingroup$ Okay, thank you so much, I will try to look at the problems in that way $\endgroup$ – Shelley Nov 11 '19 at 19:27

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.