Discrete Math Problem Please explain the answer Thanks Suppo

Discrete Math Problem, Please explain the answer! Thanks!

Suppose you have a standard (8-by-8) chessboard, and you place a marker on the bottom left square, which we\'ll call (1, 1). Your marker can now take single moves: either the marker can move one square to the right, or one square upward at any step. Thus, it will take 14 moves to get the marker to the upper right corner, which we\'ll call (8, 8).

1. How many distinct 14-move paths are there by which the marker can go from the bottom left corner to the upper right corner?
2. Suppose we want to avoid landing on the square (3, 3): that is, the square in the third row from the bottom and the third column from the left. How many distinct 14-move paths can get the marker from bottom left to upper right, subject to this constraint?
3. Suppose we want to avoid paths that land on just one of (3, 3) and (6, 6), but paths that land on neither or both of these squares are okay. Now how many paths are there from
bottom left to upper right corner?

Solution

(1).,,...

To get from (1,1) to (8,8), it takes 14 moves, and they must consist of some sequence involving
7 moves to the right and 7 moves up. So every path that works can be characterized by which 7,
out of the 14 moves, are upward. Thus, there are a total of
14C7 = 14! / (7! 7!)
= 14 * 13 * 12 * 11 * 10 * 9 * 8 / (7 * 6 * 5 * 4 * 3 * 2 * 1)
= 2 * 13 * 2 * 11 * 2 * 3
= 3,432 different paths (without restrictions).

(2),.....

The paths that pass through (3,3) have
exactly 2 out of the first 4 moves upward, and
exactly 5 out of the last 10 moves upward.
So there are
4C2 * 10C5 = [4! / (2! 2!)] [10! / (5! 5!)]
= 6 [10 * 9 * 8 * 7 * 6 / (5 * 4 * 3 * 2 * 1)]
= 6 * 2 * 9 * 2 * 7
= 1,512 paths that pass through (3,3).

That does, as we\'ve already determined, leave
3,432 - 1,512 = 1,920 paths that don\'t pass through (3,3).

(3).,,,,....

The situation with paths passing through (6,6) is equivalent, since any such path must have exactly 5 of the first 10 moves upward, and exactly 2 of the last 4 moves.

A path that passes through BOTH (3,3) and (6,6) must have
2 upward moves in the first 4,
3 upward moves in the middle 6, and
2 upward moves in the last 4,
so there are
4C2 * 6C3 * 4C2 = 6 * 20 * 6 = 720 paths that pass through both points.

This set is included among the total paths that pass through each. So there are
1,512 - 720 = 792 paths that pass through (3,3) but NOT through (6,6),
and the same number that pass through (6,6) but NOT through (3,3).

Those are the ones we want to exclude. So there are
3,432 - 2 (792)
= 3,432 - 1,584
= 1,848 paths that obey the restrictions:
they either pass through neither or both of (3,3) and (6,6)