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

Author

Henry Bottomley, Feb 25 2003

Keywords

• nonn
• tabl

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000108, A079214, A080934, A080936.

Formula

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