A191318 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths of length n (i.e., Motzkin paths of length n with no (1,0) steps at positive heights) having pyramid weight equal to k.

1, 1, 1, 1, 1, 2, 1, 3, 2, 1, 4, 5, 1, 5, 10, 4, 1, 6, 16, 12, 1, 7, 24, 30, 8, 1, 8, 33, 56, 28, 1, 9, 44, 98, 84, 16, 1, 10, 56, 152, 179, 64, 1, 11, 70, 228, 358, 224, 32, 1, 12, 85, 320, 618, 536, 144, 1, 13, 102, 440, 1030, 1206, 576, 64, 1, 14, 120, 580, 1580, 2292, 1528, 320, 1, 15, 140, 754, 2370, 4202, 3820, 1440, 128

Offset

0,6

Comments

A pyramid in a dispersed Dyck path is a factor of the form U^h D^h, h being the height of the pyramid and U=(1,1), D=(1,-1). A pyramid in a dispersed Dyck path w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The pyramid weight of a dispersed Dyck path is the sum of the heights of its maximal pyramids.

Row n has 1 + floor(n/2) entries.

Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).

Links

Table of n, a(n) for n=0..80.

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

Formula

T(n,0) = 1;

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

T(n,2) = A001859(n-3) (n>=4).

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

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

Example

T(6,2)=10 because we have HH(UD)(UD), HH(UUDD), H(UD)H(UD), H(UD)(UD)H, H(UUDD)H, (UD)HH(UD), (UD)H(UD)H, (UD)(UD)HH, (UUDD)HH, and U(UD)(UD)D, where U=(1,1), D=(1,-1), H=(1,0); the maximal pyramids are shown between parentheses.
Triangle starts:
  1;
  1;
  1,  1;
  1,  2;
  1,  3,  2;
  1,  4,  5;
  1,  5, 10,  4;
  1,  6, 16, 12;
  1,  7, 24, 30,  8;

Maple

a := (z-1)*(2*t*z^2+z-1): c := -1+t*z^2: eq := a*z*G^2+a*G+c: f := RootOf(eq, G): fser := simplify(series(f, z = 0, 20)): for n from 0 to 16 do P[n] := sort(expand(coeff(fser, z, n))) end do: for n from 0 to 16 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

Crossrefs

Cf. A001405, A001859, A191319.

Sequence in context: A049280 A108786 A008315 * A341315 A293600 A191395

Adjacent sequences: A191315 A191316 A191317 * A191319 A191320 A191321

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 01 2011

Status

approved