1
$\begingroup$

Today I came across the inclusion-exclusion principle for the first time. I believe I have understood it, however when I tried solving some questions on it, I got severely stuck. I couldn't solve any of them. Could you please suggest some questions of escalating difficulty, so that I can get a good grasp on the topic at hand? One of the questions is this one :https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , It was in a Greek contest-math book and I also found it on this site.

The other question I couldn't find it on the internet, so I'll translate it:

Find the number of solutions to the equation $x_1+x_2+x_3=100$, if for every $3\ge i\ge1$, xi is a non negative integer with $40\ge x_i$.

I have found the solutions to both of these questions, the reason which I am posting them as well, is to give a better understanding to the reader of the post , of what level of questions in inclusion-exclusion principle are giving me difficulty. Could you please suggest some resources on this principal (e.g. questions of escalating difficulty and theory)?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I think it is admirable that you are teaching yourself this content, and certainly a sequence of progressively more difficult questions is a good way to go! However, this is a site for mathematics educators to answer each others questions about how to teach. I think this question is off topic here. Maybe it would fit better at math.stackexchange.com, but I am not sure. $\endgroup$
    – Steven Gubkin
    Oct 17 '20 at 15:16
  • $\begingroup$ @StevenGubkin the problem is that I have already asked on math.stackexchange.com but unfortunately no one has answered there. So I was hoping that someone here would know $\endgroup$
    – Michael
    Oct 17 '20 at 15:38
  • $\begingroup$ I would suggest looking on MSE for inclusion/exclusion. There are probably hundreds of problems you could try, and then you could check your answer. $\endgroup$
    – Steven Gubkin
    Oct 17 '20 at 15:40
  • $\begingroup$ Yes @StevenGubkin but how about the theory? And how would I know which question are easier and which harder so as to study methodically $\endgroup$
    – Michael
    Oct 17 '20 at 15:43
  • 3
    $\begingroup$ See Mathematics of Choice by Ivan Niven (1965). For what it's worth, problems like this can be relatively straightforward with the appropriate tools (found in the book I cited) and they can be quite difficult even with a reasonable knowledge of these tools, and sometimes it's not easy to tell in advance unless one is very experienced in this topic. (I speak from experience, as someone not an expert in combinatorics, who has had to work hundreds of problems like this in the past few years for my "day job".) $\endgroup$
    – Dave L Renfro
    Oct 17 '20 at 16:58
3
$\begingroup$

See Mathematics of Choice. How to Count Without Counting by Ivan Niven (1965). For what it's worth, problems like this can be relatively straightforward with the appropriate tools (found in the book I cited) and they can be quite difficult even with a reasonable knowledge of these tools, and sometimes it's not easy to tell in advance unless one is very experienced in solving these types of problems.

I've solved quite a few problems like this in the past three years as part of my "day job" work, and even I sometimes can't tell very easily whether or not the problem can be solved easily with the right approach. Sometimes I've found it's simpler to just list all possibilities rather than try to determine a clever non-counting approach. If it's no more than $20$ or $30,$ then this is often the quickest approach (for me, at least); and if it becomes clear that there will be too many to reasonably list all of them, then sometimes by attempting to list all of them, you'll gain some insight as to "how to count without counting".

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks a lot, this is exactly what I was looking for $\endgroup$
    – Michael
    Oct 18 '20 at 14:48

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