Homework Help: Combinatoric problem

Tags:
1. Feb 1, 2016

David Waiter

We have a square grid. In how many ways we get to the point [20,30], if we can not get points [5,5], [15,10] [15,10] [17,23]? The starting point is [0,0], we can only move up and to the right. Thanks

My solutions:
$$\binom{50}{20} - \binom{10}{5}\binom{40}{15} - \binom{25}{10}\binom{25}{10} -\binom{25}{15}\binom{25}{5}-\binom{40}{17}\binom{10}{3}$$

2. Feb 1, 2016

Staff: Mentor

I moved the thread to the homework forum.

You are subtracting some paths more than once, e. g. every path that passes both through [5,5] and [15,10]. One [15,10] should be [10,15] I guess?

3. Feb 1, 2016

David Waiter

Yes, I use the principle of inclusion and exclusion

4. Feb 1, 2016

Staff: Mentor

So where do you consider the double-counting I mentioned?

5. Feb 1, 2016

Ray Vickson

You have included [15,10] twice in your list of forbidden points. What did you really mean?

6. Feb 1, 2016

haruspex

The principle of inclusion and exclusion leads to expressions with both plus and minus signs, usually alternating. This is because you subtract out all the cases ruled out by each single criterion, then add back all that you have subtracted twice over because they were ruled out by two criteria, then add back in all that you've added back in too often because they were ruled out by three criteria, and so on.