+0  
 
0
52
5
avatar+133 

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

 

dgfgrafgdfge111  Nov 22, 2018

Best Answer 

 #1
avatar+20578 
+8

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
 #1
avatar+20578 
+8
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+133 
+1

Nice! That's a smart way!

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

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

 

 

cool cool cool

CPhill  Nov 23, 2018
 #3
avatar+3423 
+2

There has to be! Maybe combinations!

tertre  Nov 23, 2018
 #4
avatar+20578 
+5

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

11 Online Users

avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.