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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A118920 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that cross the x-axis k times (n>=1, k>=0). 2
2, 4, 2, 10, 8, 2, 28, 28, 12, 2, 84, 96, 54, 16, 2, 264, 330, 220, 88, 20, 2, 858, 1144, 858, 416, 130, 24, 2, 2860, 4004, 3276, 1820, 700, 180, 28, 2, 9724, 14144, 12376, 7616, 3400, 1088, 238, 32, 2, 33592, 50388, 46512, 31008, 15504, 5814, 1596, 304, 36, 2 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

A Grand Dyck path of semilength n is a path in the half-plane x>=0, starting at (0,0), ending at (2n,0) and consisting of steps u=(1,1) and d=(1,-1).

Row sums are the central binomial coefficients (A000984). T(n,0)=2*A000108(n) (the Catalan numbers doubled). T(n,1)=2*A002057(n-2). Sum(k*T(n,k),k>=0)=2*A008549(n-1). For crossings of the x-axis in one direction, see A118919.

This triangle is related to paired pattern P_3 and P_4 defined in the Pan & Remmel link. - Ran Pan, Feb 01 2016

LINKS

Table of n, a(n) for n=1..55.

Ran Pan, Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

FORMULA

T(n,k) = 2*(k+1)*binomial(2*n,n-k-1)/n.

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

More generally, the trivariate g.f. G=G(x,y,z), where x (y) marks number of downward (upward) crossings of the x-axis, is given by G = z*C^2*(2+(x+y)*z*C^2)/(1-x*y*z^2*C^4).

EXAMPLE

T(3,1)=8 because we have ud|dudu,ud|dduu,udud|du,uudd|du,du|udud,du|uudd, dudu|ud and dduu|ud (the crossings of the x-axis are shown by |).

Triangle starts:

2;

4,2;

10,8,2;

28,28,12,2;

84,96,54,16,2;

MAPLE

T:=(n, k)->2*(k+1)*binomial(2*n, n-k-1)/n: for n from 1 to 11 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form

MATHEMATICA

Table[2 (k + 1) Binomial[2 n, n - k - 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Feb 01 2016 *)

PROG

(Sage) # Algorithm of L. Seidel (1877)

# Prints the first n rows of the triangle.

def A118920_triangle(n) :

    D = [0]*(n+2); D[1] = 2

    b = True; h = 1

    for i in range(2*n) :

        if b :

            for k in range(h, 0, -1) : D[k] += D[k-1]

            h += 1

        else :

            for k in range(1, h, 1) : D[k] += D[k+1]

        b = not b

        if b : print [D[z] for z in (1..h-1) ]

A118920_triangle(10)  # Peter Luschny, Oct 19 2012

(PARI) T(n, k) = 2*(k+1)*binomial(2*n, n-k-1)/n \\ Charles R Greathouse IV, Feb 01 2016

CROSSREFS

Cf. A000984, A000108, A002057, A008549, A118919.

Sequence in context: A236959 A097577 A097692 * A162982 A259707 A247085

Adjacent sequences:  A118917 A118918 A118919 * A118921 A118922 A118923

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, May 06 2006

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 06:54 EDT 2017. Contains 292502 sequences.