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

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, 1374, 1364, 702, 160, 10, 3562, 3551, 1975, 564, 60, 1, 9360, 9348, 5484, 1840, 280, 12, 24871, 24858, 15144, 5716, 1125, 84, 1, 66706, 66692, 41768, 17208, 4102, 448, 14

Offset: 2

Author

R. J. Mathar, Nov 02 2021

Keywords

• nonn
• tabf

Comments

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.

Examples

			The triangle starts
      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
   1374  1364   702   160   10
   3562  3551  1975   564   60   1
   9360  9348  5484  1840  280  12
  24871 24858 15144  5716 1125  84  1
  66706 66692 41768 17208 4102 448 14
T(4,2)=1 counts udud.
T(5,1)=8 counts uuddh uudhd uuhdd udhhh uhudd uhdhh uhhdh uhhhd.
T(5,2)=4 counts ududh uduhd udhud uhdud.
T(2n,n) = 1 counts udududu... (ud repeated n times).
		

Crossrefs

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

Programs

Maple

A348869 := proc(n,c)
    local g,x,y ;
    g := add( A086615(i)*x^(i+2),i=0..n) ;
    1/(1-y*g) ;
    coeftayl(%,x=0,n) ;
    coeftayl(%,y=0,c) ;
end proc:
seq(seq( A348869(n,c),c=1..n/2),n=2..10) ;

Mathematica

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[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}]&];
Table[T[n, c], {n, 2, 15}, {c, 1, n/2}] // Flatten (* Jean-François Alcover, Aug 12 2023, after Maple code *)

Formula

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