# 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.