How many paths are there from one vertex of a subdivided triangle to another?

Question

Other than counting, is there any shortcut to solve this?

Using only the paths and the indicated directions, how many different routes are there from $A$ to $J$?

My answer is $22$.

Let me suggest that you improve this problem (and eliminate exhaustive solutions) by generalizing to equilateral triangles of arbitrary number, $k$, of levels. — David G. Stork, Apr 30 '20 at 01:41
This sum is $, _2F_1(-n,n+1;2;-1)$, where $F$ is the HyperGeometric function. Here's a table: $${ {0, 1}, {1, 2} , {2, 6 } , {3, 22 }, { 4, 90 }, {5 , 394 }, {6, 1806 }, {7, 8558 }, {8, 41586 } }$$ — David G. Stork, Apr 30 '20 at 02:13
@DavidG.Stork: Can you refer me to something that connects the difference equation to the HyperGeometric function please? — copper.hat, Apr 30 '20 at 03:30

score 5 · Answer 1 · answered Apr 30 '20 at 01:32

5

Put a number on every node, starting with a $1$ on point $A$. The numbers you put on node is how many ways to get to this particular node. It is the sum of every nodes that lead to it.

        1
      2   1
    6   4   1
 22  16   6   1

You are right, there are $22$ ways to get from $A$ to $J$.

answered Apr 30 '20 at 01:32

Alain Remillard

3,625

Isn't this "counting"—the method the OP explicitly excluded? – David G. Stork Apr 30 '20 at 01:45
1

@DavidG.Stork I considered counting to be exhaustive, i.e. finding the exact $22$ ways. But if it is OP's ways, I'll delete my answer. – Alain Remillard Apr 30 '20 at 01:51
I'll leave that up to the OP. Moreover, it seems that @bof has a functional solution. – David G. Stork Apr 30 '20 at 01:55

score 4 · Accepted Answer · answered Apr 30 '20 at 04:05

Building upon a prior comment answer, we have:

$$\sum\limits_{k=0}^n C_k {n+k \choose 2k} = \, _2F_1(-n,n+1;2;-1)$$

where $C_n$ is the $n$th Catalan number and $F$ is the HyperGeometric function.

Here's a table:

$$\left( \begin{array}{cc} 0 & 1 \\ 1 & 2 \\ 2 & 6 \\ 3 & 22 \\ 4 & 90 \\ 5 & 394 \\ 6 & 1806 \\ 7 & 8558 \\ 8 & 41586 \\ \end{array} \right)$$

score 4 · Answer 3 · answered Apr 30 '20 at 04:36

The numbers given by @David G. Stork in comments and answers are the Schröder numbers $S_n$

Quoting the Wikipedia page they

"describe the number of lattice paths from the southwest corner $(0,0)$ of an $(n \times n)$ grid to the northeast corner $(n,n)$ using only single steps north, $(0,1)$; northeast, $(1,1)$ or east, $(1,0)$ that do not rise above the $\text{SW-NE}$ diagonal."

You could find them in sequence $A006318$ in $OEIS$.

Thanks... didn't know that! (+1). – David G. Stork Apr 30 '20 at 04:40 — David G. Stork, Apr 30 '20 at 04:40

How many paths are there from one vertex of a subdivided triangle to another?

3 Answers3