+0  
 
-1
1580
5
avatar+936 

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

 

 Nov 22, 2018

Best Answer 

 #1
avatar+26364 
+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}\)

 

laugh

 Nov 23, 2018
 #1
avatar+26364 
+12
Best Answer

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}\)

 

laugh

heureka Nov 23, 2018
 #5
avatar+936 
0

Nice! That's a smart way!

dgfgrafgdfge111  Nov 26, 2018
 #2
avatar+128085 
+1

Is there some "formula" for computing this, heureka???

 

 

cool cool cool

 Nov 23, 2018
 #3
avatar+4609 
+2

There has to be! Maybe combinations!

tertre  Nov 23, 2018
 #4
avatar+26364 
+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.

Source: https://oeis.org/search?q=A033877


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} \)

 

laugh

heureka  Nov 26, 2018

3 Online Users

avatar
avatar