login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A094322 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k pyramids. 1
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

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

LINKS

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

FORMULA

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.

EXAMPLE

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];

MAPLE

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

MATHEMATICA

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

CROSSREFS

Cf. A082989, A000108.

Sequence in context: A159755 A215534 A304573 * A136757 A134599 A117235

Adjacent sequences:  A094319 A094320 A094321 * A094323 A094324 A094325

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jun 03 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 20:24 EDT 2019. Contains 328273 sequences. (Running on oeis4.)