2
$\begingroup$

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<b<c<n,x<y<z<k$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – paulinho
    May 29, 2020 at 19:13
  • $\begingroup$ Near duplicate: math.stackexchange.com/questions/2833857/… $\endgroup$ May 29, 2020 at 20:07

1 Answer 1

2
$\begingroup$

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)$$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .