How many paths from A to B?

852 Views Asked by At

How many paths from A = lower left corner to B = upper right corner.

Do not take the dotted line paths and only move either right or up.

enter image description here


I am getting

$$\binom{20}{10} - \left [ \binom{9}{5}.\binom{10}{5} + \binom{14}{7}.\binom{5}{3} - \binom{9}{4}.\binom{4}{2}. \binom{5}{3}\right ]$$

Is this correct ?

1

There are 1 best solutions below

0
On BEST ANSWER

Constraints :

(1) going right or up and starting lower left and finishing upper right.

(2) going through the lower left "$\dots$".

(3) going through the upper right "$\vdots$".

Let :

$X$ = set of paths verifying (1).

$A$ = set of paths verifying (1) and (2). ($A\subset X$)

$B$ = set of paths verifying (1) and (3). ($B\subset X$)

$C$ = set of paths verifying (1) but not (2) and not (3). ($C = (A\cup B)^c = A^c \cap B^c \subset X$)

Then

$|C| = (A\cup B)^c \\= |X| - |A\cup B| \\= |X| - (|A| + |B| - |A\cap B|) \\= |X| - |A| - |B| + |A\cap B|$

Now we need to count. A path can be described as a word made out of the letters $u$ (up) and $r$ (right).

For X we have 10 u's and 10 r's for a total of 20 letters. So $|X| = 20!/(10! 10!)$.

Then $|A| = (9!/(4!5!))(10!/(5!5!))$

Then $|B| = (14!/(7!7!))(5!/(3!2!))$

Then $|A\cap B| = (9!/(4!5!))(4!/(2!2!))(5!/(3!2!))$

So I get

$|C| = 20!/(10! 10!) \\ -(9!/(4!5!))(10!/(5!5!)) \\- (14!/(7!7!))(5!/(3!2!)) \\+ (9!/(4!5!))(4!/(2!2!))(5!/(3!2!))$

(sorry for the typing mess)

Yes, I believe your answer is good.