Question
How many paths from point A to point B with length 8 exists that that have even number of negative signs?
path example
my main problem is that i can't find a good way for counting paths.also the question is different from most "number of paths on grid" that I've solved previously.
the answer keys says the answer is $\frac {1}{2} {8 \choose 4}$.
It is clear from just the shape of the grid that every path of length 8 must consist of exactly 4 steps up and 4 steps to the right, with no steps down or left. So, by standard techniques the total number of paths is $\binom84$.
Now, the answer key claims that exactly half of those paths have an even number of minuses. This suggests that there is probably a clever way to pair up the paths such that each odd-minuses path corresponds to an even-minuses path and vice versa.
Notice that except for the nodes on the diagonal, each node has the opposite sign of the one that's directly opposite from it across the diagonal.
So if we take any 8-step path from A to B and flip it around the diagonal, all off-diagonal nodes in the path change from
+to-or vice versa. Unfortunately that doesn't help us, because the number of off-diagonal nodes on a path can be either odd or even.However, we can be a bit more clever. A node on the diagonal can only be reached by an even number of steps from A, so the number of nodes we meet before the first diagonal node after A (which may be B or something in between) is necessarily odd. And these are all, by construction, off-diagonal. So if we flip just that portion of the path, we're changing odd many nodes between
+and--- and repeating that operation gives us the original path back. So this gives us the hypothesized pairing between odd-minuses paths and even-minuses paths.