A162986 Number of Dyck paths with no UUU's and no DDD's of semilength n and having k UD's starting at level 0 (i.e., hills); (0 <= k <= n; U=(1,1), D=(1,-1)).

1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 2, 3, 0, 1, 4, 5, 3, 4, 0, 1, 8, 10, 9, 4, 5, 0, 1, 17, 21, 18, 14, 5, 6, 0, 1, 37, 46, 40, 28, 20, 6, 7, 0, 1, 82, 102, 90, 66, 40, 27, 7, 8, 0, 1, 185, 230, 204, 152, 100, 54, 35, 8, 9, 0, 1, 423, 526, 469, 353, 235, 143, 70, 44, 9, 10, 0, 1, 978, 1216

Offset: 0

Author

Emeric Deutsch, Oct 11 2009

Keywords

• nonn
• tabl

Comments

T is the convolution triangle based on T(n,0) = A004148(n-1) (n >= 1). - Peter Luschny, Oct 19 2022

Examples

			T(5,2)=3 because we have (UD)(UD)UUDUDD, (UD)UUDUDD(UD), and UUDUDD(UD)(UD) (the hills are placed between parentheses).
Triangle starts:
  1;
  0, 1;
  1, 0, 1;
  1, 2, 0, 1;
  2, 2, 3, 0, 1;
  4, 5, 3, 4, 0, 1;
		

Crossrefs

Cf. A004148, A162987.

Programs

Maple

g := ((1-z-z^2-sqrt(1-2*z-z^2-2*z^3+z^4))*1/2)/z^3: G := 1/(1-t*z-z^2-z^3*g): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 12 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 12 do seq(coeff(P[n], t, j), j = 0 .. n) end do; # yields sequence in triangular form
# Alternative based on a modified form of A004148:
# Uses function PMatrix from A357368. Adds column 1,0,0,0,... to the left.
M004148 := n -> `if`(n<3, 2-n, hypergeom([(2-n)/2, (3-n)/2, (3-n)/2, (4-n)/2], [2, 2-n, 3-n], 16)):
PMatrix(10, n -> simplify(M004148(n))); # Peter Luschny, Oct 19 2022

Formula

G(t,z) = 1/(1 - tz - z^2 - z^3*g), where g = 1 + zg + z^2*g + z^3*g^2.

Sum of entries in row n = A004148(n+1) (the secondary structure numbers).

T(n,0) = A004148(n-1) (n>=1).

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