A080935 Triangle read by rows of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

1, 1, 2, 1, 4, 5, 1, 8, 13, 14, 1, 16, 34, 41, 42, 1, 32, 89, 122, 131, 132, 1, 64, 233, 365, 417, 428, 429, 1, 128, 610, 1094, 1341, 1416, 1429, 1430, 1, 256, 1597, 3281, 4334, 4744, 4846, 4861, 4862, 1, 512, 4181, 9842, 14041, 16016, 16645, 16778, 16795

Offset

1,3

Comments

T(n,k) is the number of different out-stack sequences of n elements to be pushed into a stack of size k. E.g. T(3,2) = 4 since the 4 possible out-stack sequences are 123, 132, 213, 231; 321 is not allowed since it requires a stack of size 3. - Jianing Song, Oct 28 2021

Links

Table of n, a(n) for n=1..54.

Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.

Formula

For 1<=k<=n, T(n, k) =A080934(n, k) =T(n, k-1)+A080936(n, k).

Example

Rows start:
  1;
  1,2;
  1,4,5;
  1,8,13,14;
  1,16,34,41,42;
  ...
T(3,2)=4 since the paths of length 2*3 (7 points) with all values less than or equal to 2 can take the routes 0101010, 0101210, 0121010 or 0121210, but not 0123210.

Crossrefs

Cf. A000108, A079214, A080934, A080936.

Sequence in context: A211561 A134248 A248670 * A362926 A102661 A121574

Adjacent sequences: A080932 A080933 A080934 * A080936 A080937 A080938

Keyword

nonn,tabl

Author

Henry Bottomley, Feb 25 2003

Status

approved