login
Triangle T(n,c) counting Motzkin Paths of length n with c sections starting with an up-step at level 0.
3

%I #8 Aug 12 2023 04:38:04

%S 1,2,4,1,8,4,17,12,1,38,32,6,89,82,24,1,216,208,80,8,539,530,243,40,1,

%T 1374,1364,702,160,10,3562,3551,1975,564,60,1,9360,9348,5484,1840,280,

%U 12,24871,24858,15144,5716,1125,84,1,66706,66692,41768,17208,4102,448,14

%N Triangle T(n,c) counting Motzkin Paths of length n with c sections starting with an up-step at level 0.

%C This is a Sequence Transform of A086615. A086615(n-2) counts the Motzkin Paths of length n which start with an u-step, return to the horizontal level once with a d-step and remain there (with any number of trailing h-steps). These might be called single-return M-Paths. The path of length n=2 is ud. The paths of length 3 are udh, uhd. The Paths of length 4 are uudd, udhh, uhdh and uhhd. A Motzkin Path can be chopped into subpaths of that type by splitting it at each u-step that starts from the horizontal line. [The exception is the path that consists entirely of h-steps.] The triangle of the Sequence Transform T(n,c) counts how many Motzkin Paths of length n which start with an u-step are concatenations of c of these single-return M-paths. T(n,1) are the single-return M-Paths. Row sums and column 1 are an INVERT transform pair.

%F G.f.: 1/(1-y*g086615(x)) where g086615(x) = x^2 +2*x^3 +4*x^4 +8*x^5 +17*x^6 +....

%e The triangle starts

%e 1

%e 2

%e 4 1

%e 8 4

%e 17 12 1

%e 38 32 6

%e 89 82 24 1

%e 216 208 80 8

%e 539 530 243 40 1

%e 1374 1364 702 160 10

%e 3562 3551 1975 564 60 1

%e 9360 9348 5484 1840 280 12

%e 24871 24858 15144 5716 1125 84 1

%e 66706 66692 41768 17208 4102 448 14

%e T(4,2)=1 counts udud.

%e T(5,1)=8 counts uuddh uudhd uuhdd udhhh uhudd uhdhh uhhdh uhhhd.

%e T(5,2)=4 counts ududh uduhd udhud uhdud.

%e T(2n,n) = 1 counts udududu... (ud repeated n times).

%p A348869 := proc(n,c)

%p local g,x,y ;

%p g := add( A086615(i)*x^(i+2),i=0..n) ;

%p 1/(1-y*g) ;

%p coeftayl(%,x=0,n) ;

%p coeftayl(%,y=0,c) ;

%p end proc:

%p seq(seq( A348869(n,c),c=1..n/2),n=2..10) ;

%t b[n_] := b[n] = If[n <= 3, 2^n, (3*(n+1)*b[n-1] + (n-4)*b[n-2] - 3*(n-1)*b[n-3])/(n+2)];

%t T[n_, c_] := Module[{g, x, y}, g = Sum[b[i]*x^(i+2), {i, 0, n}]; 1/(1-y*g) // SeriesCoefficient[#, {x, 0, n}]& // SeriesCoefficient[#, {y, 0, c}]&];

%t Table[T[n, c], {n, 2, 15}, {c, 1, n/2}] // Flatten (* _Jean-François Alcover_, Aug 12 2023, after Maple code *)

%Y Cf. A086615 (column c=1), A002026 (row sums)

%K nonn,tabf

%O 2,2

%A _R. J. Mathar_, Nov 02 2021