A191319 -id:A191319 - cp's OEIS frontend

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

Emeric Deutsch, Jun 01 2011

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

			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;

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

Cf. A001405, A001859, A191319.

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

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.

A191399 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths of semilength n having k peak plateaux.

Original entry on oeis.org

1, 1, 2, 3, 5, 1, 8, 2, 13, 7, 21, 14, 34, 35, 1, 55, 68, 3, 89, 149, 14, 144, 282, 36, 233, 576, 114, 1, 377, 1068, 267, 4, 610, 2088, 711, 23, 987, 3810, 1566, 72, 1597, 7229, 3771, 272, 1, 2584, 13024, 7953, 744, 5, 4181, 24179, 17922, 2304, 34, 6765, 43114, 36594, 5780, 125

Offset: 0

Emeric Deutsch, Jun 05 2011

A dispersed Dyck paths of semilength n is a Motzkin path of length n with no (1,0)-steps at positive heights. A peak plateau is a run of consecutive peaks that is preceded by an upstep and followed by a down step; a peak consists of an upstep followed by a downstep.
Row n has 1+floor(n/4) entries.
Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).
T(n,0) = A000045(n+1) (Fibonacci numbers).
Sum_{k>=0} k*T(n,k) = A191319(n-2).

			T(8,2)=1 because we have (UUDD)(UUDD), where U=(1,1) and D=(1,-1) (the peak plateaux are shown between parentheses).
Triangle starts:
   1;
   1;
   2;
   3;
   5,  1;
   8,  2;
  13,  7;
  21, 14;
  34, 35,  1;

Cf. A000045, A001405, A191319.

eq := (t*z^4-z^4-2*z^3+z^2+2*z-1)*G*(1+z*G)+1-z^2 = 0: g := RootOf(eq, G): Gser := simplify(series(g, z = 0, 23)): for n from 0 to 19 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 19 do seq(coeff(P[n], t, k), k = 0 .. floor((1/4)*n)) end do; # yields sequence in triangular form

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula