login
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.
3

%I #15 Jul 03 2024 12:46:33

%S 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,

%T 417,428,429,1,128,610,1094,1341,1416,1429,1430,1,256,1597,3281,4334,

%U 4744,4846,4861,4862,1,512,4181,9842,14041,16016,16645,16778,16795

%N 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.

%C 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

%H Vince White, <a href="https://digitalcommons.georgiasouthern.edu/etd/2799">Enumeration of Lattice Paths with Restrictions</a>, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.

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

%e Rows start:

%e 1;

%e 1,2;

%e 1,4,5;

%e 1,8,13,14;

%e 1,16,34,41,42;

%e ...

%e 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.

%Y Cf. A000108, A079214, A080934, A080936.

%K nonn,tabl

%O 1,3

%A _Henry Bottomley_, Feb 25 2003