A190167 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n having a total of k (1,0)-steps at levels 1,3,5,... .

1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 2, 1, 4, 6, 4, 2, 1, 7, 12, 10, 5, 2, 1, 12, 24, 23, 14, 6, 2, 1, 21, 48, 52, 36, 18, 7, 2, 1, 38, 96, 115, 90, 51, 22, 8, 2, 1, 70, 193, 254, 217, 138, 68, 26, 9, 2, 1, 130, 388, 559, 522, 358, 196, 87, 30, 10, 2, 1, 243, 782, 1220, 1240, 926, 542, 264, 108, 34, 11, 2, 1

Offset

0,7

Comments

Row n has n-1 entries (n>=3).

Sum of entries in row n is A004148(n) (the RNA secondary structure numbers).

T(n,0) = A190168(n).

Sum_{k>=0} k*T(n,k) = A190169(n).

The trivariate g.f. H(t,s,z), where t (s) marks (1,0)-steps at even (odd) levels and z marks length, satisfies z^2(1-tz+z^2)H^2-(1-tz+z^2)(1-sz+z^2)H+1-sz+z^2=0.

Links

Alois P. Heinz, Rows n = 0..200, flattened

Formula

G.f.: G(s,z) satisfies the equation z^2*(1-z+z^2)*G^2-(1-z+z^2)*(1-s*z+z^2)*G+1-s*z+z^2 = 0.

Example

T(5,2)=2 because we have huh'h'd and uh'h'dh, where u=(1,1), h=(1,0), d=(1,-1) (the odd-level h-steps are marked).
Triangle starts:
  1;
  1;
  1;
  1,  1;
  1,  2,  1;
  2,  3,  2, 1;
  4,  6,  4, 2, 1;
  7, 12, 10, 5, 2, 1;
  ...

Maple

eq:=z^2*(1-z+z^2)*G^2-(1-z+z^2)*(1-s*z+z^2)*G+1-s*z+z^2 = 0: g:= RootOf(eq, G): Gser:= simplify(series(g, z = 0, 17)): for n from 0 to 13 do P[n] := sort(expand(coeff(Gser, z, n))) end do: 1; 1; for n from 0 to 13 do seq(coeff(P[n], s, k), k = 0 .. n-2) end do; # yields sequence in triangular form
# Alternative:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y, false)*`if`(y::odd, z, 1)+
     `if`(t, 0, b(x-1, y-1, false))+b(x-1, y+1, true))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, false)):
seq(T(n), n=0..13);  # Alois P. Heinz, Feb 01 2026

Mathematica

Flatten@CoefficientList[CoefficientList[Nest[1+z (z-s+# (1-z+(1-z+z^2) (-z+s+z #))) &, 1+O[z], 15], z], s] (* Oliver Seipel, Feb 01 2026 *)

Crossrefs

Cf. A004148, A190164, A190168, A190169.

Sequence in context: A128979 A332509 A336157 * A339010 A332842 A352696

Adjacent sequences: A190164 A190165 A190166 * A190168 A190169 A190170

Keyword

nonn,tabf

Author

Emeric Deutsch, May 06 2011

Status

approved