0

Rectangular grid of given dimension

I was asked to find the no. of ways to get from (0,0) to (8,8) with the 4 points of the shaded box unpassable, aka I can't use the 4 points namely (3,3)(4,4)(3,4)(4,3) while on my way to (8,8). Right and up movements.

I know it is something like a pascal triangle and worked out the solution of 4050 ways.

May I know if there are any faster means using permutation formula?

Thank you in advance.

bearbearsocute
  • 23
  • It might be faster in a spreadsheet where you can copy right and down and let it do the arithmetic, but otherwise this looks like the best approach. – Ross Millikan Mar 02 '20 at 04:54
  • There are infinitely many ways to get from $(0,0)$ to $(8,8)$. From the numbers you've written down, it seems that you're looking for the number of ways to get from $(0,0)$ to $(8,8)$ with steps upward and to the right? – joriki Mar 02 '20 at 04:56
  • yes only upwards and right movements – bearbearsocute Mar 02 '20 at 04:57
  • @RossMillikan: It depends on your definition of "best" – I'd prefer doing an inclusion–exclusion calculation to setting up a large spreadsheet any time :-) – joriki Mar 02 '20 at 05:25

1 Answers1

1

Update: This answer is unnecessarily complicated for this case, as you can see from Gerry Myerson’s comment and the simpler calculation in the comment underneath. I’m leaving this here nevertheless since it shows how to do the calculation in the general case when this simplification is not available.

You can do this using inclusion–exclusion. There are $\binom{m+n}m$ ways to go from $(0,0)$ to $(m,n)$ with upward and rightward steps. You have four conditions corresponding to the four points not to be used. The number of ways to use some subset of the excluded points is the number of ways to go from $(0,0)$ to the bottom left point of the subset, then from that to the top right point of the subset, and then from that to $(8,8)$. Thus by inclusion–exclusion the number of admissible paths is

$$ \binom{8+8}8-\binom{3+3}3\binom{5+5}5-\binom{3+4}3\binom{5+4}5-\binom{4+3}4\binom{4+5}4-\binom{4+4}4\binom{4+4}4+\binom{3+3}3\binom{4+5}4+\binom{3+3}3\binom{5+4}5+2\binom{3+3}3\binom{4+4}4+\binom{3+4}3\binom{4+4}4+\binom{4+3}3\binom{4+4}4-\binom{3+3}3\binom{4+4}4-\binom{3+3}3\binom{4+4}4=12870 – 20\cdot252-35\cdot126-35\cdot126-70\cdot70+20\cdot126+20\cdot126+2\cdot20\cdot70+35\cdot70+35\cdot70-20\cdot70-20\cdot70=4050\;, $$

where the $2$ counts the two ways to get from $(3,3)$ to $(4,4)$ and the missing terms in the inclusion–exclusion sum are not included (i.e. excluded ;-) because there's no way to use both $(3,4)$ and $(4,3)$.

joriki
  • 238,052
  • 1
    Isn't it enough to just count the paths that use $A=(3,4)$ and the paths that use $B=(4,3)$, since any path that uses either $(3,3)$ or $(4,4)$ must also use $A$ or $B$? – Gerry Myerson Mar 02 '20 at 05:31
  • 1
    @GerryMyerson: Ah, quite right, thanks, what an unnecessary complication :-) So it's simply $\binom{8+8}8-2\binom{3+4}3\binom{5+4}5=12870-2\cdot35\cdot126=4050$; we don't even need inclusion–exclusion, since we can't use both $A$ and $B$. – joriki Mar 02 '20 at 05:38