A082989 -id:A082989 - cp's OEIS frontend

A035929 Number of Dyck n-paths starting U^mD^m (an m-pyramid), followed by a pyramid-free Dyck path.

0, 1, 1, 1, 2, 6, 19, 61, 200, 670, 2286, 7918, 27770, 98424, 351983, 1268541, 4602752, 16799894, 61642078, 227239086, 841230292, 3126039364, 11656497518, 43601626146, 163561902392, 615183356156, 2319423532024, 8764535189296, 33187922345210, 125912855167740

Offset: 0

N. J. A. Sloane

nonn

Hankel transform is -A128834. - Paul Barry, Jul 04 2009

			The a(5) = 6 cases are UUUUUDDDDD, UDUUUDUDDD, UDUUUDDUDD, UDUUDUUDDDD, UDUUDUDUDUDD and UUDDUUDUDD.

Alois P. Heinz, Table of n, a(n) for n = 0..500
J.-L. Baril, S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv:1509.08216 [cs.DM], 2015.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A082989.

/* Expansion */ Q:=Rationals(); R:=PowerSeriesRing(Q,30); R!(2*x/(1+x+(1-x)*Sqrt(1-4*x))); // G. C. Greubel, Jan 15 2018

A:= proc(n) option remember; if n=0 then 0 else convert (series ((A(n-1)^2 *(x^2-2*x+2) +x)/ (x+1), x,n+1), polynom) fi end: a:= n-> coeff (A(n), x,n): seq (a(n), n=0..25); # Alois P. Heinz, Aug 23 2008

CoefficientList[Series[2*x/(1+x+(1-x)*Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

x='x+O('x^30); concat([0], Vec(2*x/(1+x+(1-x)*sqrt(1-4*x)))) \\ G. C. Greubel, Jan 15 2018

G.f.: A(x) satisfies A^2*(x^2-2*x+2) - A*(x+1) + x = 0.
The generating function can be written as x/(1-x) times that of A082989.
G.f.: (2*x)/(1+x+(1-x)*sqrt(1-4*x)) = 1/(1-x(1-x)/(1-x/(1-x/(1-x/(1-x/(1-x/(1-... (continued fraction). - Paul Barry, Jul 04 2009
From Gary W. Adamson, Jul 14 2011: (Start)
a(n), n>0; is the upper left term in M^(n-1), where M is the infinite square production matrix:
  1, 1, 0, 0, 0, 0, ...
  0, 1, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, 1, ...
  ... (End)
D-finite with recurrence: 2*n*a(n) +4*(-3*n+4)*a(n-1) +(19*n-44)*a(n-2) + (-13*n + 36)*a(n-3) +2*(2*n-7)*a(n-4)=0. - R. J. Mathar, Nov 24 2012
a(n) ~ 3 * 4^n / (25 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
From Alexander Burstein, Aug 05 2017: (Start)
G.f: A = x/(1-(1-x)*x*C) = x*C/(1+x^2*C^2) = x*C^3/(1+2*x*C^3), where C is the g.f. of A000108.
A/x composed with x*C = g.f. of A165543, where A and C are as above. (End)

Edited by Louis Shapiro, Feb 16 2005

Wrong g.f. removed by Vaclav Kotesovec, Feb 12 2014

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

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 4, 3, 3, 3, 1, 13, 11, 7, 6, 4, 1, 42, 37, 23, 14, 10, 5, 1, 139, 122, 78, 43, 25, 15, 6, 1, 470, 408, 262, 145, 75, 41, 21, 7, 1, 1616, 1390, 887, 494, 251, 124, 63, 28, 8, 1, 5632, 4810, 3048, 1694, 864, 414, 196, 92, 36, 9, 1, 19852, 16857, 10622

Offset: 0

Emeric Deutsch, Jun 03 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,2)=2 because there are two Dyck paths of semilength 3 having 2 pyramids: (UD)(UUDD) and (UUDD)(UD) (pyramids shown between parentheses).
Triangle begins:
[1];
[0, 1];
[0, 1, 1];
[1, 1, 2, 1];
[4, 3, 3, 3, 1];
[13, 11, 7, 6, 4, 1];
[42, 37, 23, 14, 10, 5, 1];

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

Cf. A082989, A000108.

C:=(1-sqrt(1-4*z))/2/z: G:=(1-z)/(1-z*C+z^2*C-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);
# second Maple program:
b:= proc(x, y, u, t) option remember; expand(`if`(y<0 or y>x, 0,
      `if`(x=0, `if`(t, z, 1), (b(x-1, y-1, false, t)+
      b(x-1, y+1, true, t and u or y=0))*`if`(t and y=0, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p,z,i), i=0..n))(b(2*n, 0, false$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Jul 22 2015

b[x_, y_, u_, t_] := b[x, y, u, t] = Expand[If[y<0 || y>x, 0, If[x==0, If[ t, z, 1], (b[x-1, y-1, False, t] + b[x-1, y+1, True, t && u || y == 0]) * If[t && y==0, z, 1]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, n}]][b[2*n, 0, False, False]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 29 2016, after Alois P. Heinz *)

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

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.

cp's OEIS Frontend

A035929 Number of Dyck n-paths starting U^mD^m (an m-pyramid), followed by a pyramid-free Dyck path.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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