login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A114489 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n that have k valleys at level 1. 1
1, 1, 2, 4, 1, 9, 4, 1, 22, 14, 5, 1, 58, 46, 21, 6, 1, 163, 149, 80, 29, 7, 1, 483, 484, 292, 124, 38, 8, 1, 1494, 1589, 1044, 498, 179, 48, 9, 1, 4783, 5288, 3701, 1928, 780, 246, 59, 10, 1, 15740, 17848, 13096, 7304, 3237, 1152, 326, 71, 11, 1, 52956, 61060, 46428 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

T(n,k) is also the number of Dyck paths of semilength n having k pairs of consecutive valleys at the same level. Example: T(4,1)=4 because we have U(DU)(DU)UDD, U(DU)UD(DU)D, UUD(DU)(DU)D, and UU(DU)(DU)DD, where U=(1,1), D=(1,-1); the pairs of consecutive same-level valleys are shown between parentheses. - Emeric Deutsch, Jun 19 2011

Rows 0 and 1 contain one term each; row n contains n-1 terms (n>=2).

Row sums are the Catalan numbers (A000108).

Column 0 yields A059019.

Sum(k*T(n,k), k=0..n-1) = 6*binomial(2*n-1,n-3)/(n+3) (A003517).

LINKS

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

FORMULA

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

EXAMPLE

T(4,1) = 4 because we have UU(DU)DDUD, UDUU(DU)DD, UU(DU)UDDD and UUUD(DU)DD, where U=(1,1), D=(1,-1); the valleys at level 1 are shown between parentheses.

Triangle starts:

1;

1;

2;

4,   1;

9,   4, 1;

22, 14, 5, 1;

MAPLE

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

# second Maple program:

b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,

      `if`(x=0, 1, expand(b(x-1, y-1, 1)+

      `if`(t=1 and y=1, z, 1)*b(x-1, y+1, 0))))

    end:

T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):

seq(T(n), n=0..14);  # Alois P. Heinz, Mar 12 2014

MATHEMATICA

b[x_, y_, t_] :=  b[x, y, t] = If[y>x || y<0, 0, If[x == 0, 1, Expand[b[x-1, y-1, 1] + If[t == 1 && y == 1, z, 1]*b[x-1, y+1, 0]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-Fran├žois Alcover, May 20 2015, after Alois P. Heinz *)

CROSSREFS

Cf. A000108, A059019, A003517.

Sequence in context: A169840 A321461 A092107 * A101974 A097607 A132893

Adjacent sequences:  A114486 A114487 A114488 * A114490 A114491 A114492

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Dec 01 2005

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 August 1 22:36 EDT 2021. Contains 346408 sequences. (Running on oeis4.)