+937 Using only the paths and the indicated directions, how many different routes are there from A to J?
+26396 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}\)
+26396 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}\)
+26396 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} \)
