+0

# PL5 Math Question 22

-1
275
5

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

#1
+12

Using only the paths and the indicated directions, how many different routes are there from A to J? $$\text{There are \mathbf{22} routes from A to J:} \\ \begin{array}{rl} 1 & \text{path of length } 3 \\ 6 & \text{paths of length } 4 \\ 10 & \text{paths of length } 5 \\ 5 & \text{paths of length } 6 \\ \end{array}$$ Nov 23, 2018

#1
+12

Using only the paths and the indicated directions, how many different routes are there from A to J? $$\text{There are \mathbf{22} routes from A to J:} \\ \begin{array}{rl} 1 & \text{path of length } 3 \\ 6 & \text{paths of length } 4 \\ 10 & \text{paths of length } 5 \\ 5 & \text{paths of length } 6 \\ \end{array}$$ heureka Nov 23, 2018
#5
0

Nice! That's a smart way!

dgfgrafgdfge111  Nov 26, 2018
#2
+1

Is there some "formula" for computing this, heureka???   Nov 23, 2018
#3
+2

There has to be! Maybe combinations!

tertre  Nov 23, 2018
#4
+9

Hello CPhill !

My attempt:

EXAMPLE
Triangle starts

1

1    2

1    4    6

1    6   16   22

1    8   30   68   90

1   10   48  146  304  394

1   12   70  264  714 1412 1806

A033877:
Triangular array read by rows associated with Schroeder numbers:
T(1,k) = 1;
T(n,k) = 0, if k T(n,k) = T(n,k-1) + T(n-1,k-1) + T(n-1,k).
1,
1, 2,
1, 4, 6,
1, 6, 16, 22,
1, 8, 30, 68, 90,
1, 10, 48, 146, 304, 394,
1, 12, 70, 264, 714, 1412, 1806,
1, 14, 96, 430, 1408, 3534, 6752, 8558,
1, 16, 126, 652, 2490, 7432, 17718, 33028, 41586,
1, 18, 160, 938, 4080, 14002, 39152, 89898, 164512, 206098

Note that for the terms T(n,k) of this triangle n indicates the column and k the row.

Consider a Pascal triangle variant where T(n, k) = T(n, k-1) + T(n-1, k-1) + T(n-1, k), i.e.,
the order of performing the calculation must go from left to right (A033877).
This sequence is the rightmost diagonal.

Triangle begins:

1;

1,  2;

1,  4,  6;

1,  6, 16, 22;

1,  8, 30, 68, 90;

(End)

A006318:
Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).
1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738,
142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926,
3236724317174, 17518619320890, 95149655201962, 518431875418926,
2832923350929742, 15521467648875090

Formula Large Schröder numbers:
$$\text{For n > 0 ,  \\ \displaystyle a(n) = \left(\dfrac{1}{n}\right)* \sum \limits_{k=0}^n \Big(2^k*C(n, k)*C(n, k-1) \Big)  .}$$

Source: https://oeis.org/A006318

The routes from A to J:

$$n=3:$$

$$\begin{array}{|rcll|} \hline a(3) &=& \dfrac13 * \Big( 2^0 * C(3,0) * C(3,-1) \\ && + 2^1 * C(3,1) * C(3,0) \\ && + 2^2 * C(3,2) * C(3,1) \\ && + 2^3 * C(3,3) * C(3,2) \Big) \\ a(3) &=& \dfrac13 * \Big( 1*1*0+ 2 * 3 * 1 + 4 * 3 * 3 + 8 * 1 * 3 \Big) \\ a(3) &=& \dfrac13 * \left( 0 + 6 + 36 + 24 \right) \\ \mathbf{a(3)} & \mathbf{=} & \mathbf{22} \\ \hline \end{array}$$ heureka  Nov 26, 2018