Skip to main content
added 36 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

Here's an approach that uses a Pascal-type recursion. Impose Introduce a Cartesian coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of good paths to the terminal Ds at the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. ThenNow $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

Here's an approach that uses a Pascal-type recursion. Impose a coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of paths to the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Then $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

Here's an approach that uses a Pascal-type recursion. Introduce a Cartesian coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of good paths to the terminal Ds at the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Now $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

edited body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

Here's an approach that uses a Pascal-type recursion. Impose a coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of paths to the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Then $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+d_\ell}.$$$$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

Here's an approach that uses a Pascal-type recursion. Impose a coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of paths to the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Then $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+d_\ell}.$$The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

Here's an approach that uses a Pascal-type recursion. Impose a coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of paths to the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Then $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+\ell}.$$ The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}

Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

Here's an approach that uses a Pascal-type recursion. Impose a coordinate system with the initial D at the origin. Let $a_{i,j}$ be the number of paths to the border, starting from point $(i,j)$. We want to compute $a_{0,0}$. Then $a_{i,j}=1$ for the four terminal Ds and otherwise $$a_{i,j} = \sum_{\substack{k=\pm1,\ \ell=\pm1:\\|i|+|j|<|i+k|+|j+\ell|}} a_{i+k,j+d_\ell}.$$The resulting values are as follows:

\begin{matrix} & & & & && 1 \\ & & & & & 1 &3 &1 \\ & & & & 1 &2 &7 &2 &1 \\ & & & 1 &2 &4 &15 &4 &2 &1 \\ & & 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ 1 &3 &7 &15 &31 &63 &\color{blue}{252} &63 &31 &15 &7 &3 &1 \\ & 1 &2 &4 &8 &16 &63 &16 &8 &4 &2 &1 \\ && 1 &2 &4 &8 &31 &8 &4 &2 &1 \\ & && 1 &2 &4 &15 &4 &2 &1 \\ & & && 1 &2 &7 &2 &1 \\ & & & && 1 &3 &1 \\ & & & & && 1 \end{matrix}