A091866 -id:A091866 - cp's OEIS frontend

A166301 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having pyramid weight k.

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 1, 2, 5, 0, 0, 0, 0, 1, 2, 6, 8, 0, 0, 0, 0, 1, 2, 8, 13, 13, 0, 0, 0, 0, 1, 2, 10, 19, 29, 21, 0, 0, 0, 0, 1, 2, 12, 25, 51, 60, 34, 0, 0, 0, 0, 1, 2, 14, 31, 78, 120, 122, 55, 0, 0, 0, 0, 1, 2, 16, 37, 110, 200, 282, 241

Offset: 0

Emeric Deutsch, Nov 07 2009

A pyramid in a Dyck word (path) is a factor of the form U^h D^h, h being the height of the pyramid. A pyramid in a Dyck word 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 Dyck path (word) is the sum of the heights of its maximal pyramids.
Sum of entries in row n is the secondary structure number A004148(n-1) (n>=2).
T(n,n)=A000045(n-1) (n>=1; the Fibonacci numbers).
Sum(k*T(n,k), k>=0)=A166302(n).

			T(6,5)=2 because we have U(UUDD)(UUUDDD)D and U(UUUDDD)(UUDD)D (the maximal pyramids are shown between parentheses).
Triangle starts:
1;
0,0;
0,0,1;
0,0,0,1;
0,0,0,0,2;
0,0,0,0,1,3;
0,0,0,0,1,2,5;
0,0,0,0,1,2,6,8;

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

Cf. A004148, A166302, A000045, A091866.

eq := G = 1+z*G*(G-1+t^2*z*(1-z)/(1-t*z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 12 do P[n] := sort(expand(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

G.f.: G=G(t,z) satisfies G = 1 + zG[G - 1 + tz - tz(1 - t)/(1 - tz)].

A247285 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n (n>=1) having k (0<=k<=n-1) upper interactions.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 7, 1, 1, 7, 19, 14, 1, 1, 9, 36, 59, 26, 1, 1, 11, 58, 150, 162, 46, 1, 1, 13, 85, 300, 543, 408, 79, 1, 1, 15, 117, 523, 1335, 1771, 966, 133, 1, 1, 17, 154, 833, 2747, 5303, 5335, 2184, 221, 1, 1, 19, 196, 1244, 5031, 12792, 19272, 15099, 4767, 364, 1

Offset: 1

Emeric Deutsch, Sep 11 2014

An upper interaction in a Dyck path is an occurrence of a string d^k u^k for some k>=1; here u = (1,1) and d = (1,-1). For example, the Dyck path uu[d(du)u]dd has 2 upper interactions, shown between parentheses.
Number of entries in row n is n.
Sum of entries in row n is the Catalan number A000108(n).
Sum(k*T(n,k), k>=0) = A172061(n-2).
The statistic "number of lower interactions", mentioned in the Le Borgne reference is basically identical with the statistic "pyramid weight" of the Denise and Simion reference (see A091866 and the bottom of p. 8 of the Le Borgne reference).
T(n+1,n) = A001924(n) for n>=1. - Alois P. Heinz, Sep 11 2014

			Row 3 is 1,3,1. Indeed, the number of upper interactions in uuuddd, uududd, uuddud, uduudd, and ududud are 0, 1, 1, 1, and 2, respectively.
Triangle starts:
1;
1,1;
1,3,1;
1,5,7,1;
1,7,19,14,1;
1,9,36,59,26,1;

Alois P. Heinz, Rows n = 1..141, flattened
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
Y. Le Borgne, Counting upper interactions in Dyck paths, Sem. Lotharingien de Combinatoire, 54, 2006, Article B54f.

Cf. A000108, A001924, A172061, A091866.

q := u*t: s := ((1+t-2*q-sqrt((1-t)*(1-t-4*q+4*q^2)))*(1/2))/(t*(1-q)): Q := proc (x, n) options operator, arrow: product(1-q^k*x, k = 0 .. n-1) end proc: A := -t*add(((q-t)*s/(1-q))^n*q^(binomial(n+2, 2)-1)/(Q(q, n)*Q(q*t*s^2, n)), n = 0 .. 15)/add(((q-t)*s/(1-q))^n*q^binomial(n+2, 2)*(1-t*q^n*s)/(Q(q, n)*Q(q*t*s^2, n)*(1-q^n*s)*(1-q^(n+1)*s)), n = 0 .. 15): Aser := simplify(series(A, t = 0, 22)): for n to 16 do P[n] := sort(coeff(Aser, t, n)) end do: for n to 13 do seq(coeff(P[n], u, j), j = 0 .. n-1) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t, c) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, false, max(0, c-1))*
     `if`(c>0, z, 1)+b(x-1, y-1, true, 1+`if`(t, c, 0)))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n-1))(b(2*n, 0, false, 0)):
seq(T(n), n=1..15);  # Alois P. Heinz, Sep 11 2014

b[x_, y_, t_, c_] := b [x, y, t, c] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, False, Max[0, c-1]]*If[c>0, z, 1] + b[x-1, y-1, True, 1 + If[t, c, 0] ] ] ] ]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, n-1}]][b[2*n, 0, False, 0]]; Table[T[n], {n, 1, 25}] // Flatten (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

The g.f. A(t,u), where t marks semilength and u marks upper interactions, is given in Proposition 2 of the Le Borgne reference. It is extremely complex; the Maple program follows it (blindly), except that the infinite sums have been replaced by summations from n=0 to n=15.

A091977 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.

Original entry on oeis.org

1, 1, 2, 4, 1, 8, 5, 1, 16, 18, 7, 1, 32, 56, 34, 9, 1, 64, 160, 138, 55, 11, 1, 128, 432, 500, 275, 81, 13, 1, 256, 1120, 1672, 1205, 481, 112, 15, 1, 512, 2816, 5264, 4797, 2471, 770, 148, 17, 1, 1024, 6912, 15808, 17738, 11403, 4536, 1156, 189, 19, 1, 2048, 16640

Offset: 0

Emeric Deutsch, Mar 15 2004

A pyramid in a Dyck word (path) is a factor of the form u^h d^h, h being the height of the pyramid. A pyramid in a Dyck word 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 Dyck path (word) is the sum of the heights of its maximal pyramids. An exterior pair in a Dyck path is a pair consisting of a u and its matching d (when viewed as parentheses) which do not belong in any pyramid. Clearly, for a given Dyck path, the sum of its pyramid weight and the number of its exterior pairs is equal to the semilength of the path.
Triangle, with zeros omitted, given by (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ...) DELTA (0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 06 2012

			T(4,1)=5 because the Dyck paths of semilength 4 having 1 exterior pair are: ud(u)udud(d), (u)udud(d)ud, (u)ududud(d), (u)uduudd(d) and (u)uuuddud(d) [the u and d that form the unique exterior pair are shown between parentheses].
Triangle begins:
[1],
[1],
[2],
[4, 1],
[8, 5, 1],
[16, 18, 7, 1],
[32, 56, 34, 9, 1],
[64, 160, 138, 55, 11, 1],
[128, 432, 500, 275, 81, 13, 1]
Triangle (1,1,0,1,1,0,1,1,...) DELTA (0,0,1,0,0,1,0,0,1,...) begins :
1
1, 0
2, 0, 0
4, 1, 0, 0
8, 5, 1, 0, 0
16, 18, 7, 1, 0, 0
32, 56, 34, 9, 1, 0, 0
64, 160, 138, 55, 11, 1, 0, 0...- _Philippe Deléham_, Feb 06 2012

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

T(n, k)=A091866(n, n-k), T(n, 0)=2^(n-1) (n>0), T(n, 1)=A001793(n-2), row sums give the Catalan numbers (A000108).

Cf. A091866, A001793, A000108.

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

A094449 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having sum of pyramid heights equal to k.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 4, 2, 0, 0, 8, 13, 8, 5, 0, 0, 16, 42, 26, 20, 12, 0, 0, 32, 139, 85, 65, 48, 28, 0, 0, 64, 470, 286, 214, 156, 112, 64, 0, 0, 128, 1616, 982, 727, 517, 364, 256, 144, 0, 0, 256, 5632, 3420, 2518, 1772, 1214, 832, 576, 320, 0, 0, 512, 19852

Offset: 0

Emeric Deutsch, Jun 04 2004

A pyramid in a Dyck path is a factor of the form U^j D^j (j>0), starting at the x-axis. Here U=(1,1) and D=(1,-1). This definition differs from the one in A091866. Column k=0 is A082989. Row sums are the Catalan numbers (A000108).

			T(3,3)=4 because there are four Dyck paths of semilength 3 having 3 as sum of pyramid heights: (UD)(UUDD),(UUDD)(UD),(UD)(UD)(UD) and (UUUDDD) (the pyramids are shown between parentheses).
Triangle begins:
  [1];
  [0, 1];
  [0, 0, 2];
  [1, 0, 0, 4];
  [4, 2, 0, 0, 8];
  [13, 8, 5, 0, 0, 16];
  [42, 26, 20, 12, 0, 0, 32];

Cf. A082989, A000108.

C:=(1-sqrt(1-4*z))/2/z: G:=(1-t*z)*(1-z)/(1-2*t*z+t*z^2-z*C*(1-z)*(1-t*z)): Gserz:=simplify(series(G,z=0,16)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(coeff(Gserz,z^n)) od: seq([subs(t=0,P[n]),seq(coeff(P[n],t^k),k=1..n)],n=0..14);

G.f.: G(t, z) = (1-t*z)*(1-z)/(1-2*t*z+t*z^2-z*(1-z)*(1-t*z)*C), where C = (1-sqrt(1-4*z))/(2*z) is the Catalan function.

A114597 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n having pyramid weight k.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 5, 9, 3, 1, 7, 21, 23, 5, 1, 9, 38, 74, 56, 8, 1, 11, 60, 170, 237, 130, 13, 1, 13, 87, 325, 674, 706, 293, 21, 1, 15, 119, 553, 1535, 2442, 1994, 645, 34, 1, 17, 156, 868, 3030, 6542, 8259, 5401, 1395, 55, 1, 19, 198, 1284, 5411, 14840, 25738, 26441

Offset: 2

Emeric Deutsch, Dec 12 2005

A pyramid in a Dyck word (path) is a factor of the form U^h D^h, h being the height of the pyramid. A pyramid in a Dyck word 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 Dyck path (word) is the sum of the heights of its maximal pyramids. Row sums are the Fine numbers (A000957). T(n,n)=fibonacci(n-1) (A000045).

			T(4,3)=3 because we have U(UD)(UUDD)D, U(UUDD)(UD)D and U(UD)(UD)(UD)D, where U=(1,1),D=(1,-1) (the maximal pyramids are shown between parentheses).
Triangle begins:
1;
1,1;
1,3,2;
1,5,9,3;
1,7,21,23,5;
1,9,38,74,56,8;

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

Cf. A000957, A091866, A000045.

G:=(1+z-2*t^2*z^2-sqrt((1-z)*(1-z-4*t*z+4*t^2*z^2)))/2/z/(1+t-t^2*z-t^3*z^2)-1: Gser:=simplify(series(G,z=0,15)): for n from 2 to 13 do P[n]:=expand(coeff(Gser,z^n)) od: for n from 2 to 13 do seq(coeff(P[n],t^j),j=2..n) od; # yields sequence in triangular form

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

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013

cp's OEIS Frontend

A166301 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having pyramid weight k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A247285 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n (n>=1) having k (0<=k<=n-1) upper interactions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A091977 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k exterior pairs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A094449 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n and having sum of pyramid heights equal to k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A114597 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n having pyramid weight k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions