# Number of routes not passing in 3 points

Given a coordinates system in which you can move in unit steps right or up, how many possible routes are there from $$(0, 0)$$ to $$(k, n)$$ while also not passing in any of the points $$(z,c), (y,b), (x,a)$$?

$$a

all parameters are in $$\mathbb{N}$$.

I managed to solve it with inclusion-exclusion but the solution is extremely ugly. Looking for a hint for a more elegant solution.

• Have you tried simplifying the solution? If it turns out there is a simpler form to the solution there might be an elegant solution, but if for example there is no closed form for the solution, then there might be less hope. May 29, 2020 at 19:13
• Near duplicate: math.stackexchange.com/questions/2833857/… May 29, 2020 at 20:07

# Overview

The number of paths of east and north steps ($${\bf E}$$ and $${\bf N}$$) on the grid without constraints is $$T = {k+n \choose k}$$. You can envision this as $$k+n$$ slots (steps) into which you place $$k$$ $${\bf E}$$ steps, where the rest must be $${\bf N}$$.

Consider the first forbidden point, at $$(x,a)$$, which we call $$A$$. The number of the total paths that pass through $$A$$ is the product of the number of legal paths from $$(0,0)$$ to $$(x,a)$$ times the number of legal paths from $$(x,a)$$ to the endpoint $$(k,n)$$. Those numbers, multiplied, are $$N(A) = {a+x \choose a}{(k-x)+(n-a) \choose k-x}$$.

So you subtract these from the total number to find the total number of paths that do not pass through the first forbidden point.

A similar calculation holds for the second and the third forbidden points, $$B$$ and $$C$$.

However, for the full problem you must consider paths that don't go through multiple such points.

This is a straightforward matter of counting all the path segments that do or do not pass through the points, using the general mathematical formula above. This is the technique of inclusion/exclusion. Call the total number of paths $$T$$ (as above) and the number passing through $$A$$ as $$N(A)$$, and likewise for point $$B$$ and point $$C$$. Then the total number of ways that avoid $$A$$ and $$B$$ and $$C$$ is:

$$T - N(A) - N(B) -N(C) + N(A \cap B) + N(A \cap C) + N(B \cap C) - N(A \cap B \cap C)$$

• This is exactly how I solved it but you have to use inclusion exclusion don't you? Or is there another way? May 29, 2020 at 19:35
• Yep. Inclusion/exclusion is what I meant by my last sentence. Doesn't seem too ugly... May 29, 2020 at 19:45