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,2

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.

Links

Table of n, a(n) for n=2..57.

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 +....

Example

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).

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 *)

Crossrefs

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

Sequence in context: A152195 A133156 A207538 * A127529 A091977 A112829

Adjacent sequences: A348866 A348867 A348868 * A348870 A348871 A348872

Keyword

nonn,tabf

Author

R. J. Mathar, Nov 02 2021

Status

approved